Set difference

\(X::LazySet, Y::LazySet)

Convenience alias for the difference function.

Notes

In this library, X \ Y denotes the set difference. If X and Y are intervals, in some libraries it denotes the left division, as the example below shows.

julia> X = Interval(0, 2); Y = Interval(1, 4);

julia> X \ Y  # compute the set difference
Interval{Float64}([0, 1])

julia> X.dat \ Y.dat  # underlying intervals compute the left division instead
[0.5, ∞]

difference(X::Interval{N}, Y::Interval) where {N}

Compute the set difference between two intervals.

Input

• X – first interval
• Y – second interval

Output

Depending on the position of the intervals, the output is one of the following:

• An EmptySet.
• An Interval.
• A UnionSet of two Interval sets.

Algorithm

Let $X = [a, b]$ and $Y = [c, d]$ be intervals. Their set difference is $X ∖ Y = \{x: x ∈ X \text{ and } x ∉ Y \}$ and, depending on their position, three different results may occur:

• If $X$ and $Y$ do not overlap, i.e., if their intersection is empty, then the set difference is just $X$.
• Otherwise, let $Z = X ∩ Y ≠ ∅$, then $Z$ splits $X$ into either one or two intervals. The latter case happens when the bounds of $Y$ are strictly contained in $X$.

To check for strict inclusion, we assume that the inclusion is strict and then check whether the resulting intervals that cover $X$ (one to its left and one to its right, let them be L and R), obtained by intersection with $Y$, are flat. Three cases may arise:

• If both L and R are flat then $X = Y$ and the result is the empty set.
• If only L is flat, then the result is R, the remaining interval not covered by $Y$. Similarly, if only R is flat, then the result is L.
• Finally, if none of the intervals is flat, then $Y$ is strictly contained in $X$ and the set union of L and R is returned.

difference(X::AbstractHyperrectangle, Y::AbstractHyperrectangle)

Compute the set difference between two hyperrectangular sets.

Input

• X – first hyperrectangular set
• Y – second hyperrectangular set

The set difference is defined as:

\[ X ∖ Y = \{x: x ∈ X \text{ and } x ∉ Y \}\]

Output

A UnionSetArray consisting of the union of hyperrectangles. Note that this union is in general not convex.

Algorithm

This implementation uses IntervalArithmetic.setdiff.