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.