A General Randomized Incremental Reconstruction Procedure

Kenneth L. Clarkson Bell Laboratories, Lucent Technologies Murray Hill, New Jersey 07974

                 clarkson@research.bell-labs.com
              http://cm.bell-labs.com/who/clarkson/

July 30, 1997

Abstract

The technique of randomized incremental construction allows a variety of geometric structures to be built quickly. This note shows that once such a structure is built, it is possible to store the geometric input data for it so that the structure can be built again by a randomized algorithm even more quickly. Except for the randomization, this generalizes the technique of Snoeyink and van Kreveld that applies to planar problems.

1 Introduction

Given a set S of n points in the plane, Snoeyink and van Kreveld have shown that the points can be stored so that their Delaunay triangulation can be found in O(n) time.[8] Snoeyink and van Kreveld have generalized this technique to a variety of problems, but restricted to geometric structures that are planar graphs. This note generalizes the technique even more, to the setting of randomized incremental construction.

For concreteness, the ideas will first be described in the setting of Delaunay triangulation, and then in general.

2 Delaunay triangulations

Given a set S of n sites (points) in the plane, their Delaunay triangulation D(S) can be built by maintaining a Delaunay triangulation D(R) of a random subset R ⊂ S, adding sites one by one to R and updating the triangulation. The expected number of triangles generated site is added is O(1), and a simple auxiliary data structure allows the addition of each site to be done in O(log r) expected time, where r is the number of sites in R. (Such an algorithm was proposed by Boisannat et al.[2] the first analysis of a similar, offline, algorithm was given in Clarkson and Shor[4]. This readily shows that the expected overall time of an online algorithm is O(n log n),[5] and subsequent analyses showed that the expected cost of adding site r +1 is O(log r).[6, 1, 3, 7].) The dominant cost of inserting a site p into R (and so into the triangulation) is the search problem of finding the set of triangles of D(R) that conflict with p, in the sense that p is inside the circumcircle of such a triangle. Such triangles will not be in D(R ∪ {p}). By walking over the triangulation from a triangle that conflicts with p, it is easy to find the remaining triangles that conflict with p, and so the search problem reduces to that of finding a single triangle that conflicts with p.

Many methods for solving the search problem involve finding all triangles, over the history of the triangulation, that conflict with p; the expected number of such triangles is O(log r). A simple data structure allows the work for finding these triangles to be constant per triangle.[1, 3]

Snoeyink and van Kreveld have shown that it is possible to order the points in such a way that when the Delaunay triangulation is rebuilt, the search problem is easy to solve, requiring constant time per point. Their approach involves finding large sets of independent vertices of the triangulation, each with small degree, following Kirkpatrick.

We give an alternative approach, as follows. Let R_{i} denote the random subset R after i sites have been inserted, so that the sites can be numbered in a permutation π as x_{1} … x_{n} with R_{i} = {x_{1} … x_{i}}. It will be convenient to define R_{i} as equal to S, for i ≥ n.

Consider the sites as being inserted in “batches” of exponentially increasing size: let M_{1} ≡ R_{1}, and for j = 1 … ⌈lg n⌉, let

M_{j} ≡ R_{2^{j}} \ R_{2^{j−1}}.

We will build a different permutation π′ of the sites x′_{1} … x′_{n} such that the corresponding sets R′_{i} ≡ {x′_{1} … x′_{i}} have the property that R′_{i} = R_{i} when i is a power of two; that is, the batch sets M_{j} are the same for either permutation.

By picking the permutation π′ properly, the sites within M_{j} will be ordered in a way that allows the search problem for M_{j} to be solved quickly, with respect to the Delaunay triangulation of R_{2^{j−1}}: that is, for each p ∈ M_{j}, the triangles in D(R_{2^{j−1}}) conflicting with p can be found quickly. The construction of D(R_{2^{j}}) then proceeds incrementally. The sites of M_{j} are added in random order, resulting in random subsets R′′_{i} for 2^{j−1} < i ≤ 2^{j}. Note that R′′_{i} = R′_{i} = R_{i} for i a power of 2. The searching problem is solved by finding all triangles that conflict with p, for such triangles that appear in one of the triangulations D(R′′_{i}), for 2^{j−1} < i ≤ 2^{j}. Theorem 1 below implies that the expected number of such triangles is O(1).

