(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(n^{2}) time and O(n^{2}) space by
constructing a line arrangement, or in O(n^{2}) 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(n^{2}), 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(n^{2}log n)
time overall. With arrangements we can speed this up to O(n^{2}) total
time, getting rid of the extra O(log n) factor.

Here is how. Recall the point line dual transformation.

A point p = (p_{x}, p_{y}) 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 = p_{x}a - p_{y}):

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 p_{1}, p_{2}, ... ,
p_{n} 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 -->
p_{i}. Thus, the sequence in which the vertices appear on the
line is a slope ordering of the points about p_{i}, 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(n^{2}) 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, {l_{1}, l_{2}, ... ,l_{n}}. 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 l_{a} and l_{b} 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
l_{b} and below l_{a}. 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(n^{2}) 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(n^{2}) 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 U_{S}(h) = |S intersection h|/ S, then we
would like U(h) about U_{S}(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

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 U_{S}(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:

D_{S}= sup h D_{S}(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 U_{S}(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 U_{S}(h)) we can move the line up or
down without changing U_{S}(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 U_{S}(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(n^{2}) 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
p_{i}, p_{j} 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, L_{k}, 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(n^{2})
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(n^{2}) time and O(n) space, through topological plane
sweep.

Figure 73: Levels in an arrangement.