Set difference

Base.:\Method
\(X::LazySet, Y::LazySet)

Convenience alias for set difference.

Input

  • X – first set
  • Y – second set

Output

The set difference between X and Y.

Notes

If X and Y are intervals, X \ Y is used in some libraries to denote the left division, as the example below shows. However, it should not be confused with the set difference. For example,

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

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

julia> X.dat \ Y.dat  # computing the left division
[0.5, ∞]
source
LazySets.differenceMethod
difference(X::Interval{N}, Y::Interval) where {N}

Compute the set difference between two intervals.

The set difference is defined as:

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

The backslash symbol, \, can be used as an alias.

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 \setminus 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 if 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 or not. 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.
source
LazySets.differenceMethod
difference(X::AbstractHyperrectangle{N}, Y::AbstractHyperrectangle) where {N}

Compute the set difference between two hyperrectangular sets.

Input

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

The set difference is defined as:

\[ X \setminus 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.

source