The “encoding” algorithm produces an ordering of M_{j}, as given in π′, by constructing an ordered list L of the sites in M_{j} in the following way. List the Delaunay triangles of D(R_{2^{j−1}}) in lexicographic order, where a triangle with vertices x′_{a}, x′_{b}, x′_{c} ∈ R′_{2^{j−1}} with a < b < c is given a sort key (a, b, c). (For our purposes, supporting halfspaces of R_{2^{j−1}} can be viewed as triangles with a vertex at infinity; this “vertex” can be numbered as site n + 1 for the sort keys.)

Walk through the list of triangles in order, and for each triangle, look at the sites of M_{j} with which it conflicts. If such a site has not yet been put into L, append it to the end of L.

The ordering of L gives the ordering of M_{j} for π′.

Using radix sort, the encoding can be found in time proportional to the number of triangle/site conflicts.

The “decoding,” or reconstruction, algorithm sorts the triangles of D(R_{2^{j−1}}) lexicographically, as in the encoding procedure, and walks simultaneously through that sorted list of triangles and through M_{j} in order of π′. Suppose a triangle T and a site p are currently under consideration. If they do not conflict, then no site after p conflicts with T, and the next triangle on the triangle list can be considered. If they do conflict, then the search problem has been solved for p, and next site in the permutation π′ can be considered for T.

Plainly the work done for reconstruction, as described so far, is proportional to the number of triangles plus the number of sites in M_{j}. It remains to show that the rest of the searching requires O(1) expected time for each site in M_{j}; this will be shown in the general setting.

The rest of the reconstruction procedure, for sites in M_{j}, is randomized incremental construction, as applied to a random ordering of the points of M_{j}. Note that the result is a randomized incremental construction procedure using a permutation π′′ that is random, but related to the random permutation π only in that the sets R′′_{i} and R_{i} agree when i is a power of two.

3 The general case

The general setting for the reconstruction algorithm is the same as for “randomized incremental construction,” for which the terminology and analysis of Clarkson et al. will be used.[3] The setting of general randomized incremental construction generalizes that of Delaunay triangulation, by generalizing from point sites to other geometric objects, and from Delaunay triangles to geometric regions determined by d or fewer objects, for some d. If a region is determined by some set of objects, those objects will to support it. The conflict between a Delaunay triangle and a site generalizes to some conflict relation between regions and objects. For a given set of objects S, the randomized incremental paradigm gives a way to construct F_{0}(S), which is the set of all regions determined by objects of S that do not conflict with any objects of S. The randomized incremental paradigm builds F_{0}(S) by maintaining F_{0}(R) as a random subset R of S is built up to S. The dominant cost is the searching problem, finding a region of F_{0}(R) with which a newly added object x conflicts.

This search problem can be solved in the randomized incremental paradigm by examining the history of the construction, examining all regions of

H_{r−1} ≡ ∪_{1≤i≤r−1}F_{0}(R_{i})

that conflict with x.

The procedure described in the last section, for Delaunay triangulations, can be generalized in a straightforward way to this setting. This implies a low cost for finding a member of F_{0}(R_{2^{j−1}}) with which a given object x ∈ M_{j} conflicts. In most cases, the remaining cost of search is proportional to the number of regions of

∪_{2^{j−1}≤i≤2^{j}}F_{0}(R_{i})

with which a random x ∈ M_{j} conflicts. The following theorem holds.

Theorem 1 Let z ≡ 2^{j−1}. Let σ = (x_{1} … x_{n}) be a random permutation , giving random subsets T_{i} ≡ {x_{1} … x_{i}}. For given j and r with z < r ≤ 2^{j}, the expected number of regions in

∪_{z<i<r}F_{0}(T_{i})

with which object x_{r} conflicts is no more than

\frac{d}{z + 1}f_{z+1} + ∑_{z<i≤r} \frac{d(d − 1)}{i(i − 1)}f_{i},

where f_{i} is the expected number of regions of F_{0}(T_{i}).

Proof. The proof can be readily adapted from the proof of Theorem 4 of [3]: in that proof, the history

H ≡ H(x_{1}, …, x_{r−1}) ≡ ∪_{1≤i<r}F_{0}(T_{i})

is compared with the history

H′ ≡ H(x_{r}, x_{1}, …, x_{r−1}) ≡ ∪_{1≤i<r}F_{0}({x_{r}} ∪ T_{i}),

the “alternate history” of the construction, where x_{r} is added first. Here we can change the comparison to that between H and

Ĥ ≡ H(x_{1}, …, x_{z}, x_{r}, x_{z+1}, …, x_{r−1}),

