Lecture 21: Applications of Arrangements

(Tuesday, Apr 10, 2000)

Reading: Chapter 8 in the 4M's. Some of this material is not covered in the book. Applications of Arrangements and Duality: The computational and mathematical tools that we have developed with geometric duality and arrangements allow a large number of problems to be solved. Here are some examples. Unless otherwise stated, all these problems can be solved in O(n2) time and O(n2) space by constructing a line arrangement, or in O(n2) time and O(n) space through topological plane sweep.

General position test: Given a set of n points in the plane, determine whether any three are collinear.

Minimum area triangle: Given a set of n points in the plane, determine the minimum area triangle whose vertices are selected from these points.

Minimum k corridor: Given a set of n points, and an integer k, determine the narrowest pair of parallel lines that enclose at least k points of the set. The distance between the lines can be defined either as the vertical distance between the lines or the perpendicular distance between the lines.

Visibility graph: Given line segments in the plane, we say that two points are visible if the interior of the line segment joining them intersects none of the segments. Given a set of n non intersecting line segments, compute the visibility graph, whose vertices are the endpoints of the segments, and whose edges a pairs of visible endpoints.

Maximum stabbing line: Given a set of n line segments in the plane, determine whether the line that stabs (intersects) the maximum number of these line segments.

Hidden surface removal: Given a set of n non intersecting polygons in 3 space, imagine projecting these polygon onto a plane (either orthogonally or using perspective). Determine which portions of the polygons are visible from the viewpoint under this projection. Note that in the worst case, the complexity of the final visible scene may be as high as O(n2), so this is asymptotically optimal. However, since such complex scenes rarely occur in practice, this algorithm is really only of theoretical interest.

Ham Sandwich Cut: Given n red points and m blue points, find a single line that simul taneously bisects these point sets. It is a famous fact from mathematics (called the Ham Sandwich Theorem) that such a line always exists. If the point sets are separated by a line, then this can be done in time: O(n +m), space: O(n + m).

Ok, so let us consider a few such problems in more detail.

Sorting all angular sequences: Here is a natural application of duality and arrangements that turns out to be important for the problem of computing visibility graphs. Consider a set of n points in the plane. For each point p in this set we want to perform an angular sweep, say in counterclockwise order, visiting the other n - 1 points of the set. For each point, it is possible to compute the angles between this point and the remaining n - 1 points and then sort these angles. This would take O(n log n) time per point, and O(n2log n) time overall. With arrangements we can speed this up to O(n2) total time, getting rid of the extra O(log n) factor.

Here is how. Recall the point line dual transformation.

A point p = (px, py) and a line l : (y = ax - b) in the primal plane are mapped through to a dual point l* and dual line p* as follows:

l* = (a, b)
p* : (b = pxa - py):

Recall that the a coordinate in the dual plane corresponds to the slope of a line in the primal plane. Suppose that p is the point that we want to sort around, and let p1, p2, ... , pn be the points in final angular order about p.

Figure 69: Arrangements and angular sequences.

Consider the arrangement defined by the dual lines p*i. How is this order revealed in the arrangement? Consider the dual line p* , and its intersection points with each of the dual lines p*i. These form a sequence of vertices in the arrangement along p*. Consider this sequence ordered from left to right. It would be nice if this order were the desired circular order, but this is not quite correct. The a coordinate of each of these vertices in the dual arrangement is the slope of some line of the form p --> pi. Thus, the sequence in which the vertices appear on the line is a slope ordering of the points about pi, not an angular ordering.

However, given this slope ordering, we can simply test which primal points lie to the left of p (that is, have a smaller x coordinate in the primal plane), and separate them from the points that lie to the right of p (having a larger x coordinate). We partition the vertices into two sorted sequences, and then an concatenate these two sequences, with the points on the right side first, and the points on the left side later. The resulting is an angular sequence starting with the angle -90 degrees and proceeding up to +270 degrees. Thus, once the arrangement has been constructed, we can reconstruct each of the angular orderings in O(n) time, for a total of O(n2) time.

Narrowest 3 corridor: As mentioned above, in this problem we are given a set P of n points in the plane, and an integer k, 1 <= k <= n, and we wish to determine the narrowest pair of parallel lines that enclose at least k points of the set. In this case we will define the vertical distance between the lines as the distance to minimize. (It is easy, but a bit tricky to adapt the algorithm for perpendicular distance.)

To simplify the presentation, we assume that k = 3. The generalization to general k is an exercise. We will assume that no three points of P are collinear. This will allow us to assume that the narrowest corridor contains exactly three points and has width strictly greater than zero. (Observe that if three points were collinear, then they would correspond to three lines that intersect at a common vertex in the arrangement, which could be tested as we build the arrangement.) We will also assume that no two points have the same x coordinate. The dual transformation that we consider cannot represent vertical lines, but this assumption will imply that the solution is not a vertical line. We could fix this by using homogeneous coordinates, but we will not worry about it now.

If we dualize the points of P , then in dual space we have a set L of n lines, {l1, l2, ... ,ln}. The slope of each dual line is the x coordinate of the corresponding point of P, and its y intercept is the negation of the point's y coordinate.

A narrowest 3 corridor in the primal plane consists of two parallel lines la and lb in primal space. Their duals l*a and l*b are dual points, which have the same x coordinates (since the lines are parallel), and the vertical distance between these points, is the difference in the y intercepts of the two primal lines. Thus the vertical width of the corridor, is the vertical length of the line segment.

In the primal plane, there are exactly three points lying in the corridor, that is, there are three points that are both above lb and below la. Thus, by the order reversing property, in the dual plane, there are three dual lines that pass both below point l* b and above l* a . Combining all these observations it follows that the dual formulation of the narrowest 3 corridor problem is the following:

