Lecture 14: Trapezoidal Decompositions

Reading: Chapter 6 of the 4M's.

More Point Location: Earlier we presented Kirkpatrick's point location
algorithm. Today we will consider another asymptotically optimal
algorithm for point location, which is considerably more
practical. One interesting element of this algorithm is that it is
randomized, and in particular, it is based on a randomized incremental
construction. We will show that the size, preprocessing time, and
query time are O(n), O(n log n) and O(log n), respectively, in the
expected case. Here the expectation is independent of the choice of
the polygonal subdivision or the query point. It depends only on the
order in which the objects are inserted.

Trapezoidal Map:

The algorithm is based on a construction called a trapezoidal map
(which also goes under many other names in the computational geometry
literature). Although we normally think of the input to a point
location algorithm as being a planar subdivision, we will define the
algorithm under the assumption that the input is just a collection of
line segments S = {s1, s2, ... ,sn},
such that these line segments do not intersect except possibly at
their endpoints. To construct a trapezoidal map, imagine shooting a
bullet vertically upwards and downwards from each vertex in the
polygonal subdivision until it hits another segment of S.

(For simplicity, we will assume that there are no vertical segments in
the initial subdivision and no two segments have the same x
coordinate. Both of these are easy to handle with an appropriate
symbolic perturbation.) The resulting ``bullet paths'', together with
the initial line segments define the trapezoidal map. To avoid
infinite bullet paths at the top and bottom of the subdivision, we may
assume that the initial subdivision is contained entirely within a
large bounding rectangle. An example is shown in the figure below.