the alternate history where x_{r} is added at the beginning of M_{j}. We have

|H| + |Ĥ \ H| = |Ĥ| + |H \ Ĥ|,

where H \ Ĥ is the set of regions we want to count, those in H that conflict with x_{r} and appear in some F_{0}(T_{i}) for i > z. The set Ĥ \ H comprises regions supported by x_{r}, and appear after those in F_{0}(T_{z}). Hence the expected size E|H \ Ĥ| is bounded by

E|H| − E|Ĥ| + E|Ĥ \ H|.  (1)

The rest of the proof follows analogously to the proof of Theorem 4 of [3]. For completeness, we briefly complete the proof here. A region of Ĥ \H may be in F_{0}(T′_{z}) and supported by x_{r}, where T′_{i} ≡ T_{i} ∪ {x_{r}}. The expected number of such regions is df_{z+1}/(z + 1), since the probability that x_{r}, a random member of T′_{z}, supports a given region of F_{0}(T′_{z}) is d/(z + 1).

A remaining region of Ĥ \ H first appears at some i, for z < i < r; that is, such a region is in F_{0}(T′_{i}) but not in F_{0}(T′_{i−1}) or F_{0}(T_{i}). Hence it is supported by x_{r} and by x_{i}. Since x_{r} and x_{i} are random elements of T′_{i}, the probability that they support a given member of F_{0}(T′_{i}) is at most d(d − 1)/(i + 1)i: for a given member of F_{0}(R′_{i}), there are at most \binom{d}{2} pairs from R′_{i} that support it, and \binom{i+1}{2} pairs altogether. Hence the expected size

E|Ĥ \ H| ≤ \frac{d}{z + 1}f_{z+1} + ∑_{z<i<r} \frac{d(d − 1)}{i(i + 1)}E|F_{0}(T′_{i})|

= \frac{d}{z + 1}f_{z+1} + ∑_{z<i<r} \frac{d(d − 1)}{i(i + 1)}f_{i+1}.  (2)

To bound E|H \ Ĥ| using (1), it remains to bound the expected size E|H|. This is ∑_{m<r} df_{m}/m, as in Theorem 3[3]: count each region of H by its first appearance, at which, for some m, the region is in F_{0}(T_{m}) but not in F_{0}(T_{m−1}); this implies that x_{m} supports the region. The probability that a random member of T_{m} supports the region is d/m, and therefore the expected number of new regions when x_{m} is added is df_{m}/m. A similar bound holds for E|Ĥ|, and so E|H| − E|Ĥ| is −df_{r}/r.

Putting this bound with (1) and (2), theorem follows.

In the case of Delaunay triangulation, d = 3 and f_{i} = O(i), so the above implies that the search cost in reconstruction is expected O(1) per site.

References

[1] J.-D. Boissonnat, O. Devillers, R. Schott, M. Teillaud, and M. Yvinec. Applications of random sampling to on-line algorithms in computational geometry. Discrete Comput. Geom., 8:51–71, 1992.

[2] J.-D. Boissonnat and M. Teillaud. A hierarchical representation of objects: The Delaunay tree. In Proc. 2nd Annu. ACM Sympos. Comput. Geom., pages 260–268, 1986.

[3] K. L. Clarkson, K. Mehlhorn, and R. Seidel. Four results on randomized incremental constructions. Comput. Geom. Theory Appl., 3(4):185–212, 1993. http://cm.bell-labs.com/who/clarkson/4res.html.

[4] K. L. Clarkson and P. W. Shor. Applications of random sampling in computational geometry, II. Discrete Comput. Geom., 4:387–421, 1989. http://cm.bell-labs.com/who/clarkson/rs2m.html.

[5] L. J. Guibas, D. E. Knuth, and M. Sharir. Randomized incremental construction of Delaunay and Voronoi diagrams. Algorithmica, 7:381–413, 1992.

[6] K. Mulmuley. Randomized multidimensional search trees: Further results in dynamic sampling. In Proc. 32nd Annu. IEEE Sympos. Found. Comput. Sci., pages 216–227, 1991.

[7] K. Mulmuley. Computational Geometry: An Introduction Through Randomized Algorithms. Prentice Hall, Englewood Cliffs, NJ, 1994.

[8] J. Snoeyink and M. van Kreveld. Good orders for incremental (re)construction. In Proc. 13th Annu. ACM Sympos. Comput. Geom., pages 400–405, 1997.