Shortest vertical 3 stabber: Given an arrangement of n lines, determine the shortest vertical segment that stabs three lines of the arrangement.

Figure 70: Narrowest 3 corridor: primal and dual form.

It is easy to show (by a simple perturbation argument) that the shortest vertical 3 stabber may be assumed to have one of its endpoints on a vertex of the arrangement, implying that the other endpoint lies on the line of the arrangement lying immediately above or below this vertex. (In the primal plane the significance is that we can assume that the minimum 3 corridor one of the lines passes through 2 of the points, and the other passes through a third point, and there are no points within the interior of the corridor. This is shown in the figure below. We can compute the minimum 3 stabber in an arrangement, by a simple plane sweep of the arrangement (using a vertical sweep line). Whenever we encounter a vertex of the arrangement, we consider the distance to the edge of the arrangement lying immediately above this vertex and the edge lying immediately below. We can solve this problem by topological plane sweep in O(n2) time and O(n) space.

We can also solve this by constructing the arrangement and computing the (vertical) trapezoidal map. Each trapezoidal edge will correspond to a corridor. The shortest such edge is the final answer. This leads to an O(n2) time and space solution.

Figure 71: Narrowest corridor and trapezoidal maps.

Maximum Discrepancy: Next we consider a problem derived from computer graphics and sampling. Suppose that we are given a collection of n points S lying in a unit square U = [0, 1]2. We want to use these points for random sampling purposes. In particular, the property that we would like these points to have is that for any halfplane h, we would like the size of the fraction of points of P that lie within h should be roughly equal to the area of intersection of h with U . That is, if we define U(h) to be the area of h intersection U , and US(h) = |S intersection h|/ S, then we would like U(h) about US(h) for all h. This property is important when point sets are used for things like sampling and Monte Carlo integration.

Figure 72: Discrepancy of a point set.

To this end, we define the discrepancy of S with respect to a halfplane h to be

DS(h) = |U(h) - US(h)|.

For example, in the figure, the area of h intersect U is U(h) = 0.625, and there are 7 out of 13 points in h, thus US(h) = 7/13 = 0.538. Thus the discrepancy of h is |0.625 - 0:538| = 0:087. Define the halfplane discrepancy of S to be the maximum (or more properly the supremum, or least upper bound) of this quantity over all halfplanes:

DS= sup h DS(h)

Since there are an uncountably infinite number of halfplanes, it is important to derive some sort of finiteness criterion on the set of halfplanes that might produce the greatest discrepancy.

Lemma: Let h denote the halfplane that generates the maximum discrepancy with respect to S, and let l denote the line that bounds h. Then either (i) l passes through at least two points of S, or (ii) l passes through one point of S, and this point is the midpoint of the line segment l intersect U .

Remark: If a line passes through one or more points of S, then should this point be included in US(h)? For the purposes of computing the maximum discrepancy, the answer is to either include or omit the point, whichever will generate the larger discrepancy. The justification is that it is possible to perturb h infinitesimally so that it includes none or all of these points without altering U(h).

Proof: If l does not pass through any point of S, then (depending on which is larger U(h) or US(h)) we can move the line up or down without changing US(h) and increasing or decreasing U(h) to increase their difference. If l passes through a point p in S, but is not the midpoint of the line segment l intersect U , then we can rotate this line about p and hence increase or decrease U(h) without altering US(h), to increase their difference. Since for each point p in S there are only a constant number of lines l (at most two, I think) through this point such that p is the midpoint of l intersect U , it follows that there are at most O(n) lines of type (i) above, and hence the discrepancy of all of these lines can be tested in O(n2) time.

To compute the discrepancies of the other lines, we can dualize the problem. In the primal plane, a line l that passes through two points pi, pj in S, is mapped in the dual plane to a point l* at which the lines p*i and p*j intersect. This is just a vertex in the arrangement of the dual lines for S. So, if we have computed the arrangement, then all we need to do is to visit each vertex and compute the discrepancy for the corresponding primal line.

It is easy to see that the area l intersect U of each corresponding line in the primal plane can be computed in O(1) time. So, all that is needed is to compute the number of points of S lying below each such line. In the dual plane, the corresponds to determining the number of dual lines that lie below or above each vertex in the arrangement. If we know the number of dual lines that lie strictly above each vertex in the arrangement, then it is trivial to compute the number of lines that lie below by subtraction.

We define a point to be at level k, Lk, in an arrangement if there are at most k - 1 lines above this point and at most n - k lines below this point. The k-th level of an arrangement is an x monotone polygonal curve, as shown below. For example, the upper envelope of the lines is level 1 of the arrangement, and the lower envelope is level n of the arrangement. Note that a vertex of the arrangement can be on multiple levels. (Also note that our definition of level is exactly one greater than our text's definition.)

We claim that it is an easy matter to compute the level of each vertex of the arrangement (e.g. by plane sweep). The initial levels at x = -inf are determined by the slope order of the lines. As the plane sweep proceeds, the index of a line in the sweep line status is its level. Thus, by using topological plane sweep, in O(n2) time we can compute the minimumand maximum level number of each vertex in the arrangement. From the order reversing property, for each vertex of the dual arrangement, the minimum level number minus 1 indicates the number of primal points that lie strictly below the corresponding primal line and the maximum level number is the number of dual points that lie on or below this line. Thus, given the level numbers and the fact that areas can be computed in O(1) time, we can compute the discrepancy in O(n2) time and O(n) space, through topological plane sweep.

Figure 73: Levels in an arrangement.