Figure 51: Trapezoidal map.
First observe that all the faces of the resulting subdivision are trapezoids with vertical sides. The left or right side might degenerate to a line segment of length zero, implying that the resulting trapezoid degenerates to a triangle. We claim that the process of converting an arbitrary polygonal subdivision into a trapezoidal decomposition increases its size by at most a constant factor. Actually this follows from the facts that we only increase the number of vertices by a constant factor and the graph is planar. But since constant factor expansions in space are significant, it is a good idea to work this through carefully. We assume that the final trapezoidal map will be given as a subdivision of the plane, represented, say, using a DCEL. Claim: Given a polygonal subdivision with n segments, the resulting trapezoidal map has at most 6n + 4 vertices and 3n + 1 trapezoids. Proof: To prove the bound on the number of vertices, observe that each vertex shoots two bullet paths, each of which will result in the creation of a new vertex. Thus each original vertex gives rise to three vertices in the final map. Since each segment has two vertices, this implies at most 6n vertices. To bound the number of trapezoids, observe that for each trapezoid in the final map, its left side (and its right as well) is bounded by a vertex of the original polygonal subdivision. The left endpoint of each line segment can serve as the left bounding vertex for two trapezoids (one above the line segment and the other below) and the right endpoint of a line segment can serve as the left bounding vertex for one trapezoid. Thus each segment of the original subdivision gives rise to at most three trapezoids, for a total of 3n trapezoids. The last trapezoid is the one bounded by the left side of the bounding box. An important fact to observe about each trapezoid is that it is defined (that is, its existence is determined) by exactly four entities from the original subdivision: a segment on top, a segment on the bottom, a bounding vertex on the left, and a bounding vertex on the right. This simple observation will play an important role in the analysis. Trapezoidal decompositions, like triangulations, are interesting data structures in their own right. It is another example of the idea of converting a complex shape into a disjoint collection of simpler objects. The fact that the sides are vertical makes trapezoids simpler than arbitrary quadrilaterals. Finally observe that the trapezoidal decomposition is a refinement of the original polygonal subdivision, and so once we know which face of the trapezoidal map a query point lies in, we will know which face of the original subdivision it lies in (either implicitly, or because we label each face of the trapezoidal map in this way). Construction: We could construct the trapezoidal map easily by plane sweep. (Hopefully, this is an easy exercise by this point, but think about how you would do it.) We will build the trapezoidal map by a randomized incremental algorithm, because the point location algorithm is based on this construction. (In fact, historically, this algorithm arose as a method for computing the trapezoidal decomposition of a collection of intersecting line segments, and the point location algorithm arose as an artifact that was needed in the construction.) The incremental algorithm starts with the initial bounding rectangle (that is, one trapezoid) and then we add the segments of the polygonal subdivision one by one in random order. As each segment is added, we update the trapezoidal map. Let Si denote the subset consisting of the first i (random) segments, and let Ti denote the resulting trapezoidal map. To perform the update this we need to know which trapezoid the left endpoint of the segment lies in. We will let this question go until later, since it will be answered by the point location algorithm itself. Then we trace the line segment from left to right, determining which trapezoids it intersects. Finally, we go back to these trapezoids and ``fix them up''. There are two things that are involved in fixing. First, the left and right endpoints of the new segment need to have bullets fired from them. Second, one of the earlier bullet paths might hit this line segment. When that happens the bullet path must be trimmed back. (We know which vertices are from the original subdivision vertices, so we know which side of the bullet path to trim.) The process is illustrated in the figure below.
Figure 52: Incremental update.
Observe that the structure of the trapezoidal decomposition does not depend on the order in which the segments are added. This observation will be important for the probabilistic analysis. The following is also important to the analysis. Claim: Ignoring the time spent to locate the left endpoint of an segment, the time that it takes to insert the ith segment and update the trapezoidal map is O(ki), where ki is the number of newly created trapezoids. Proof: Consider the insertion of the ith segment, and let K denote the number of bullet paths that this segment intersects. We need to shoot four bullets (two from each endpoint) and then trim each of the K bullet paths, for a total of K + 4 operations that need to be performed. If the new segment did not cross any of the bullet paths, then we would get exactly four new trapezoids. For each of the K bullet paths we cross, we add one more to the number of newly created trapezoids, for a total of K + 4. Thus, letting ki = K + 4 be the number of trapezoids created, the number of update operations is exactly ki. Each of these operations can be performed in O(1) time given any reasonable representation of the trapezoidal map (e.g. a DCEL). Analysis: We left one important detail out, namely, how we locate the trapezoid containing left endpoint of each new segment that we add. Let's ignore this for now. (We will see later that this is O(logn) time on average). We will show that the expected time to add each new segment is O(1). Since there are n insertions, this will lead to a total expected time complexity of O(n(1 + log n)) = O(n log n). We know that the size of the final trapezoidal map is O(n). It turns out that the total size of the point location data structure will actually be proportional to the number of new trapezoids that are created with each insertion. In the worst case, when we add the ith segment, it might cut through a large fraction of the existing O(i) trapezoids, and this would lead to a total size proportional to Sum(i = 1..n) i = n2 However, the magic of the incremental construction is that this does not happen. We will show that on average, each insertion results in only a constant number of trapezoids being created. (You might stop to think about this for a moment, because it is rather surprising at first. Clearly if the segments are short, then each segment might not intersect very many trapezoids. But what if all the segments are long? It seems as though it might be possible to construct a counterexample. Give it a try before you read this.) Lemma: Consider the randomized incremental construction of a trapezoidal map, and let ki denote the number of new trapezoids created when the ith segment is added. Then E[ki] = O(1), where the expectation is taken over all permutations of the segments. Proof: The analysis will be based on a backwards analysis. Let Ti denote the trapezoidal map after the insertion of the ith segment. Because we are averaging over all permutations, among the i segments that are present in Ti , each one has an equal probability 1/i of being the last one to have been added. For each of the segments s we want to count the number of trapezoids that would have been created, had s been the last segment to be added. Let's say that a trapezoid T depends on an segment s, if s would have caused T to be created, had s been added last. We want to count the number of trapezoids that depend on each segment, and then compute the average over all segments. If we let d(T,s) = 1 if segment s depends on T, and 0 otherwise, then the expected complexity is E[ki] = 1/i * sum (all segments s) (sum (all trapezoids T) d(T,s)) Some segments might have resulted in the creation of lots of trapezoids and other very few. How do we get a handle on this quantity? The trick is, rather than count the number of trapezoids that depend on each segment, we count the number segments that each trapezoid depends on. (The old combinatorial trick of reversing the order of summation.) In other words we want to compute: E[ki] = 1/i * sum (all traingles T) (sum (all segments s) d(T,s)) This is much easier to determine. In particular, each trapezoid is bounded by at most four sides (recall that degenerate trapezoids are possible). The top and bottom sides are each determined by a segment of Si, and clearly if either of these was the last to be added, then this trapezoid would have come into existence as a result. The left and right sides are each determined by a endpoint of a segment in Si, and clearly if either of these was the last to be added, then this trapezoid would have come into existence. Thus, each trapezoid is dependent on at most four segments, implying that sum (all segments s) d(T,s) <= 4. Since there are O(i) trapezoids E[ki] <= 1/i * sum (all traps T defined after i steps) 4 = 1/i * 4 * |all traps T defined after i steps| = 1/i * O (i) = O(1). Figure 53: Trapezoid segment dependencies.
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.