Figure 32: Halfplane intersection.
How many sides can bound the intersection of n halfplanes in the worst case?
Observe that by convexity, each of the halfplanes can appear only once
as a side, and hence the maximum number of sides is n. How fast can we
compute the intersection of halfspaces? As with the convex hull
problem, it can be shown through a suitable reduction from sorting
that the problem has a lower bound of O( n log n).
Who cares about this problem?
Our books discusses a rather fanciful application in the area of
casting. More realistically, halfplane intersection and halfspace
intersection in higher dimensions are used as a method for generating
convex shape approximations. In computer graphics for example, a
bounding box is often used to approximate a complex multi sided
polyhedral shape. If the bounding box is not visible from a given
viewpoint then the object within it is certainly not visible. Testing
the visibility of a 6 sided bounding box is much easier than a multi
sided nonconvex polyhedron, and so this can be used as a filter for a
more costly test. A bounding box is just the intersection of 6 axis
aligned halfspace in 3 space. If more accurate, but still convex
approximations are desired, then we may compute the intersection of a
larger number of tight bounding halfspaces, in various orientations,
as the final approximation.
Solving the halfspace intersection problem in higher dimensions is
quite a bit more challenging than in the plane. For example, just
storing the output as a cyclic sequence of bounding planes is not
sufficient. In general some sort of adjacency structure (ala DCEL's)
is needed. We will discuss two algorithms for the halfplane
intersection problem. The first is given in the text. For the other,
we will consider somewhat simpler problem of computing something
called the lower envelope of a set of lines, and show that it is
closely related to the convex hull problem.
Divide and Conquer Algorithm:
We begin by sketching a divide and conquer algorithm for computing the
intersection of halfplanes. The basic approach is very simple:
(1) If n = 1, then just return this halfplane as the answer.
(2) Split the n halfplanes of H into subsets H(1) and H(2) of sizes
floor(n/2), ceil(n/2), respectively.
(3) Compute the intersection of H(1) and H(2) , each by calling this
procedure recursively. Let C(1) and C(2) be the results.
(4) Intersect the convex polygons C(1) and C(2) (which might be
unbounded) into a single convex polygon C, and return C.
The running time of the resulting algorithm is most easily described
using a recurrence, that is, a recursively defined equation. If we
ignore constant factors, and assume for simplicity that n is a power
of 2, then the running time can be described as:
T (n) =
1 if n = 1,
2T (n/2) + S(n) if n > 1,
where S(n) is the time required to compute the intersection of two
convex polygons whose total complexity is n. If we can show that
S(n) = O(n), then by standard results in recurrences it will follow that
the overall running time T (n) is O(n log n). (See Cormen, Leiserson,
and Rivest, for a proof.)
Intersecting Two Convex Polygons: The only nontrivial part of the
process is implementing an algorithm that intersects two convex
polygons, C(1) and C(2) , into a single convex polygon. Note that
these are somewhat special convex polygons because they may be empty
or unbounded.
We know that it is possible to compute the intersection of line
segments in O((n + I) log n) time, where I is the number of
intersecting pairs. Two convex polygons cannot intersect in more than
I = O(n) pairs. (This follows from the observation that each edge of
one polygon can intersect at most two edges of the other polygon by
convexity.) This would given O(n log n) algorithm for computing the
intersection and an O(n (log n)^2) solution for T (n), which is not as
good as we would like.
However, there is a very simple plane sweep approach to solving this
problem. Suppose that we perform a left to right plane sweep to
compute the intersection. Observe that by convexity the sweep line
intersects each C(i) in at most two points. Therefore, there are at
most four points in the sweep line status at any time. Thus we do not
need a fancy dictionary for storing the sweep line status. All the
operations can be performed in constant time. Furthermore, you do not
need a priority queue for the events. The only two events that are
important are the leftmost points of C(1) and C(2) (note that they might
stretch back to -Inf). To determine the next event point, you just
need to check the four current edges for intersections, and check the
four edges for their next endpoints. Since there are only a constant
number of possibilities, each event can be handled in O(1) time.
Figure 33: Convex polygon intersection.
Lower Envelopes and Duality: Next we consider a slight variant of this
problem, to demonstrate some connections with convex hulls. These
connections are very important to an understanding of computational
geometry, and we see more about them in the future. These connections
have to do with a concept called point line duality. In a nutshell
there is a remarkable similarity between how points interact with each
other an how lines interact with each other. Sometimes it is possible
to take a problem involving points and map it to an equivalent problem
involving lines, and vice versa. In the process, new insights to the
problem may become apparent.
The problem to consider is called the lower envelope problem, and it
is a special case of the halfplane intersection problem. We are given
a set of n lines L = {e(1),e(2), .. e(n)}, where e(i) is of the form
y = a(i) x - b(i) .
Think of these lines as defining n halfplanes, y < a(i) x - b(i), each
lying below one of the lines. The lower envelope of L is the boundary
of the intersection of these half planes. (There is also an upper
envelope, formed by considering the intersection of the halfplanes
lying above the lines.)
Figure 34: Lower and upper envelopes.
The lower envelope problem is a restriction of the halfplane
intersection problem, but it an interesting restriction. Notice that
any halfplane intersection problem that does not involve any vertical
lines can be rephrased as the intersection of two envelopes, a lower
envelope defined by the lower halfplanes and an upper envelope defined
by the upward halfplanes.
I will show that solving the lower envelope problem is essentially
equivalent to solving the upper convex hull problem. In fact, they are
so equivalent that exactly the same algorithm will solve both
problems, without changing even a single character of code. All that
changes is the way in which you view the two problems.
Duality: Let us begin by considering lines in the plane. Each line can
be represented in a number of ways, but for now, let us assume the
representation y = ax - b, for some scalar values a and b. We
cannot represent vertical lines in this way, and for now we will just
ignore them. Later in the semester we will fix this up.
Why did we subtract b? We'll see later that this is just a
convenience. Therefore, in order to describe a line in the plane, you
need only give its two coordinates (a, b). In some sense, lines in
the plane can be thought of as points in a new plane in which the
coordinate axes are labeled (a, b), rather than (x, y). Thus the line
y = 7x - 4 corresponds to the point (7, 4) in this new plane. Each
point in this new plane of ``lines'' corresponds to a nonvertical line
in the original plane. We will call the original (x; y) plane the
primal plane and the new (a; b) plane the dual plane.
What is the equation of a line in the dual plane? Since the coordinate
system uses a and b, we might write a line in a symmetrical form, for
example b = 3a - 5, where the values 3 and 5 could be replaced by any
scalar values. Consider a particular point p = (p(x), p(y)) in the
primal plane, and consider the set of all nonvertical lines passing
through this point. Any such line must satisfy the equation:
p(y) = a p(x) - b.
The images of all these lines in the dual plane is a set of points:
L = {(a,b) | p(y) = a p(x) - b}
= {(a,b) | b = p(x) a - p(y)}
Notice that this set is just the set of points that lie on a line in
the dual (a; b) plane. (And this is why we negated b.) Thus, not only
do lines in the primal plane map to points in the dual plane, but
there is a sense in which a point in the primal plane corresponds to a
line in the dual plane. To make this all more formal, we can define a
function that maps points in the primal plane to lines in the dual
plane, and lines in the primal plane to points in the dual plane. We
denote it using an asterisk *. Thus, given point p = (p(x),p(y)) and
line e : (y = ax - b) in the primal plane we define *e and *p
to be a point and line respectively in the dual plane defined by:
*e = (a, b)
*p = {b = p(x) a - p(y) }
We can define the same mapping from dual to primal as well. Duality
has a number of interesting properties, each of which is easy to
verify by substituting the definition and a little algebra.
Self Inverse: *(*(p)) = p.
Order reversing: Point p lies above/on/below line e in the primal
plane if and only if line *p passes below/on/above point *e in the
dual plane, respectively.
Intersection preserving: Lines e1 and e2 intersect at point p if and
only if line *p \Lambda passes through points *e1, *e2 in the dual
plane.
Collinearity/Coincidence: Three points are collinear in the primal
plane if and only if their dual lines intersect in a common point.
Figure 35: Dual transformation.
To finish things up, we need to make the connection between the upper
convex hull of a set of points and the lower envelope of a set of
lines.
Lemma: Let P be a set of points in the plane. The counterclockwise
order of the points along the upper (lower) convex hull of P , is
equal to the left to right order of the sequence of lines on the lower
(upper) envelope of the dual *P.
Proof: We will prove the result just for the upper hull and lower
envelope, since the other case is symmetrical. For simplicity, let us
assume that no three points are collinear. Observe that a necessary
and sufficient condition for a pair of points p(i) p(j) to form an
edge on the upper convex hull is that the line e(ij) that passes
through both of these points has every other point in P strictly
beneath it.
Consider the dual lines *p(i) and *p(j). A necessary and sufficient
condition that these lines are adjacent on the lower envelope is that
the dual point at which they meet, *e(ij) lies beneath all of
the other dual lines in *P . The order reversing condition of
duality assures us that the primal condition occurs if and only if the
dual condition occurs. Therefore, the sequence of edges on the upper
convex hull is identical to the sequence of vertices along the lower
envelope. As we move counterclockwise along the upper hull observe
that the slopes of the edges increase monotonically. Since the slope
of a line in the primal plane is the a coordinate of the dual point,
it follows that as we move counterclockwise along the upper hull, we
visit the lower envelope from left to right.
One rather cryptical feature of this proof is that, although the upper
and lower hulls appear to be connected, the upper and lower envelopes
of a set of lines appears to consist of two disconnected sets. To make
sense of this, we should interpret the primal and dual planes from the
perspective of projective geometry, and think of the rightmost line of
the lower envelope as ``wrapping around'' to the leftmost line of the
upper envelope, and vice versa. We will discuss projective geometry
later in the semester.
Another interesting question is that of orientation. We know the the
orientation of three points is positive if the points have a
counterclockwise orientation. What does it mean for three lines to
have a positive orientation? (The definition of line orientation is
exactly the same, in terms of a determinant of the coefficients of the
lines.)
Next Class:
Linear Programming, which is maximize the value of a linear function,
within the region defined by a set of half-planes.
Read Chapter 4.
This course is modeled on the Computational Geometry Course taught by Dave Mount, at the University of Maryland. These notes are modifications of his Lecture Notes, which are copyrighted as follows: Copyright, David M. Mount, 2000, Dept. of Computer Science, University of Maryland, College Park, MD, 20742. These lecture notes were prepared by David Mount for the course CMSC 754, Computational Geometry, at the University of Maryland, College Park. Permission to use, copy, modify, and distribute these notes for educational purposes and without fee is hereby granted, provided that this copyright notice appear in all copies.