\input CS445Hdr
% This is CS445N6.tex of February 25, 09:00 am
\def\header{6. Intersection problems}
\def\title{Lecture 11}
\chap{\header.}
\sect{6.1 Introduction and applications.}
Another frequently occuring type of geometrical problem is to determine
whether two figures intersect, and, if so, to compute
their common part. This basic {\it intersection
problem} has several important
variants, some of which will be covered in this chapter.\par
The classical application of intersection algorithms is in the
determination of visibility (hidden surface elimination) in three-dimensional
computer graphics: an object can obscure another only if their projections
on the picture plane intersect, and the first is closer to the observer than
the second. Notice that this is a essentially a two-dimensional
intersection problem, distinct from (and considerably simpler than) the
three-dimensional one of deciding whether the objects themselves
intersect in space.\par
Another important application is the checking of design rules in
VLSI circuits. Typically, these rules have the form ``two circuit elements
of types such-and-such cannot be closer than $x$ length units’’. This
is equivalent to saying that ``two circuit elements of types such-and-such,
if extended in all directions by $x/2$ units, should not
intersect’’.\par
Finally, with reference to the cluster analysis example we
discussed in the previous chapter, we should remark that two sets
of points can be separated by a straight line iff the
same is true of their convex hulls, and this in turn happens if
and only if the two hulls do not intersect.\par
\sect{6.2. Intersection of two polygons.}
One of the simplest intersection problems is computing
the common part of two convex polygons $P$ and $Q$. We can use the
same technique we discussed in section 5.4, namely breaking
both poligons into simpler pieces by drawing vertical lines
through their vertices. The set of all such lines divides the
plane into $n+1$ vertical strips (where $n$ is the total number of
vertices in both polygons), and the intersection of each polygon with
any of the strips either is empty, or is a single trapezoid with vertical
(possibly degenerate) bases.\fig5\par
The intersection of two trapezoids in the same strip has at most
six vertices, and these can be found in $O(1)$ time. Since the
two polygons are convex, it is relatively easy to produce the
strips in the proper sequence and compute the corresponding trapezoids in
time $O(n)$ (note that no general sorting step is required).
The vertices of the intersection will also be generated in
left-to-right order, and, since the intersection itself is a
convex polygon, it is a simple matter to rearrange them in
counterclockwise order. We conclude that the whole algorithm will
run in $O(n)$ time. If each strip is processed as soon as it
is generated, the extra working space required by
the algorithm will be essentially $O(1)$.\par
The description and coding of this algorithm becomes considerably
simpler if both the input polygons and the answer are represented using
the half-hull technique of section 4.10. If we write $P=P↑U\inte P↑L$ and
$Q=Q↑U\inte Q↑L$, then
$$\eqalignno{P\inte Q=|(P↑U\inte P↑L)\inte(Q↑U\inte Q↑L)\cr\va
\null=|(P↑U\inte Q↑U)\inte (P↑L\inte Q↑L).|(1)\cr}$$\par
The computation of $P↑U \inte Q↑U$ can be carried out in linear time
by sweeping simultaneously through both half-hulls in increasing order
of $x$-coordinate; the same holds for $P↑L\inte Q↑L$. We could take
$$\eqalign{(P\inte Q)↑U=|P↑U\inte Q↑U,\cr\vb
(P\inte Q)↑L=|P↑L\inte Q↑L,\cr}\eqno(2)$$
except for the fact the left hand sides in (2) may have some edges and
vertices (perhaps all of them) that do not belong to the
intersection of $P$ and $Q$.\fig4
Therefore, we must carry out the
computation of both $P↑U \inte Q↑U$ and $P↑L\inte Q↑L$
in parallel, and output them only where the first is above the second.
This is just another way of describing the strip-and-trapezoid method
given before.\par
This method can be easily adapted for the case of monotone polygons.
The only caveat is that the intersection of two such polygons
can have two or more monotone pieces:\fig4
However, since the pieces do not overlap when projected onto the
monotonicity axis $d$, they will be encountered one at a time by
the intersection algorithm, and therefore will not add to its complexity.\par
We could consider generalizing this method for arbitrary simple polygons,
as we did for point inclusion. However, the algorithm is
rather messy and extremely inefficient, so we will postpone
the discussion of this problem
until the end of the chapter.
Actually, by exploiting the full power of the half-hull technique and
the properties of convex figures, we can detect in just
logarithmic time whether
two convex polygons $P$ and $Q$ intersect. The algorithm given
below explains how this is done, and therefore solves
problem 1 of the midterm\foot1{Except that the original
formulation was in terms of left and right half-hulls, instead of
the upper and lower ones. We apologize for this unfortunate
notational mix-up.}.\par
The basis of this algorithm is the following fact:\par
\theorem{6.1}{Two convex polygons $P$ and $Q$ intersect iff $P↑U$
intersects $Q↑L$ and $P↑L$ intersects $Q↑U$.}
\proof{If $p$ is a point in the intersection of $P$ and $Q$, then
$p$ has to be in all four of the
sets $P↑U$, $Q↑U$, $P↑L$ and $Q↑L$; this implies that both
$P↑U$ intersects $Q↑L$ and $P↑L$ intersects $Q↑U$.\par
\hp Conversely, if $P$ and $Q$ are disjoint, they admit a
separating line (cf. theorem 3.18). If this line is vertical, or $P$
is above the line and $Q$ is below it, we conclude that the line also
separates $P↑L$ from $Q↑U$, and therefore these two are
disjoint; if $Q$ is above and $P$ is below, we
conclude that $P↑U$ and $Q↑L$ are disjoint.}
The algorithm below takes a lower half-hull
$X$ and a upper one $Y$ and checks whether they are disjoint,
locating the leftmost point in their intersection if that is not the case.
The algorithm assumes both $X$ and $Y$ have at least two vertices to
begin with.\par
To simplify the wording of the algorithm, let’s define an {\it upward}
(resp. {\it downward}) {\it beam}
as being an infinite figure consisting of all points of the plane
that are above (resp. below) a given line segment.
The basic idea of the algorithm is the following:
consider the beams $A$ and $B$ circunscribed at $X$ and $Y$
and tangent to them at the median corners $p$ and $q$, respectively:\fig4
If the two beams are disjoint, we can immediately conclude that
the two half-hulls are disjoint also. Otherwise,
by drawing vertical lines through $p$ and $q$,
we decompose each beam into two smaller ones.
We then have several possible cases, depending
on how these four beams relate to each other.\par
If one of the parts of $A$ does not intersect the
$B$, then that part cannot contain any point
common to both hulls, and we can eliminate from consideration
that part of $X$ contained in it;\fig5
and of course this same assertion holds if we rotate everything
by 180\deg.\par
If each of the four beams intersects one of the opposite ones,
then all four may contain points common to both $X$ and $Y$.
However, since the boundaries of the hulls are connected
lines that pass through $p$ and $q$,
we can easily conclude that the {\it leftmost} intersection point
will never be located in the ``rightmost’’ of the four
beams:\fig5
Therefore, we can again eliminate from consideration
the piece of that is contained in this region.\par
The process continues until both half-hulls are reduced
to a single edge; once we get to this case, the
problem becomes trivial. Since one of
the two sets loses half of its edges at each iteration,
the number of iterations to get to this
terminal situation is will be $O\biglp\log\leftv
X\rightv+\log\leftv Y\rightv\bigrp=O(\log n)$.\par
\algorithm{6.1}{Testing intesection of an upper half-hull with a lower one.}{
\step 1. [Find bounding regions.] {Let $p$ be the median vertex of
$X$, and let $\alpha$ be a supporting line of $X$ (not a vertical one) that
passes through $p$. Let $A$ be the upward beam circunscribed
around $X$ and bounded below by $\alpha$. Similarly,
let $q$ be the median vertex of $Y$, let $\beta$ be a supporting
line of $Y$ passing through $q$, and let $B$ be the corresponding
downward beam circunscribing $Y$.
Let $A1̌$ and $A2̌$ be the two parts of $A1̌$
are respectively to the left and to the right of $p$;
let $X1̌$ and $X2̌$ be the parts of $X$ contained in each of these
two regions. Similarly,
divide $B$ in two regions, $B1̌$ to the left of $q$
and $B2̌$ to the right of it, and let $Y1̌$ and $Y2̌$ be the parts of
$Y$ contained in $B1̌$ and $B2̌$, respectively.\fig5}
\step 2. [Check for disjointness.] {If $A$ and $B$ do not intersect,
report that the given hulls were disjoint and stop.}
\step 3. [Check for termination.] {If both $X$ and $Y$ have a single edge
each, then $X=A$ and $Y=B$; use an {\it ad hoc} method to compute
$A\inte B$, return its leftmost point, and stop.}
\step 4. [Eliminate impossible cases.] {If $p$ is not in $B$,
then either $A1̌$ or $A2̌$ is entirely outside $B$;
set $X\gets X2̌$ or $X\gets X1̌$,
according to the case, and go back to step 1.
Similarly, if $q$ is not in $A$, either $B1̌$ or $B2̌$ is entirely
outside $A$; set $Y\gets Y2̌$ or $Y\gets Y1̌$, according
to the case, and go to step 1.}
\step 5. [Discard rightmost part.] {(Now we have $p\in B$ and
$q\in A$) If $X$ has only two vertices, or $q$ is to the right of $p$,
set $Y\gets Y1̌$ and go back to step 1. Otherwise, $X$ has at least
three vertices and $q$ is to the left of $p$: set $X\gets X1̌$
and go back to step 1.}}
Given two convex polygons $P$ and $Q$, we apply the algorithm above
first to $X=P↑L$ and $Y=Q↑U$, and then to $X=Q↑L$ and $Y=P↑U$.
If one of the two pairs are determined to be disjoint, the
same will be true of $P$ and $Q$; otherwise $P$ and $Q$ will intersect,
and the {\it rightmost} of the two answers will be the leftmost
point of $P\inte Q$.\par
One may wonder whether this method can be used to actually
compute the intersection, rather than just determining whether
it is empty or not. Any intersection algorithm must take time at least
proportional to the number of ``new’’ vertices in the intersection
(that is, vertices that were not corners of the original polygons).
Unfortunately, the number of new vertices can be as large as $\Omega(n)$,
as can be seen from the figure below.\fig4\par
Therefore, computing the intersection of two convex polygons
will require linear time, at least in some cases.
However, it is possible to use this algorithm (and its symmetrical version,
that computes the rightmost intersection point of $X$ and $Y$) as the
basis of an algorithm for computing the intersection of two convex
polygons in time $O(\log n + m)$, where $m$ is the number of
vertices of the intersection. The details are left to the reader.\par
Algorithm 6.1 can easily be extended so as to produce a separating line
for $X$ and $Y$ when they are disjoint. This is not as trivial as it may seem:
when we terminate the algorithm in step 2 the hulls
$X$ and $Y$ are just subsets of the original ones, so a line that separates
them may intersect the parts that were thrown away.\par
However, it turns out that a slight modification of algorithm 6.1
is enough to remove this problem. In steps 4 and 5, instead of
just throwing away one of the halves of $X$ or $Y$, say $X1̌$, we should
replace it by the corresponding half-beam $B1̌$. In this way,
instead of becoming thinner and thinner, the two hulls retain
their original width, but their edges are progressively engulfed
by two growing ``wings’’, until only two of the original vertices
remain.\fig4
It can be shown that the modified
algorithm still finds the leftmost intersection point, if it
exists. If not, then the final sets $X$ and $Y$ will be
disjoint and contain the original hulls, so a separating line for the
former will also separate the latter.\par
\sect{6.3. The problem of pairwise intersections.}
The {\it pairwise intersection problem} comes in three major
variants: given a collection $\Cscr$ of $n$ geometrical ``objects’’,
we may want to know (a) {\it whether} any two of
them intersect, (b) {\it how many}
pairs of objects intersect, or (c) {\it which} pairs intersect.\par
The objects in $\Cscr$
usually are figures or other geometrical entites of bounded complexity,
e.g. line segments, rectangles, triangles, circles, and so forth, so that
testing a single pair for intersection is usually an $O(1)$ operation. A
trivial algorithm (check all possible pairs)
will therefore solve all three variants above in $O(n↑2)$
time; the question is, can we do better than this?\par
A non-trivial lower bound can be derived from a
known result of complexity theory, namely
that at least $\Omega(n\log n)$ time is required to determine
whether a collection $X$ of $n$ numbers
contains two identical elements (this is
known as the {\it element uniqueness problem}). This problem can
be mapped into the pairwise intersection one by
taking $\Cscr$ to be a set of points on the $x$-axis, whose abscissas
are the numbers in $X$.\par
It follows that any general algorithm
for solving variant (a) or (b) will require
$\Omega(n\log n)$ time, too\foot1{This argument
applies even if one restricts $\Cscr$ to a specific class of figures,
e.g. triangles. If the numbers in $X$ have precision $\epsilon$, we take
$\Cscr$ to be a set of congruent figures of the specified kind,
of width $\null<{\epsilon\over 2}$, displaced horizontally according
to the numbers in $X$.}. The lower bound for variant (c),
in which the $I$ intersecting pairs have to be listed, is
therefore $\Omega(n\log n + I)$.\par
\digress{Note how in this chapter we got to the rather unusual
situation of specifying the complexity of a problem as a function of the
sizes both the input {\it and the output}, rather than of the input alone.}
An algorithm that solves variant (a) in time $O(n\log n)$ has been known for
some time. For variant (c), however, no reasonably general algorithm
is known that realizes the $O(n\log n+I)$ lower bound.
The ones that do so are restricted to special classes of
objects, e.g. rectangles whose sides are aligned with the axes.
If $\Cscr$ is a collection of general line segments, the fastest
algorithm known that reports all intersections takes
$\Omega((n+I)\log n)$ in the worst case. This is true
also of the best algorithm known for reporting the intersection
of $n$ circles with equal radii (which is equivalent to the
problem of finding among $n$ points all pairs closer than a given distance).
Note that this performance is quite reasonable when $I$ is small, but
in the worst case it becomes $\Omega(n↑2\log n)$, i.e. even worse than
the trivial, exaustive search algorithm. This algorithm is general enough to be extended to other kinds of objects,
like circles, triangles, general rectangles, and so forth, and it is also the
basis of several other specialized intersection algorithms.\par
As for variant (b), the gap is still wider. The only lower bound we know of
is $\Omega(n\log n)$, the same as that of (a). For some special kinds
of figures, there are algorithms that realize this lower bound;
however, for reasonably general $\Cscr$ the fastest intersection counting
algorithms take as long as the ones that report all intersections, namely
$O((n+I)\log n)$.
\sect{6.3.1. The sweeping line method.}
The pairwise intersection algorithms we will study next are all based on a
technique that is very common in the processing of geometrical problems,
especially of those involving points connected
by straight edges. This technique consists in sorting
the points that define the problem according to their projections onto
a particular axis $d$, and then processing them in that order.
We can visualize this process by imagining that the plane is swept by a line
perpendicular to $d$; whenever the line encounters one of the
given points, some event ``happens’’ that changes the state of the
computation. Usually, the latter can be described in terms
of the segments determined on the sweeping line by the points
and edges of the input problem. Therefore, this technique
maps a two-dimensional static problem into
a one-dimensional dynamic process.\par
We have already used this {\it sweeping line method} on a number
of previous occasions (albeit in a rather limited fashion),
e.g., in the half-hull variant of Graham’s
algorithm. To illustrate its use in the pairwise intersection problem, let’s
begin with a degenerate case, namely let’s assume $\Cscr$ is a
collection of intervals on the $x$-axis.\par
For this case, the sweeping line algorithm reduces to a very simple one:
we scan the plane with a vertical line,
maintaining a list (initially empty) of the
segments this line is currently intercepting.
Whenever the left endpoint of a segment is encountered, we report
an intersection between it and each segment currently in the list,
and we add it to
the latter; when a right endpoint is encountered, the corresponding
segment is deleted from the list. The time required is $O(n\log n)$ to
sort the collection of endpoints, $O(n)$ to insert and delete them from
the list, and $O(I)$ for reporting the intersections --- giving a total of
$O(n\log n + I)$.\par
If all we have to do is to check for the existence of some intersection, or
even to count the number of intersections, the time required drops
to $O(n\log n)$. In the first case we stop as soon as the list contains
two elements. In the second, we keep a count of the intersections
detected so far; whenever a new segment is encountered,
instead of reporting all its intersections we just add to this
count the current size of the list. As we can see, in all three
variants of the problem the optimum performance can be attained.\par
As a less trivial example, let’s take $\Cscr$ to be a collection of line
segments on the plane, consisting of a set $V$ of vertical segments
and a set $H$ of horizontal ones:\fig4
For simplicity’s sake, let’s assume there are no $H$-$H$ or $V$-$V$
intersections.
As before, while we sweep a vertical line through this collection,
we keep a list of all horizontal segments that the line currently intercepts.
Whenever we encounter the left endpoint of an horizontal segment,
we add it to the list, and we delete it when its right endpoint is
encountered. When a vertical segment is encountered, we report one
intersection between it and each segment on the list whose ordinate
falls between the endpoints of the vertical segment.\par
In order to find those segments in a reasonably short time, the
current list has to be maintained as a balanced search tree.
Insertion and deletion of $H$ segments take $O(\log n)$ time each. When
a vertical segment is encountered, we look up its endpoints
in the tree to find the first and last nodes in that interval
(an $O(\log n)$ operation) and traverse all
nodes between the two (which takes $O(\log n)$ plus $O(1)$
time per node visited). The total time is therefore $O(n\log n + I)$,
as in the previous example.\par
We can also get optimal running time for variants (a) and (b).
For the first, all we have to do is to stop when the first intersection
is found. For variant (b), we can store in each node of the tree
the number of nodes in its left subtree. From numbers values,
the search routine can compute (still in $O(\log n)$ time) the
nuber of nodes preceding a given key, i.e. the number of
$H$ segments above a given point. The difference between
these counts for the upper and lower endpoints of a vertical
segment is the number of horizontal ones it
intersects. The maintenance of
these counts does not increase the asymptotic costs of insertion
and deletion, and so the total cost is just $O(n\log n)$,
independently of $I$.\par
\sect{6.3.2. Pairwise intersection of general line segments.}
Let’s now tackle the pairwise intersection problem for a set $\Cscr$
of $n$ {\it general} line segments on the plane. If we try
to apply the sweeping line technique to this problem, we
encounter one immediate difficulty, namely that the intersections
of the segments with the line move continuously up and down
along it as the line moves between one point and the next.\par
As long as we encounter no intersections, this problem is of
no consequence, since the vertical ordering of the segments intercepted
by the sweeping line does not change between successive
point encounters. Therefore, we can still remember those
segments in a sorted search tree. Whenever we hit
a new left endpoint, we can locate the two
segments immediately above and below it in $O(\log n)$ time,
and insert the new segment there. When a right endpoint is encountered,
we just delete the corresponding segment from this tree.\par
As a first idea, we could think of checking for intersections whenever
a new segment is inserted. Of course, we can visit all segments
currently in the tree and see if they meet the new one, but this
would be too expensive. On the other hand, if we just look at its
two neighbors in the list, we may miss some intersections, as in
the example below:\fig4 \par
It takes very little to fix this problem, since two
segments can intersect only if they are neighbors in
the sorted list at some time before the intersection is
encountered. Two segments can become neighbors in only two
occasions: when the second of them is inserted in the list,
or when a segment that was between them is deleted.\par
Therefore, if every inserted segment is checked
for intersection against the two
adjacent ones, and the same test is applied
to the the two that become adjacent when a a segment is deleted, then
we will always detect an intersection before the sweeping
line encounters it. This algorithm, due to Shamos and Hoey (1976)
solves variant (a) in $O(n\log n)$ time, and therefore
is optimal\footfig1(3){Surprisingly enough, this method
will {\it not} find the leftmost intersection, as demonstrated by the
example at the right. The first intersection to be detected seems
rather hard to characterize.}.\par
If we want to fint {\it all} intersections, we must be able to keep the
current segment tree correctly ordered when we sweep past an
intersection point. This event has the effect of interchanging two
segments in the list; if we are careful enough, this interchange can be done in
$O(1)$ time. We must not forget, however, that this
event represents a third occasion in which two segments
may become adjacent; therefore, we must check the two
interchanged segments for intersections against their new
immediate neighbors. This algorithm was developed by J. Bentley
and Th. Ottman (1978).\par
Intersection and endpoint events have to be processed in the
appropriate order, which is determined by the ordering of
their $x$-coordinates. Since the order in which the intersections
are detected is quite random, those future events have to be stored
in a priority queue (a sorted heap would do fine). This queue
will contain $O(n+I)$ elements in the worst case, and therefore
the cost of inserting each new event will be $O(\log(n+I))=
O(\log(n+n↑2))=O(\log n)$. Assuming the cost of processing
an event is $O(\log n)$ for an endpoint, and $O(1)$ for
an intersection, the total time will be $O(n\log n) + O(I) + O(I\log n)=
O((n+I)\log n)$, which is somewhat worse than the theoretical
lower bound of $\Omega(n\log n + I)$.\par
\digress{Each intersection can be reported either when it is detected,
or when the sweeping line hits it. In the second case, the
intersections will be reported in increasing order of $x$-coordinate.
This sorting behavior could be viewed as the reason for
having an $O(I\log n)=O(I\log I)$ term in the formula for its
running time; accordingly, we might conjecture that any
$O(n\log n + I)$ algorithm has per force to produce the
intersections in ``random’’ order. This will not be firmly
established, however, until someone shows how to map
the problem of sorting more than $\Omega(n)$ numbers into
that of reporting the intersections of $n$ line segments in
sorted order.}
This algorithm can be extended to compute the intersection of many other
kinds of figures, e.g. circles, triangles, and so forth. The essential
requirements are that (1) the figures in $\Cscr$ are monotone in the
direction of sweep, so that their intersections with the sweeping line
can be properly ordered; (2) if a sweeping line meets two objects
of $\Cscr$, it must be possible to determine in $O(1)$ time which
of them is above the other; and (3) for any pair of
objects in $\Cscr$, it must be
possible to determine in $O(1)$ time whether they intersect. If
these conditions are satisfied, then the analysis above will also hold.\par
\vfill\eject\end
damn damn damn damn damn damn damn damn damn!
damn damn damn damn damn damn damn damn damn!
damn damn damn damn damn damn damn damn damn!
damn damn damn damn damn damn damn damn damn!
damn damn damn damn damn damn damn damn damn!
damn damn damn damn damn damn damn damn damn!
damn damn damn damn damn damn damn damn damn!
damn damn damn damn damn damn damn damn damn!
damn damn damn damn damn damn damn damn damn!
damn damn damn damn damn damn damn damn damn!
damn damn damn damn damn damn damn damn damn!
damn damn damn damn damn damn damn damn damn!
damn damn damn damn damn damn damn damn damn!
damn damn damn damn damn damn damn damn damn!
damn damn damn damn damn damn damn damn damn!
damn damn damn damn damn damn damn damn damn!
damn damn damn damn damn damn damn damn damn!
damn damn damn damn damn damn damn damn damn!
damn damn damn damn damn damn damn damn damn!
damn damn damn damn damn damn damn damn damn!
damn damn damn damn damn damn damn damn damn!
damn damn damn damn damn damn damn damn damn!
damn damn damn damn damn damn damn damn damn!
damn damn damn damn damn damn damn damn damn!
damn damn damn damn damn damn damn damn damn!
damn damn damn damn damn damn damn damn damn!
damn damn damn damn damn damn damn damn damn!
damn damn damn damn damn damn damn damn damn!
damn damn damn damn damn damn damn damn damn!
damn damn damn damn damn damn damn damn damn!