Intersection of Convex Objects in Two and Three

Dimensions

B. CHAZELLE
Yale University, New Haven, Connecticut

AND
D. P. DOBKIN
Princeton University, Princeton, New Jersey

Abstract. One of the basic geometric operations involves determining whether a pair of convex objects
intersect. This problem is well understood in a model of computation in which the objects are given as
input and their intersection is returned as output. For many applications, however, it may be assumed
that the objects already exist within the computer and that the only output desired is a single piece of
data giving a common point if the objects intersect or reporting no intersection if they are disjoint. For
this problem, none of the previous lower bounds are valid and algorithms are proposed requiring
sublinear time for their solution in two and three dimensions.

Categories and Subject Descriptors: E.l [Data]: Data Structures; F.2.2 [Analysis of Algorithms]:
Nonnumerical Algorithms and Problems
General Terms: Algorithms, Theory, Verification
Additional Key Words and Phrases: Convex sets, Fibonacci search, Intersection

1. Introduction
This paper describes fast algorithms for testing the predicate,
Do convexobjectsP and Q intersect?
where an object is taken to be a line or a polygon in two dimensions or a plane or
a polyhedron in three dimensions. The related problem
Given convexobjectsP and Q, compute their intersection
has been well studied, resulting in linear lower bounds and linear or quasi-linear
upper bounds [2, 4, 11, 15-171. Lower bounds for this problem use arguments
This research was supported in part by the National Science Foundation under grants MCS 79-03428,
MCS 81-14207, MCS 83-03925, and MCS 83-03926, and by the Defense Advanced Project Agency
under contract F33615-78-C-1551, monitored by the Air Force Offtce of Scientific Research. The
research was facilitated by the use of Theory Net, NSF grant MCS 78-01689. Portions of this research
appeared in Chazelle’s Ph.D. dissertation for Yale University, entitled “Computational Geometry and
Convexity,” and appeared in the Proceedings of the 12th Annual ACM Symposium on the Theory of
Computing (Los Angeles, Calif., May). ACM, New York, 1980, pp. 146-153.
Authors’ current address: Department of Computer Science, Princeton University, Princeton, NJ 08544.
Permission to copy without fee all or part of this material is granted provided that the copies are not
made or distributed for direct commercial advantage, the ACM copyright notice and the title of the
publication and its date appear, and notice is given that copying is by permission of the Association for
Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specific permission.
0 1987 ACM 0004-541 l/87/0100-0001 $00.75

Journal ofthe Association for Computing Machinery, Vol. 34, No. 1, January 1987, pp. I-27.
2 B. CHAZELLE AND D. P. DOBKIN

INTERSECTED LINE POLYGON PLANE POLYHEDRON

LINE constont log n constont log%

I I I 1
FIG. I. The time bounds of our algo-
POLYGON log n log n log2n
rithm.
PLANE constant log2n

POLYHEDRON log3 n

claiming that linear time is required to read all inputs or report the output. For the
problem that we pose, such arguments do not apply. We only require a witness to
the intersection or nonintersection of P and Q, and we further assume that the
objects we wish to intersect are available (i.e., in random-access memory [ 11) so
that we cannot rely on input time to yield a linear lower bound.
Figure 1 summarizes our results, most of which are fully original. The time
bounds are achieved by using the standard array representation for twodimensional
objects and a special representation of polyhedra that requires O(n’) operations to
reach from the standard representation (where n denotes the total number of
vertices). An O(nlogn) preprocessing of the standard representation is actually
sufficient, but the running times given here must then be multiplied by a logn
factor [7]. Note that convex polyhedra have the structure of planar graphs, so the
number of vertices, edges,and faces are linearly related, and any of these measures
can be used to represent the input size. Although the times given in Figure 1 are
asymptotic, the constants involved are sufficiently small to make the algorithms
viable in practice. Furthermore, many of the applications for which such algorithms
might be used require a knowledge of only portions of the intersection or of the
existence of an intersection, rather than a complete description of any intersection
(A. Forrest, private communication). For example, in computer graphics,
when we wish to clip or window a scene [ 121, algorithms of the form given
here would be sufficient for identifying the polygons that would require further
processing. Also, many applications for which such algorithms might be used in
design rule checking for VLSI [4], computer geography [8], (D. Tomlin, private
communication), computer-aided design, and computer animation require a gross
procedure that detects the possibility of an intersection, from which relined
procedures can handle the small number of casesin which an intersection has been
reported and must be computed.
All these algorithms rely on a small number of unifying concepts. Convexity
combined with random-access capabilities allows for binary and Fibonacci search,
and it is with an explanation of these basic principles that we start our analysis.
Section 2 is devoted to the two-dimensional case, while Section 3 investigates the
problem cast in three dimensions.

2. Computing Planar Intersections

2.1 NOTATION. Polygons are represented by arrays with their vertices given in
clockwise order. Polygon P will have vertices pl, . . . , p,, and polygon Q vertices
41, * - -, qy. We assume that no three vertices of a polygon are collinear. All indices
of P (respectively, Q) are taken modulo p (respectively, q) in the obvious fashion.
A line is specified by any two of its points and a segment by its two endpoints. AB
always refers to the segment from A to B, and “line(AB)” represents the infinite
line containing AB. We define d(x, L) as the orthogonal distance from the point x
Intersection of Convex Objects in Two and Three Dimensions 3

FIG. 2. The distance from a convex polygon to a

line is bimodal.

L
r ’

to the line L and h(x, L, v) as the oriented distance from x to L with respect to
point v. This latter quantity is defined as -d(x, L) if x and v lie on opposite sides
of L and as d(x, L) if they lie on the same side. Both d and h can be computed
in constant time. F; represents the ith Fibonacci number with FO = F, = 1 and
FN= F,+, + FNW2,forN> 1.
2.2 FIBONACCI SEARCHON BIMODAL FUNCTIONS. A real functionfdefined on
the integers 1, 2, . . . , n is said to be unimodal if there exists an integer m (1 I m
I n) such that f is strictly increasing (respectively, decreasing) on [ 1, m] and
decreasing (respectively, increasing) on [m + 1, n], with f(m) 2 f(m + 1)
(respectively, f(m) I f(m + 1)). Kiefer [9] showed that Fibonacci search was an
optimal method of finding m, the turning point of a unimodal function, requiring
1.44 . . logn probes. We extend his algorithm to find the turning points of
a bimodal function. For our purposes, it suffices to define a bimodal function as
one for which there is an r in [ 1, n] such that f(r), f(r + I), . . . , f(n), f( l), . . . ,
f(r - 1) is unimodal. Our interest in bimodal functions stems from the following:
LEMMA 1. Let P be a convex polygon with p vertices pI, . . . , pp in clockwise
order. For any line L and any point v not in L, the function defined for i = 1, . . . ,
p by f (i) = h( pi, L, v) is bimodal.
PROOF. Let pk be the vertex of P that minimizes f (i) for i = 1, . . . , p. In case
of a tie, we choose k so that the only other integer that achieves the same value of
f is k - 1. We can do this because P is convex. We show that the sequencef (k),
f(k+ I), . . ..f@- 1) is unimodal, which suffices to prove the lemma. Let us
choose a directing vector r of the line L such that the angle (r, pkpk+,) is less than
180. All angles are measured between 0 and 360 degrees in a counterclockwise
motion. We define the oriented angles ai = (r, pipi+,) and bi = (pipi+, , pi-l, pi) for
i= 1>***, p as in Figure 2. By construction, the following relations hold for all i:
f(i + 1) = f(i) + 1pipi+ Isinai;
ai+l = ai - bi+l[mod360].
Since P is convex, all bi are less than 180 degrees; therefore the sequence
sin(ak), sin(ak+,), . . . , sin(ak-J will be positive then negative, thus showing that
f(k), f(k + l), . . . , f(k - 1) is unimodal. Cl
Since a unimodal sequence has exactly one maximum and one minimum, and
each of them is achieved in at most two points which must be consecutive modulo
n, bimodal functions have the same property. However, finding the extrema of a
bimodal function may not be so easy, since we do not know the starting point of
its unimodal sequence in advance. To circumvent this difficulty, given a bimodal
4 B. CHAZELLE AND D. P. DOBKIN

function f; we construct a unimodal function g as follows: First, let T be the line

through the points (1, f( 1)) and (n, f(n)), that is,

T(x) = 5 (f(n) -f(l)) +ft1).

Iff( 1) = f(n), then f( 1) is an extremum and fis unimodal, showing that the
extrema can be found with the previous method. Otherwise, we assume that
f( 1) < f(n) (the case f(1) > f(n) being similar). If f(2) 2 f(l), then f( 1) is a
minimum and the subsequence f(2), . . . , f(n) is unimodal, which solves our
problem. Else, iff(2) <f(l), the function g defined by
g(x) = min(fW, T(x))
can be evaluated in constant time and is unimodal. This follows, since for all x,
g(x) I f(n) 5 max( f(t)), so g first decreases,then rises, and is therefore unimodal.
It follows that the minimum of g (which is also the minimum off) can be found
with a Fibonacci search. If x is the point at which g achieves its minimum, the
sequencef(x + l), f(x + 2), . . . , f(n) is unimodal, and the maximum offcan also
be determined through a second Fibonacci search, yielding
LEMMA 2. The extrema of a bimodal function f (I), . . . , f (n) can be computed
in O(log n) time, which involves at most 2.88 . . log2n + 0( 1)function evaluations.
2.3 INTERSECTION OF A LINE WITH A CONVEX POLYGON (IGL). Combining
previous facts yields an algorithm for determining the intersection (null, 1 point, a
segment, or an edge of P) of an infinite line L and a convex polygon P.
THEOREM 3. The intersection of an infinite line with a convex polygon with p
vertices can be computed in O(log p) time.
PROOF. We can always assume that p1 does not lie on L. Then it follows from
Lemma 1 that the function f (pi) = h( pi, L, p,) is bimodal; therefore, the algorithm
of Lemma 2 allows us to find a vertex w of P that minimizes f: We know that P
and L intersect if and only if f (w) is negative or zero. In the latter case, w or an
edge including w is the unique intersection of P and L. In the former case, the
signs off(pAf(pd, . . . , f(w) and f(w),f(w + I), . . ..f(p.) can be searched by
binarysearchtodetermineiandjsuchthatf(pi)=O>f(p;+l),f(pj)IO<f(pj+l)
from which the two points of intersection are determined. 0
Our algorithm involves approximately 2.8808 logzp + 0( 1) computations off:
The extension to the case in which L is a line segment does not increase the time
bound. Since O(log p) has been shown to be a lower bound on the time complexity
for testing the inclusion of a point in a convex polygon, which is constant time
reducible to our problem, the algorithm we have described is optimal in the
minimax sense [ 161. In what follows, we refer to this algorithm as IGL. Though
our algorithms are m.ore complex than IGL, they are based on principles similar
to those used to derive this algorithm.
2.4 INTERSECTION OF Two CONVEX POLYC~NS (IGG). The algorithm for com-
puting the intersection of a line and a polygon suggests methods that might be
used to speed up algorithms for intersecting two polygons P and Q. If we could
determine the sides of P closest to Q (and vice versa), we would be able to reduce
the problem to a small number of tests of segment intersections. Our method
reduces the number of remaining edges of one of the polygons by a factor of 2 at
each iteration. The algorithm we present (referred to as IGG) returns NO if P and
Intersection of Convex Objects in Two and Three Dimensions 5

FIG. 3. AYBX formed as a bounding

quadrilateral in which P n Q lies if it
exists.

Q do not intersect and (YES, K) if they do, where K is a point of their intersection.
When a NO answer is returned, it is possible to generate in constant time a pair of
parallel lines that separate the polygons.
We begin by limiting the intersection of P and Q to a quadrilateral or a pentagon.
This requires O(logpq) stepsand also tests for simple intersections (e.g., Pcontained
in Q). From the quadrilateral we form two chains of vertices L, and L, that
intersect if and only if P and Q intersect. The iterative step of the algorithm is a
division in which we eliminate half of either L, or L,. This step is reached as one
of five possible casesdetermined from the structure of the remaining vertices.
It is important to keep in mind that by intersection of P and Q we mean the
intersection of the regions P and Q and not of the polygonal boundaries. We shall
prove further that the latter problem requires linear time, whereas our problem
can be solved in O(log(p + q)) time. We first give a description of the algorithm
and prove its correctness, and then we establish its running time.

Algorithm IGG (intersecting two polygons):

(I) “Cover Q (respectively, P) with two lines of support intersecting in P
(respectively, Q).”
(a) Let q be a point interior to Q (say the center of mass of three vertices) such
that q is not interior to P (if q is interior to P, we have found an intersection).
Compute the intersection of Q with line ( plq). This line always intersects Q in two
points a and b, which the algorithm IGL can find, as well as the edges of Q where
a and b lie, say qjqi+l and qjqj+l, respectively (see Figure 3a).
(b) If pi lies on the segment ab, it also lies in Q and the algorithm can return
(YES, p,). Otherwise, we do a Fibonacci search on the sequence of oriented angles
(p,q, p,qk), for all qk between qi+l and qj in clockwise order, in order to find the
maximum angle. Call t the corresponding vertex of Q. Such a Fibonacci search is
legitimate since the sequence is unimodal. If it were not, we could find an ordered
list of three consecutive vertices of Q with the angle relative to the middle vertex
smaller than both of the others. Then the line joining p1 to this vertex would cut
Q in more than two points, contradicting the convexity of Q. Similarly, by
6 B. CHAZELLE AND D. P. DOBKIN

considering the sequence qj+l, . . . , q;, we find the vertex u which minimizes the
angle (p, q, pI qJ. Call CI the pencil ( p1U, p1t) so defined (see Figure 3b).
(c) Apply the previous procedure (Steps a, b) with q1 relative to P. If the
algorithm does not return, it will determine another pencil, CZ, centered in q1 and
covering P. Since C, (respectively, C2) contains q1(respectively, p,), the intersection
of C, and C2 is a convex quadrilateral, p1YqlX, as shown in Figure 3b. Note that
X or Y may not be defined; in which case we can replace the missing intersection
by a segment joining the two pencils, thus obtaining a pentagon.
(II) Note that the portion of the boundary of P that lies in C, is a contiguous
polygonal line from the intersection of plX and P to the intersection of p, Y and P,
and lies also in C,. Determine its two endpoints (note that one or even both of
these endpoints may be p,). Renumber the vertices of P so that L, = (vI , . . . , vn)
gives the vertices of this polygonal line in clockwise order (we have v1 on pI Y and
v,, on p&). Throughout this section, any renumbering is implicit, that is, does not
involve any scan through the vertices. It may simply consist of the setting of an
arithmetic expression redefining the mapping. The same procedure is carried out
with Q defining L,,. = (wl, . . . , w, ). In what follows, we rename the former pI and
ql , A and B, respectively, as in Figure 3b. Note that although L, intersects A Y and
AX, it may also intersect BX or BY (in at most one point, though).
(III) We have now reduced the original problem to checking the intersection of
L, and L,,..
Let x (respectively, y) denote the polygonal line AXB (respectively, AYB). To
simplify the exposition, for two points F and G, we say that F < G if F and G are
both on x or both on y and F is on the path from A to G.
At this stage, we call upon the function INTERSECT(L,, L,) defined recursively
as follows:
INTERSECT(L,, L,,,)
Assume that n, m > 5, where n = 1L, 1 and m = 1L, 1, using the procedure of the
previous section if this is not the case:

Let F and G (respectively, E, H) denote the two intersections of line(vivi+l)

(respectively, line(wjwj+l)) with the boundary AYBXA. The point F (respectively,
H) is chosen such that vi+1(respectively, wj+J lies on the segment viF(respectively,
WjH) (see Figure 4a).
The algorithm distinguishes between cases depending on the relative positions
of GF and EH. Each case reduces the size of L, and/or L,, after which a recursive
call is made. (Casesare not mutually exclusive and each should be tested.)

Case 1. Either GF or EH lies on the same side of AB (Figure 4a).

ifGandFlieonx
then L,. = (v,, . . . , vi+1,v,)
else if G and F lie on y
then L,. = (v,, v,, . . . , v,)
ifEandHlieonx
thenL,=(w,,wj,...,~~l
else if E and H lie on y
then L,,.= (w,, . . . , wj+], w,,J
Intersection of Convex Objects in Two and Three Dimensions

X
(4

X
(4
A 0
”

X
(b)
Y

A B (4

FIG. 4. The algorithm INTERSECT. (a) Case 1. GF (EH, respectively) lies on the same side of AB, in
which case half of L, (L.., respectively) is eliminated. (b) Case 2. A, F, E, /3 and A, G, H, B occur in this
order on x and y, respectively, in which case there is no intersection. (c) Case 3. GF and EH intersect.
(d) Case 4. Av, and Bw, intersect, in which case P n Q contains their intersection point. (e) Case 5. Avi
lies strictly “above” (or “below”) BWj.

Case 2. From now on, F and E (respectively, G and H) lie on x (respectively,

y) (Figure 4b).
if F < E and G < H then return (NO)
Case 3. If the segments GF and EH intersect, let I be this intersection
(Figure 4~).
ifG<HandE<F
then if v, lies on GI
then L,. = Iv,, vi, . . . , vn)
if w,+~lies on HI
thenL,.=(~~,...,wj+~,w,)
ifH<GandF<E
then if Vi+1lies on FI
thenL,={v,,..., vi+i, vnl
if w, lies on EI
thenL,,.=(~,,w~,...,w,,,)
 8 B. CHAZELLE AND D. P. DOBKIN

Case 4. Avi and Bwj intersect (Figure 4d).

if Av, and Bw, intersect in R
then return (YES, R)
else
Case 5. Let R be the intersection of Avi and HE (Figure 4e).
if w, lies on ER
then
L,. = {VI, v,, . . . , vn)
LH = {WI3 Wj, . . . 9 Wm)
else
L= (VI,. . . I Vi+17 Vn]

Lt.= (WI, f. * 9 Wj+l, Wm)

Recursive call with parameters of smaller size.

INTERSECT (L,., L,,.)
Next we show that INTERSECT runs correctly within the given time bound. For
correctness, it sufftces to show that INTERSECT@,, ~5~) indeed tests for the
intersection of L,. and L,,. and possibly outputs a point common to P and Q.
Case 1. Suppose that G and F lie on y (the three other cases being similar)
(see Figure 4a). By construction, line(BY) intersects P at exactly one point, which
lies on the same side of B as Y. Now, since P lies totally on the same side of
line(GF) asX, the intersection of P with line(BY) lies on the segment BF. Therefore,
if L,, and L,,. intersect, at least one intersection point lies on the polygonal line
{Vi, - * . Y v,]. By making L, equal to (vr , vi, . . . , v,,), we reset the initial conditions
required by the algorithm. Moreover, we note that since the region delimited by
the new setting of L, is included in P, any intersection point later output will surely
be in P. This remark prevails in all the remaining cases.
Consider the two polygons delimited by (A, X, FG, y) and (B, X, EH, y) and call
V their intersection (see Figure 4b). Since P and Q are convex, their intersection
lies totally in I/.
Case 2. Corresponds to V empty (see Figure 4b).
Case 3. The first if statement supposes that E and F belong to Vand the other
that H and G belong to K Since both cases are similar, we treat only the first.
Suppose that Vi does not lie in I’. Then, since Gvi lies outside of EHyBxE, L, can-
not intersect this segment; therefore, if L, intersects the polygonal line vl, . . . , vi,
it also intersects v1vi. Thus the new setting of L, is legitimate. The same is true of
Wj+i. From now on, we know that both viVi+r and wjwj+r lie on the boundary of V.
Case 4. Assumes that Av; and BWj intersect (see Figure 4d). Since these two
segments lie in P and Q, respectively, their intersection lies in the intersection of P
and Q, which is then nonempty.
Case 5. First, we note that since E lies on x and Vi lies in V, R is well defined.
We also know that Avi and Bwj do not intersect. The algorithm supposessuccessively
that Avi lies “above” and “below” BWj. The two casesbeing similar, we treat only
the first. L,,. cannot intersect the polygonal line vl, . . . , Vi without first crossing
vlVie Similarly, L,. cannot intersect wl, . . . , wj without first crossing WI wj. Con-
versely, if either L,,. crosses v1Vi or L, crosses w1Wj,the intersection belongs to both
P and Q. Finally, since wl, . . . , wj (respectively, vI, . . . , vi) cannot intersect v1vi
(respectively, wI wj), the new setting of L, and L,, is legitimate.
Intersection of Convex Objects in Two and Three Dimensions 9

FIG. 5. Computing a
pair of separating lines.

To prove the time bound, we observe that the algorithm runs in constant time
between consecutive recursive calls. Every call reduces the size of one or both
polygonal lines by roughly half, and when either becomes smaller than 6, the
algorithm returns after O(log(p + q)) operations. Therefore, the main algorithm
detects the intersection of P and Q in O(log( p + q)) time.
We can regard the intersection of a line with a polygon as a special case of this
problem, and the results of the preceding section show that the algorithm described
above is optimal in the minimax sense.
We have achieved our main goal. However, we now wish to reline the algorithm
IGG so that it produces a pair of parallel separating lines (LP, Lo) when it fails to
detect an intersection. We have preferred to present this procedure separately since
there are applications in which this additional information is not needed. Instead
of a complicated formal definition, Figure 5a best illustrates what we mean by a
pair of separating lines.
Recall that the algorithm IGG fails to detect an intersection in two cases:
(1) It falls into case 2 of the INTERSECT procedure (see Figure 4b). Since P
does not intersect Q, as is easily checked, AyBx must be a bounded quadrilateral,
and so, EH joins BX, BY, or FG joins AX, A Y. Assuming the former (without loss
of generality), we find that line(EH) is a separating line LQ. To compute Lp, we
observe that it passesthrough the vertex of P, which minimizes the distance to Lo.
This distance is a bimodal function of the vertices of P; therefore, Lp can be
determined in O(log p) time.
(2) Either L,, or L, (say Ly) is reduced to fewer than six vertices (n < 6). We say
that the intersection of line(pipi+,) with Q is positive, if it is not empty, and lies
entirely on the same side of pi as P;+~.If it is not empty and lies totally on the same
side of pi+1 as pi, it is called negative. It is clear that if P and Q do not intersect,
any intersection of line(pipi+l) with Q (called Qi) is positive, negative, or empty.
The algorithm proceeds in stages,each consisting of the reduction of one or both
polygonal lines L,,, L,.. Let vI = pk; at any stage, we show that, if v2 = PI, then, for
each u between k and I - 1, the intersection Q1,is either empty or positive. Starting
with the obvious observation that initially v1 and v2 are consecutive around P
(, = k + 1) and, therefore, that the fact is true at the first stage, we prove the
assertion by induction on the number of stages.Clearly, the only stagesof interest
are those that reduce L,. from (v, , . . . , v,) to (vi, Vi, . . . , v, ). As before, let v1be p,4.
and v2 be pl, and let vi be ~1,. Using the induction hypothesis, it suffices to show
that Q1,is empty or positive for each u between I and h - 1. Assume that one of
them is negative. Then the intersection must occur in the triangle v1Gvi: A trivial
 10 B.CHAZELLEAND D.P.DoBKIN

FIG. 6. Intersecting polygonal lines.

C

examination of case 3 shows this to be impossible. Cases 2 and 4 are ruled out by
assumption. As to cases 1 and 5, the presence of Q,, in the triangle v1Gvi implies a
nonempty intersection between L,. and L,,., which is excluded.
Let us now come back to the first stage where L, has fewer than six vertices. Let
pi be the vertex y and pj the vertex v,-~. We have just shown that Q;-, is empty or
positive. Similarly, a symmetric reasoning would show that Qj is empty or negative.
It follows that, if some Q/; among Q;-I , . . . , Qj (note that there are at most four of
them to consider) are empty, Lp can be set to Qk (see Figure 5a). Otherwise, there
exists a pair (Qk-, , Qk) with Qk+ positive and Q,+negative (see Figure 5b for the
case k = I- 1). Observing that the angles (pkq, , pkq,) are bimodal for I= 1, . . . , q
(here we measure angles counterclockwise with values between -180 and + 180
degrees),we can find the vertex x (respectively, v) of Q that minimizes (respectively,
maximizes) that angle in O(log q) time. A simple argument shows that Lp may be
set to the line passing through pk and perpendicular to the bisector of (pkx, pky).
The line LQ is then obtained by minimizing the distance to P as we did earlier (1).
We can conclude:
THEOREM 4. An intersection betweentwo convexpolygons with p and q vertices,
respectively,can be detected in O(log(p + q)) time. When the polygons intersect, a
common point is returned, and a pair of parallel separating lines otherwise.
Although the previous algorithm can decide whether P and Q intersect, it is
unable to tell whether one polygon lies strictly inside the other, that is, whether or
not the boundaries of P and Q intersect. This is because the more general problem
of deciding whether two convex polygonal lines intersect requires linear time to be
solved. To see this, consider two polygons P and Q given in the complex plane
with vertices of P being the roots of z” - 1 = 0 and the vertices of Q the roots of

z” - (1,
2
1
2cos(27r/n)
n
1 = 0.

It can be easily verified that for any consecutive vertices a, b, c on the boundary
of Q, neither the edge ab nor bc intersects the boundary of P, whereas the segment
ac does (see Figure 6). So, any vertex of Q can be moved along a radius to create
an intersection without altering any of the n - 1 remaining vertices. Therefore,
any algorithm checking the intersection of the boundaries of P and Q has to look
at all the vertices of Q yielding the claimed lower bound. This is assuming, as
usual, that the points are given in an array, with no additional information except
the size of the polygons.
Intersection of Convex Objects in Two and Three Dimensions 11
D

FIG. 7. Preprocessingthree-dimen-
sional objects.

THEOREM 5. Testing the intersection of two convex polygonal lines requires

linear time.
Thus no general extensions of the algorithm in the plane are possible. However,
there are many casesto which the algorithm can be applied to give a description
of the region of intersection suflicient for its reconstruction.

3. Detecting Three-Dimensional Intersections

3.1 INTRODUCTION. Although detecting intersections becomes substantially
more difficult in three dimensions, the algorithms that we are about to describe
are based on principles similar to those used in the previous sections. We still use
Fibonacci searches to find extrema of bimodal functions and answer questions of
the form: Does object A lie entirely on one side of a given hyperplane? Similarly,
binary searchesare used to reduce the size of a problem by a constant factor.
Since all these techniques assume some random-access capabilities, we must give
our three-dimensional objects a special representation to provide these features.
From the observation that the surface of a convex polyhedron has the structure of
a planar graph, a standard method has been to represent convex polyhedra by a
description of the planar graph, along with the geometric location of the vertices
[ 111.Unfortunately, this representation does not meet all of our requirements, and
some preprocessing is needed. We represent each polyhedron as a set of parallel
convex polygons. These polygons, called preprocessing polygons, consist of a cross-
section of the polyhedron for each vertex. Each cross-section is the intersection of
the polyhedron with a plane parallel to the xy-plane passing through the vertex
(see Figure 7). This reduces a polyhedron P of p vertices to a set of p (or fewer)
convex polygons P,, . . . , P,, and p - 1 convex drums (we call a drum a convex
polyhedron with all the vertices lying on two parallel faces). Since each drum can
be tested for intersection with a convex polygon in logarithmic time, and projections
and intersections of those drums with a plane give convex objects, only O(log p)
preprocessing polygons need be considered for all of our purposes, which yields the
12 B. CHAZELLE AND D. P. DOBKIN

desired results. Before describing the preprocessing more precisely, we briefly

outline the various algorithms that we shall present.
(1) IHP-Intersection of a Polyhedron P with a Plane T. The projections of P
and T on a plane perpendicular to T and the preprocessing polygons form,
respectively, a convex polygon and a line that intersect if and only if P and T
intersect. We call IGL to test the intersection. This requires O(log p) steps, each
step involving O(log p) operations, since the accessto any vertex of the projected ‘,
polygon involves maximizing a linear combination of the x- or y-coordinates of a
preprocessing polygon, that is, maximizing a bimodal function.
(2) IHG-Intersection of a Polyhedron P with a Polygon R. If IHP fails to
detect an intersection between P and the plane T supporting R, we are finished.
Otherwise, T intersects a set of consecutive preprocessing polygons which we can
compute implicitly in O(log2p) time by a binary search whose basic step involves
intersecting a polygon with a line. Letting Q be the intersection of P and T, we first
test the intersection of R with the subpolygon of Q formed by the preprocessing
polygons determined earlier. If we fail, IGG will return a separating line adjacent
to Q. We can show that this line is adjacent to two consecutive drums of P, which
must intersect R if P does. We can test each drum for intersection in turn; thus the
whole algorithm runs in time O(log2N), ifNis the total number of vertices involved
in P and R.
(3) IHH-Intersection of Two Polyhedra P and Q. By intersecting P and Q
with a plane, a series of binary searches will reduce P successively to a drum, a
“slice,” and a pentahedron. Each step of the binary searches involves O(log2N)
operations, thus leading to an O(log3N)-time algorithm, with N the total number
of vertices in P and Q.
3.2 REPRESENTATION OF THREE-DIMENSIONAL OBJECTS. All of our polyhedra
are assumed to be in a standard representation as p (or fewer) polygonal cross-
sections. These cross-sections are created by setting a planar direction K and
intersecting the polyhedron with a plane in that direction passing through each of
its vertices (see Figure 7). The naive representation of this structure would require
O(p2) preprocessing time and O(p2) storage space in the worst case. In [7] a
representation using O(plog p) time and space is given. Accessing this data
structure, however, adds a factor of O(logp) to the running times of our algorithms.
We do not consider the details of this algorithm here and assume that questions of
the form:
What is the ith vertex of the jth cross-section?
may be answered in constant time. In a model where the accessesactually require
0( f( p)) operations, our upper bounds of 0( g( p)) are actually O(f( p)g( p)).
For the polyhedron P, we denote its cross-sections as PI, P2, . . . , Pp and let Pi,j
represent the part of the polyhedron between P; and Pj (inclusive). A key feature
of this representation is that we make no assumption about the preprocessing
direction. Therefore, the representation (in terms of PI, P2, . . . , P,,) is invariant
under scaling, rotation, or translation. Furthermore, when we consider the inter-
section of two preprocessed polyhedra, we need not assume that their polygonal
cross-sections lie in parallel planes. Since it is almost the case that each vertex of
P; is adjacent to a unique vertex of Pi+, , we nearly have a one-to-one correspond-
ence between P; and P,,, , and these two polygons almost fully describe the drum
Pi.i+, . Unfortunately, the vertices of Pi that are also vertices of P may be adjacent
Intersection of Convex Objects in Two and Three Dimensions 13

FIG. 8. The algorithm IHP.

to several vertices of Pi+, , and to remedy this discrepancy, we add dummy vertices
and dummy edgesof length 0. More precisely, let Xi,j be the jth vertex of Pi and let
el, . . . , ek be the lateral (i.e., joining Pi and Pi+,) edges of Pi,i+, emanating from
Xi,j, given in clockwise order around Pi+, (whichever order on Pi+, can be called
clockwise, as long as this is done consistently with all the cross-sections). In general
k = 1. If, however, k > 1, we conceptually duplicate Xi,j into k vertices yi , . . . , yk,
all of which have the same geometric location as Xi,j. Each y,,, however, is made
incident to exactly one edge e,,.
Iterating on this process for all vertices of Pi and all preprocessing polygons, we
rename the vertices thus obtained for each Pi,i+, , xl,, xl2 , . . . in clockwise order.
Similarly, we consider all the lateral edgesof P;,i-1 emanating from xi,j and duplicate
Xi,j accordingly. We thus defme a refinement of Pi with respect to the drum Pi-l,i,
renaming all the vertices of Pi, XC,, xi.2, . . . . Note that there is a one-to-one
correspondence between {xc,, xT2, . . .) and (x;+,J, xi+~, . . .), and all the pre-
processing can be done in O(p2) time.
3.3 INTERSECTION OF A PLANE WITH A POLYHEDRON (IHP). Let P be a convex
polyhedron with p vertices pl, p2, . . . and let T denote the plane under considera-
tion. Let K be a plane containing a (nondegenerate) preprocessing polygon. If K
and Tare parallel, then we can find which drum the plane T intersects by binary
search and, in the affirmative, intersect T with any edge of the drum nonparallel
to K and output an intersection point. So, let us assume in the following that the
intersection K n T is a line 1. Let M be a plane normal to 1; P and T intersect if
and only if their projections on M intersect (see Figure 8).
14 B.CHAZELLEAND D.P.DOBKIN

Let a; (respectively, b;) be the vertex of Pi with minimum (respectively, maxi-

mum) coordinate in the direction K fl M. In general, a; and bj are unique, although
there may be two of them if Pi has an edge parallel to the l-axis. In any case, the
orthogonal projection of ai (respectively, b;) on the M-plane, denoted a,! (respec-
tively, b,f) is unique. We first show that the polygon Q = a; . . . uib; - - - b; is
convex (see Figure 8).
LEMMA 6. The polygon Q is convex.
PROOF. We show that none of the angles (bLbL+,, b;bL-,) is reflex. Let B be
the intersection of the segment bkV1bk+,, with the plane P;,*supporting Pk. Since P
is convex, B lies on Pk; therefore its K fl M-coordinate cannot be greater than the
K n M-coordinate of bk. The projection of B on A4 being also the intersection of
b;-, b;,, with Pf, it follows that the angle (b;b;+, , bibi-,) is no greater than 180
degrees. We have the same result with the vertices a;, and it is easy to conclude
that Q is convex. Cl
This leads to
LEMMA 7. Let L be the intersection of T with M. Then P and T intersect if and
only ifQ and L intersect.
PROOF. If P and T intersect, we distinguish between two cases:
( 1) T intersects some Pi. Then the intersection of Pi and T is a line segment parallel
to 1,and its projection on M is a point that lies on the segment a,!bl. It follows
that Q and L intersect.
(2) If T does not intersect any Pi, it lies strictly between two consecutive
preprocessing polygons P; and P;+,; thus L intersects .~,!a;+,, that is,
intersects Q.
Conversely, if L intersects Q, it must intersect one of its edges. Its endpoints are
the projections on A4 of two vertices u and v on the boundary of P, and it is clear
that T must intersect the segment UV,that is, intersect P. Note that u and v are not
necessarily vertices of P. Cl
From the previous results, we can easily derive the algorithm IHP.
Algorithm IHP
If P and T do not intersect, the algorithm returns NO; otherwise, it returns (YES,
A), where A is a point of the intersection.
Lemma 7 shows that we can test the intersection of P with T by applying the
IGL algorithm to Q and L. We have an implicit description of Q, since we have
random acessto any of its vertices in O(log p) time. This is due to the fact that the
A4 fl K-coordinates of the vertices of any preprocessing polygon form a bimodal
function since the polygon is convex. Therefore, any a; or bi can be obtained in
O(log p) time, from which a,! and bJ are computed in constant time. If Q and L
do not intersect, IHP will return NO, else IGL provides, in O(log p) time, an edge
of Q intersecting L, say b,fbi’,, . Since knowing b j and b,f+,implies that bi and bi+l
have already been computed, we can immediately determine the intersection A of
T with the segment bibi+, and return (YES, A). Note that in this case, the segment
bibi+, always intersects T. Since the algorithm IGL runs in logarithmic time and
each basic step requires @log p) operations, we can conclude:
THEOREM 8. The intersection of a plane with a preprocessedconvexpolyhedron
of p verticescan be detectedin O(log2p) operations.
Intersection of Convex Objects in Two and Three Dimensions 15

FIG. 9. Intersection of a polyhedron and

a polygon.

will
w,
(R)
v “i
W

(0)
wf

FIG. 10. The two casesof intersection of Q and R.

3.4 INTERSECTION OF A POLYGONWITH A POLYHEDRON (IHG). We start with

an analysis of the problem, concentrating only on the most difficult points. Let P
be a preprocessed convex polyhedron of p vertices and R a convex polygon of q
vertices. Call Q the intersection of P with the plane T supporting R (see Figure 9).
By first calling upon IHP, we can check whether Q is empty. Assume that this is
not the case. It is equivalent to test the intersection of P and R or Q and R.
Although Q is not readily available, the preprocessing of P permits us to compute
an implicit description of it. We first observe that from the convexity of P, T
intersects a set (possibly empty) of consecutive Pi, say, P,, . . . , P,,, (I I m). Let
w;, w,! be the endpoints of the intersection of T and Pi, and Wdenote the polygon
w; . . . whw, . . . WI(see Figure 10). Since W is a subpolygon of Q (i.e., W lies
inside Q and all its vertices lie on the boundary of Q), it is easy to see that the
convexity of Q implies the convexity of W. If U, v are two consecutive vertices of
W in clockwise order, we define QU,,to be the convex polygon (outside of W)
delimited by the edge uv and the boundary of Q (see Figure 11).
The following result shows how to reduce our main problem to two easier
subproblems.
LEMMA 9. If Q and Ware not empty, P and R intersect ifand only if either of
the following conditions is satisfied:
( 1) W and R intersect.
(2) Let L be a separating line of W and R passing through a vertex a of W, and let
b, c be the vertices of Wadjacent to a (b = c if W’ is reduced to a line segment).
Then R intersects Qb,” or QU.c(see Figure 10).
PROOF. It suffices to observe that when R intersects Q but not W, the only parts
of Q that L does not separate from R are Qh.uand Qo,c.The remainder of the proof
is straightforward. Cl
16 B. CHAZELLE AND D. P. DOBKIN

FIG. 11. The polygons Q, W, Q “,“.

0)

Case 1 being easy to handle, let us turn to the other case. We wish to compute
an implicit description of Q,,.Uand QU,cin order to test these polygons for inter-
section with R. We describe the method for Q,,,rr,the other case being similar. Call
41, - *. , q/; the vertices of Qh,U,that is, the vertices of Q lying between b and a. Note
that ql, . . . , qk are the intersections of the plane T with consecutive lateral edges
of some drum Pi.;+, , say, et, . . . , ek. Since all the edges el, . . . , ek must pass
through consecutive vertices of Pi, x1, . . . , xk, it suffices to determine x1 and & to
have an implicit description of Qh,U.In order to have a one-to-one correspondence
between the xi and the e;, we must consider Pi with its vertices of the form
x;,. ) XT,,
. . . . . We distinguish between two cases:
(1) The segment ab is parallel to the preprocessing polygons (horizontal); it is
then the top or bottom edge of W, say, the top edge (without loss of generality).
Consider the three-dimensional strip S of Pi,;+, formed by ail its lateral faces. The
intersection of T with this strip is a continuous broken line D running from Pi to
Pi without intersecting Pi+, (see Figure 12a). Therefore any path from the portion
of the boundary of Pi between a and b to Pi+, must intersect D. It follows that
XI,..., xk are exactly all the vertices of Pi between a and b. To decide whether it
is between a and b or b and a in clockwise order around Pi, we simply observe that
on one part of the boundary all the lateral edgesintersect T, whereas none does on
the other. Thus, testing any lateral edge for intersection with T will resolve the
ambiguity in constant time.
(2) The segment ab is not a horizontal edge of W. Then Pi,/+, now designates
the drum lying between a and b. The intersection of T with the strip S consists of
two broken lines, one of which runs from a to b (see Figure 12b). Let x~,x~~+~
(respectively, y,,y,.+,) be the edge of Pi (respectively, Pi+l), given in, clockwise order,
which contains a (respectively, b). Note that these edges will have already been
computed when a and b are obtained. Since we wish to accessthe edges of Pi,i+,
from the vertices of Pip it is important to have a one-to-one correspondence between
the vertices of Pi and Pi+ 1; therefore, we consider the polygon Pi (respectively, Pi+!)
with its vertices xt,, XT*, . . . (respectively, xi+,,, , xi+,,~, . . .). Let xl be the vertex
of Pi in correspondence with yy, that is, the vertex lying with y, on the same lateral
edge of Pi,i+, . It is clear that if the lateral edge of Pi,/+, passing through x~,intersects
T, then ql , . . . , q/; are exactly the intersections of T with the lateral edgesemanating
from XI+~, x1+2, . . . , x,, (see Figure 12b). Otherwise, if the lateral edge emanating
from x,,+~ intersects T, the vertices ql, . . . , qk of Q are determined by the set of
vertices x~,+~,. . . , xl (see Figure 12~). Finally, if neither of the above casesarises,
no lateral edge intersects T between a and b, and Qb,rris reduced to the single edge
ub; therefore no testing is necessary.
Putting all these results together and handling the remaining cases is straight-
forward. We can now set out the algorithm IHG, whose correctness is established
by these results.
Intersection of Convex Objects in Two and Three Dimensions 17

(4

b+
Iryv
I
%+I Xl
(b)

FIG. 12. Computing Qb,..

Algorithm IHG
The algorithm takes a convex polygon R and a preprocessed convex polyhedron P
as input and returns NO if P and R do not intersect or (YES, A) if they do, with A
a point of the intersection.
Step 1. Test the intersection of P with the plane T supporting R by calling
upon IHP. If P and T do not intersect, return NO; else the algorithm IHP will
provide a point I of the intersection, as well as the preprocessing plane Py, such
that I lies in the drum Pi,;+,. If IGL indicates that T intersects neither Pi nor Pi+*,
go to Step 2; else go to Step 3.
Step 2. “T lies strictly betweenPi and Pi+,.” Q being the intersection of T and
P, the vertices of Q are exactly the intersections of T with all the lateral edges of
Pi.i+I. Therefore Pi gives an implicit description of Q, and it is possible to test the
intersection of Q and R with the IGG algorithm, returning NO if it is empty or
(YES, A) if it is not, where A is a point of the intersection returned by IGG.
Step 3. “T intersects Pi or Pi+,.” Without loss of generality, assume that
T intersects Pi. Since T intersects a set of consecutive preprocessing polygons
PI, ***, P,,,, we can determine P, and P,,, through a binary search by testing the
intersection of Pk and T with the IGL algorithm. This gives an implicit description
of IV, from which we can test the intersection of R and W with IGG. Note that to
accessa vertex of IV, we must compute the intersection of T with some prepro-
cessing polygon, using the IGL algorithm. If the intersection of R and W is not
empty, IGG will provide a common point A, and we can return (YES, A).
Otherwise, IGG will return a separating line L of W and R passing through IV,
thus providing the vertices a, b, c.
18 B.-- CHAZELLE AND D. P. DOBKIN

@ii+ (O’,
(0)
(Ob,c)
c
(0)

(4
FIG. 13. Computing a pair of separating
lines for Q and R.

(b)

Step 4. “If R intersects P, it intersects Qb.Uor QaSc.” Apply the procedure

described above for QhTrrand Qa.=successively, and test these polygons for inter-
section of R (RX), returning NO or a common point accordingly.
Before analyzing the running time of IHG, we wish to extend the algorithm
slightly so that it returns a pair of parallel separating-lines when P and R do not
intersect, that is, a pair of separating lines for Q and R. When IHG returns NO in
step 1, no such pair can be defined, but the plane T is itself a separating hyperplane
and is sufficient information for our purposes. In all of the other cases,a noninter-
section of P and R is detected after testing both Qb,aand Qa,cfor intersection has
failed. Instead of testing these two polygons successively, we can simply use the
implicit description of Qb,aand Qcl.<to test the intersection of Qb.‘.with R (Qb,Cis
defined as the union of Qh.“, QU,c,and the triangle abc). If no intersection is found,
the algorithm IGG will return a pair of separating lines (D, D ‘) for Qhqcand R. Let
v be the vertex of Ql,.clying on the separating line D.
If v is distinct from b and c, (D, D ‘) is also a pair of separating lines for Q and
R since Q is convex, and fits our purposes (see Figure 13a).
If v is b or c (say 6, without loss of generality), D may intersect Q outside of v,
thus not separate Q and R. In that case, let d be the vertex of Qb,cadjacent to b
and distinct from c. We can show that the line F passing through bd separates Q
from R. Then computing a line F’ adjacent to R and parallel to F so that (F, F’)
forms a pair of separating lines will take only @log q) time, as described earlier.
We now prove our claim.
Recall that the algorithm has already computed a line L that is adjacent to the
vertex a of Q and that separates Wand R. Call L+, D+, F+ the halfspaces delimited
by L, D, F, respectively, that do not contain the vertex c (see Figure 13b). Since
Intersection of Convex Objects in Two and Three Dimensions 19
both L and D separate R from the triangle abc, R lies in the intersection of L+ and
D+, denoted LD. Since Qb,Cdoes not intersect the interior of D+, the line F cannot
intersect LD; therefore R is completely inside F+. This implies that Fis a separating
line of R and Q, which proves our claim.
Step 1 calls upon IHP and IGL and thus requires O(log’p) operations. Step 2
is a simple application of IGG and takes O(log(p + q)) time. Step 3 involves a
binary search on the preprocessing polygons with a call on IGL at each step,
which amounts to O(log2p) time. Testing the intersection of IV and R takes
O((log p)log(p + q)) time, since each vertex of W is obtained by intersecting T
with some Pk (IGL), which takes O(logp) time. Finally, step 4 performs a
constant-time case analysis and then call on IGG, which requires O(log(p + q))
operations. We can finally state our main result.
THEOREM 10. The intersection of a preprocessed convex polyhedron of p vertices
with a convex polygon of q vertices can be detected in O((logp)log(p + q))
operations, that is, in O(log2N) time, where N is the total number of vertices in
both objects.
3.5 INTERSECTION OF A LINE WITH A POLYHEDRON (IHL). We now consider
the problem of detecting an intersection between an infinite line (or a line segment)
L and a convex polyhedron ofp vertices preprocessedas usual. We can contemplate
a solution that is a straightforward application of the method described in the
previous section.
We first test the intersection of P with any plane T supporting the line L, using
IHP. If we fail to detect an intersection, we obviously return NO. Otherwise, we
define the polygon Q as usual (i.e., the intersection of P and T), and we compute
an implicit description of its subpolygon W formed by the preprocessing polygons
of P. Next, we test the intersection of Wand L (IGL), and in the event of a failure
compute a separating line adjacent to W and derive the polygons Qh,aand &,.
Finally, we test these polygons for intersection with L, calling upon IGL.
Note that in the caseof an intersection, we can compute the segment S of L that
lies in P in O(logp) time. There are essentially two casesto consider:
(1) If an intersection is detected while intersecting Qb,a(respectively, Qa,C)with L,
then S is exactly the intersection of Qh.a(respectively, Qa,r) with L, and we can
compute it in O(logp) time (IGL) (see Figure 14a).
(2) If Wand L intersect, then IGL will provide the two edges of W that intersect
L, say, ab and a’b’ (see Figure 14b). It is clear that, if A (respectively B) is the
point on the boundary of QU,h,(respectively, QO,h,)that intersects L and does
not lie on ab (respectively, a’b’), then S is the segment AB. To obtain this
segment, we need to compute implicit descriptions of QO,hand Qa,h, and
intersect L with these two polygons (see Algorithm IHG for details of the
procedure). Finally, IGL will provide A and B in O(logp) time.
The total running time of the algorithm is clearly O(log2p), and we conclude:
THEOREM 11. We can compute (explicitly) the intersection of a preprocessed
polyhedron ofp vertices with an in.nite line or a line segment in O(log2p) operations.
3.6 INTERSECTION OF Two POLYHEDRA (IHH). We now turn to the problem
of detecting the intersection of two convex polyhedra P and Q of p and q vertices,
respectively. We assume that both polyhedra have been preprocessed, yet we do
not require that the preprocessing planes of P should be parallel to those of Q (see
Figure 15a). Thus we can maintain a coordinate-free environment. If either P or
 20 B.CHAZELLE AND D. P. DOBKIN

FIG. 14. The algorithm IHL.

(4

(b)

Q is rotated, no new preprocessing will be necessary. The algorithm IHH proceeds

by a series of binary searches, all very similar in nature, and reduces P to a drum,
a “slice,” and a pentahedron successively. For the clarity of exposition, we start
our analysis of the problem with some preliminary results related to lines and
planes of support. We redefine a line of support of P more precisely as a line having
exactly one point or one segment (not necessarily an edge) in common with the
boundary of P. Similarly, a plane of support of P is defined as a plane with exactly
one edge or one face in common with the boundary of P.
For later purposes, we need to extend the preprocessing of P slightly. We require
the existence, for each vertex of P, of an array listing the edges incident to it in
clockwise order. This additional information is readily obtained once the polyhed-
ron has been preprocessed. We begin with a preliminary result:
LEMMA 12. If L is a line of support of P and one edge of P that intersects L is
known, then it is possible to determine a plane of support of P containing L in
O(logp) operations.
PROOF. Call v the intersection of L with that edge e of P known to intersect L.
We distinguish between two cases:
(1) If v is not a vertex of P (check whether v is an endpoint of e), then the plane
containing both e and L is a plane of support of P (see Figure 16a).
(2) If v is a vertex of P, then the plane passing through e and L may unfortunately
intersect the interior of P, and further analysis is needed (see Figure 16b). Let
a,..., ek be a list of the edges of P adjacent to v, in clockwise order. Recall
that the preprocessing of P ensures random accessto these edges. Let Ui be the
plane containing both L and ei. The planes Vi (i = 1, . . . , k) such that L and
e; are not collinear form a bimodal angular sequence. The extrema are valid
planes of support and can be computed in O(log p) time. Cl
Intersection of Convex Objects in Two and Three Dimensions 21

(4

(L,) (La)
Y

2
< s
X

R=P
1

a TP TO

04

(4
FIG. 15. Reducing the size of P in IHH.

We now turn to the crux of the algorithm IHH. Let us assume that P and Q
intersect but neither contains the other. Let T be a plane intersecting P and Q but
not their intersection. Call R (respectively, S) the intersection of T and P (respec-
tively, Q), and let (LP, Lo) be a pair of parallel separating lines for R and S,
respectively. If Tp (respectively, To) is a plane of support of P (respectively, Q)
passing through Lp (respectively, Lo), observing the relative position of Tp and To
will indicate on which side of T the intersection of P and Q lies. Indeed, since P
and Q intersect but R and S do not, the intersection of P and Q lies entirely in one
of the halfspaces delimited by T (see Figure 15). To determine which, we first
observe that the intersection of P and Q must lie in the intersection H of the
halfspace delimited by Tp, which contains P with the halfspace delimited by To
containing Q. Since Lp and Lo are parallel, H lies totally on one side of T, and the
intersection L of Tp and To (which must exist since H is nonempty) may be
computed in constant time and indicates which side of T contains the intersection
of P and Q. Note that L is an infinite line parallel to T (see Figure 1Sb, c). The
portion of P that does not lie on the same side of T as L can be rejected since it
22 B. CHAZELLE AND D. P. DOBKIN

FIG. 16. Computing a plane of support of P. (4

(b)

cannot intersect with Q. This gives us a means of reducing the size of the problem,
so carrying out this process in a binary search fashion will guarantee efficiency. We
now proceed to describe the algorithm.
(1) Let P, be the middle preprocessing polygon of P (1 = [p/21). The first step
consists of reducing P to PI.1or P,,p. To do so, we test the intersection of Q with
the preprocessing plane Py passing through PI, using the IHP algorithm. If it fails
to detect an intersection, Q lies entirely on one side of PT, which can be determined
in constant time. We then iterate on this process with PI., or P,.,,whichever lies on
the same side of PT as Q. If PT and Q intersect, we call upon IHG to test the
intersection of Q with the polygon PI, returning (YES, A) if IHG finds a point A
of the intersection or providing a pair of separating lines (Lp, Lo) (see Figure 15b).
Since in this last case, IHG will also indicate edges of P (respectively, Q) that
intersect Lp (respectively, Lo), we can apply the result of Lemma 12 and compute
a plane of support of P passing through L p, which we denote Tp. A similar
computation will give a plane of support of Q passing through La, Tp (see Figure
15~). Finally, our discussion above shows how locating the intersection of Lp and
La with respect to PT permits us to substitute PI., or P,,l, for P accordingly. Of
course, if Tp and TQ do not intersect (i.e., are parallel), neither do P and Q, so we
can terminate.
Iterating on this process will either produce a point of the intersection or reduce
P to a convex drum Pi,;+,. Note that we may have i + 1 = 1 or i = p, in which case
the algorithm can return NO since P and Q do not then intersect.
(2) It now remains to test the intersection of Q and Pi,i+l . Let XI, . . . , xk be the
vertices of Pi in clockwise order. We choose a lateral edge e of Pi-i+,, say, an edge
passing through xl, and consider the plane Tj containing both Xj and the edge e.
For any u, v, 1 < u < v 5 k, we define TU,yas the portion of Pi,i+, comprised
between T,, and TV(i.e., the portion that contains the edge x,,xu+J. We have seen
 ---1
Intersection of Convex Objects in Two and Three Dimensions 23

(pi,i4

-1 1 x2 m@
e

Xl
S'1
---

‘k
--- C-
0

b
Ti

/-

(0)

FIG. 17. Reducing the cap Pi.i+l in IHH.

‘j+l

Tj

(4

e/-=4Jjjyl pFJjj/G

xI xj+ I xj+l

(b) (4
FIG. 18. The cap Pi.,+, after reduction.

in the description of the IHG algorithm how to compute an implicit description of

the polygon 5“ formed by the intersection of Pi.;+, and q (see Figure 17). Recall
that this involves computing the points a and b, as well as the lateral edgesof Z’i,i+,
that intersect Tj. Having an implicit description of Sj, we can apply the procedure
described earlier, first using IHP with arguments c, Q and then IHG with
arguments Sj, Q. This will either return a point of the intersection of S’ and Q, in
which case we are done, or produce a pair of planes of support for P and Q,
respectively, containing two parallel lines separating Sj and Q.
Once again, locating the intersection of these two planes will permit us to
substitute T2.j or Tj.k for P accordingly. We can perform a binary search on j in the
interval [2, k]. If the algorithm does not terminate before, it will reduce Piqi+, to
the convex polyhedron c;..j+l for some j (see Figure 18a).
(3) Tj,j+I has one face lying on Pi (the triangle XI XjXj+l) and a parallel face on
Pi+, , denoted F. Unfortunately, Figure 18a illustrates only the simplest case since
F is not necessarily a triangle. However, we can remedy this discrepancy easily.
24 B. CHAZELLE AND D. P. DOBKIN

a’

YI

Fi ,Tj

FIG. 19. Reducing the slice A in IHH.

Let yl be the endpoint of the edge e that lies on Pi+, (e = xl y,) and let yl, . . . , y,,
denote the vertices of Pi+, in clockwise order. F is a convex polygon yl, y, yl, . . . ,
y,,, y ‘, yl (see Figure 18b, c). We can determine y and y ’ in O(logp) time by
intersecting P;+l with Tj and Tj+l, using the IGL algorithm (which actually must
have been done already). If y and y ’ do not lie on the same edge of Pi+, , we carry
on the previous binary search on the planes T;, . . . , TA, where T,f is now the
plane containing e and yi. If the algorithm does not return, it will reduce P to a
convex polyhedron B with two parallel faces on Pi and Pi+, , denoted xl& and
y, a ‘b’, respectively, both of which are triangles (seeFigure 19). Let Fj (respectively,
Fj+I) be the face of B lying on q (respectively, T,,,). In addition to ab and a’b’, B
may contain other edgesA, . . . ,1; intersecting both Fj and Fj+l . These edgeslie on
consecutive lateral edges of Pi,i+, , say, e, , . . . , e, in clockwise order. Our next task
is to compute an implicit description of this set of edges, that is, to determine el
and e,.
The following fact will permit us to compute el and e, in constant time. We can
always assume that a, b (respectively, a’, b’) occur in clockwise order in a traversal
of the boundary Of Pi (respectively, Pi+,). Let g be a lateral edge Of Pi,i+, intersecting
both Fj and Fj+l , with gl (respectively, gz) the endpoint of g lying on Pi (respectively,
Pi+,). Note that by construction of B, any edge intersecting Fj intersects Fj+l as
well, and vice-versa. We can observe that if g, occurs between xl and a (respectively,
b and x,) in clockwise order, g2 must lie between b’ and yl (respectively, yl and a’)
in clockwise order. Without loss of generality, suppose that g, occurs between xl
and a. Let xz, be the vertex of Pi such that a lies on the edge xc,x;t,+, . Since lateral
edges can only intersect at their endpoints, the lateral edge of Pi.i+l adjacent to xc,
(which is uniquely defined by the preprocessing) also intersects both 4 and e+, .
This shows that lateral edges of P.;, ,+, intersect Fj and Fj+l if and only if the lateral
edge adjacent to XT, or xz,,, intersects Tj. This gives us a convenient way to
determine el and ek’in constant time with the technique already used in the IHG
algorithm. Namely, let x~+,,~,x~+~,,,+~ be the edge of Pi+, that intersects Fj and let
x& be the vertex of P, in one-to-one correspondence with ~i+,,~,+~.It is then clear
that el is the edge x;~,,x~+,.~,+,and e, the lateral edge adjacent to x:,. All the
lateral edgesbetween el and e, also intersect Fj and Fj+l , that is, the edges adjacent
to x&n:m, &+1, - * *, xl,. Recall that the one-to-one correspondence between
LG 3 $2, - * .) and L&I, x7+1+. . .) established in the preprocessing allows random
accessto the lateral edges of P;J+,.
(4) Having an implicit description of el, . . . , e,, we can define uj as the plane
containing xl and e, and apply the procedure of (2) on this set of planes (see Figure
19). This will either return a point of the intersection of P, Q, and Uj, or produce
Intersection of Convex Objects in Two and Three Dimensions 25
a pair of planes of support from which we can decide which side of Uj contains the
intersection of P and Q, if it exists. Note that the intersection of B and Uj is simply
a triangle that we can compute in constant time. If the algorithm does not return,
it will eventually reduce P to a pentahedron K lying between Tj, Tj+j, two
consecutive triangles Ul, U,+,, and a lateral face of Pi,;+, . In fact, k can be
“degenerate” and have fewer than five faces.
(5) Finally, we have to test the intersection of K and Q. To do so, we can test
each face of K successively, using the IHG algorithm. If we fail to detect an
intersection, we determine whether Q lies entirely inside or outside of K by testing
the inclusion of any point of Q in K, which can be done in constant time.
We now give’s more formal outline of Algorithm IHH, which will also serve as
a summary.
Algorithm IHH
The input consists of two preprocessed convex polyhedra P and Q, and the output
is NO if P and Q do not intersect or (YES, A) if they do, where A is a point of the
intersection.
Step 1
I=I;m=p
while I< m - 1
begin
i = L(f + m)/2J
if Pt does not intersectQ [IHP]
then
if q, lies above P:
thenl=i
else m = i
else
if Pi intersectsQ [IHG]
then return (YES, A = point returned by IHG)
“IHG providesa pair of separatinglines from which Tp and TQ are computed”
if Tp and TQdo not intersect
then return (NO)
if T, and TQ intersectaboveP:
then I = i
else m = i
end
i=l
Step 2. “P is reduced to a convex drum Pi,/+,.” Let e be a lateral edge of Pi,i+,
and 7; the plane containing e and the vertex Xj of Pi. Apply step 1 with respect to
the planes Tj. Finally setj to 1.
Step 3. “P is reduced to a convex polyhedron lJ,j+l .” If the face of q,j+i lying
on Py+, is not a triangle, apply step 2 with respect to the planes T;, . . . , TL
(defined in the previous discussion).
Step 4. “P is reduced to a polyhedron B bordered by two triangles, subpolygons
of Pi and Pi+,.” Apply the procedure of step 1 with respect to the planes Uj
passing through XI and ej, where xl is a vertex of Pi and ej is the jth lateral
edge of B.
Step 5. “P is reduced to a polyhedron K with at most five faces.” Check
whether q1 lies inside K. If affirmative, return (YES, 4,). Otherwise, apply the IHG
26 B. CHAZELLE AND D. P. DOBKIN

algorithm to test whether Q intersects any of the faces of K. If this is the case,
return (YES, A), where A is a point of the intersection; else return (NO).
We can now state our main result
THEOREM 13. The intersection of two preprocessed convex polyhedra of p and q
vertices, respectively, can be detected in O((logp)(logq)log(p + q)) operations, that
is, O(log3N) time, where N is the total number of vertices in P and Q.
PROOF. At this stage, we simply have to evaluate the execution time of the
algorithm. We review its various phases and derive its complexity:
(1) This stage involves O(logp) applications of IHP (log2q), IHG ((logq)log(p +
q)), and the algorithm of Lemma 12 (logpq).
(2) We can obtain an implicit description of sj in constant time, once the inter-
section of Tj with Pi and Pi+, has been computed (logp). The remainder of this
step is similar to the previous one.
(3) This stage has the same complexity as (2), since computing an implicit
description of y,, . . . , y,,, takes constant time.
(4) This stage is similar to (2).
(5) This is essentially a repeated application of IHG to Q and a triangle or a
quadrilateral (log2q). Cl

4. Conclusions
We have described a complete set of algorithms for detecting intersections in two
and three dimensions. In all cases,we have avoided issues of efficiency beyond the
asymptotic level. Although the algorithm for computing planar intersections is
asymptotically optimal [ 161, we believe that a more sophisticated treatment of
bimodal functions may improve its running time. Also, a more refined caseanalysis
might permit us to reduce not only one of the polygons by half, but always both
of them.
In three dimensions, aside from speeding up the preprocessing [7], we believe
that algorithm IHH would benefit from a more symmetric treatment of the two
polyhedra (along the lines of the algorithm IGG, for example). There also remains
the question of proving lower bounds, since none of these algorithms has been
shown to be optimal.
In all cases, we believe that improvements can be best discovered by imple-
menting the algorithms and observing their behavior on real problems. There is
also the possibility of using the methods presented here as the basis of fast
probabilistic algorithms [ 141or algorithms efficient on the average [3].
Note: While this paper was being refereed, some of the results were improved.
In particular, terms of O(log3n) in Section 3.6 have been reduced to O(log2n) and
terms of O(log2n) in Sections 3.3 and 3.5 have been reduced to O(logn) in [5].

ACKNOWLEDGMENT. We wish to thank Garret Swart for pointing out an omission

in algorithm IGG in an earlier draft.
REFERENCES
1. AHO, A. V., HOPCROFT, J. E., AND ULLMAN, J. D. The Design and Analysis of Computer
Algorithms. Addison-Wesley, Reading, Mass., 1974.
2. BENTLEY. J. L., AND OTTMANN, T. Algorithms for reporting and counting geometric intersections.
IEEE Trans. Comput. C-28 (Sept. 1979), 643-647.
Intersection of Convex Objects in Two and Three Dimensions 27

3. BENTLEY, J. L., AND SHAMOS, M. I. Divide and conquer for linear expected time. Irzj Proc. Lett.
7(1978), 87-91.
4. BENTLEY, J. L., HAKEN, D., AND HON, R. Fast geometric algorithms for VLSI tasks. In Proceedings
of the Computational Conference, 1981, pp. 88-92.
5. DOBKIN, D. P., AND KIRKPATRICK, D. Cl. Fast detection of polyhedral intersection. Theor. Comput.
Sci. 27(1983), 241-253.
6. D~BKIN, D. P., AND LITTON, R. L. Multidimensional searching problems. SIAM J. Comput. 5, 2
(June 1976), 181-186.
7. DOBKIN, D. P., AND MUNRO, J. I. Efficient uses of the past. In Proceedings ofthe 21st Annual
IEEE Symposium on Foundations of Computer Science (Syracuse, N.Y., Oct.). IEEE, New York,
1980, pp. 200-206.
8. DOBKIN, D. P., AND TOMLIN, D. Cartographic modelling techniques in environmental planning:
An efficient system design. Unpublished manuscript.
9. KIEFER, J. Sequential minimax search for a maximum. Proc. Am. Math. SOC.4 (1953), 502-506.
IO. KNUTH, D. E. The Art of Computer Programming: Fundamental Algorithms. Addison-Wesley,
Reading, Mass., 1968.
1I. MULLER, D. E., AND PREPARATA, F. P. Finding the intersection of two convex polyhedra. Theor.
Comput. Sci. 7 (1978), 2 17-236.
12. NEWMAN, W., AND SPROULL, R. Principles of Interactive Computer Graphics. 2nd Ed. McGraw-
Hill, New York, 1979.
13. NIEVERGELT, J., AND PREPARATA, F. P. Plane-sweeping algorithms for intersecting geometric
figures. Commun. ACM 25, 10 (1982), 739-747.
14. RABIN, M. Probabilistic algorithms. In Algorithms and Complexity: New Directions and Recent
Results, J. Traub, Ed. Academic Press,Orlando, Fla., 1976.
15. SHAMOS, M. I. Geometric complexity. In Proceedings of the 7th Annual ACM Symposium on
Theory of Computing (Albuquerque, N.M., May). ACM, New York, 1975, pp. 224-233.
16. SHAMOS, M. I. Computational geometry. Ph.D. dissertation, Yale Univ., New Haven, Conn.,
May, 1978.
17. SHAMOS, M. I., AND HOEY, D. Geometric intersection problems. In Proceedings ofthe f7th Annual
IEEE Symposium on Foundations of Computer Science (Houston, Tex., Ott). IEEE, New York,
1976, pp. 208-215.

RECEIVED OCTOBER 1983; REVISED JANUARY 1986; ACCEPTED JUNE 1986

Journal of the Association for Computing Machinery, Vol. 34, No. I, January 1987.