Four Results on Randomized Incremental Constructions^{∗}

Kenneth L. Clarkson^{†} Kurt Mehlhorn^{‡} Raimund Seidel^{§}

November 5, 1991 revised February 13, 1992

Abstract We prove four results on randomized incremental constructions (RICs):

• an analysis of the expected behavior under insertion and deletions,

• a fully dynamic data structure for convex hull maintenance in arbitrary dimensions,

• a tail estimate for the space complexity of RICs,

• a lower bound on the complexity of a game related to RICs.

1 Introduction

Randomized incremental construction (RIC) is a powerful paradigm for geometric algorithms [CS89, Mul88, BDS^{+}]. It leads to simple and efficient algorithms for a wide range of geometric problems: line segment intersection [CS89, Mul88], convex hulls [CS89, Sei90], Voronoi diagrams [CS89, MMO91, GKS90, Dev], triangulation of simple polygons [Sei91], and many others. In this paper we make four contributions to the study of RICs.

• We give a simple analysis of the expected behavior of RICs; cf. § 2. We deal with insertions and deletions and derive bounds for the expected number of regions constructed and the expected number of conflicts encountered in the construction. In the case of deletions our bounds are new, but compare [DMT91, Mul91a, Mul91b, Mul91c, Sch91] for related results, in the case of insertions the results were known, but our proofs are simpler.

∗A preliminary version of this papers was presented at the 9th Symposium on Theoretical Aspects of Computer Science (STACS 92)

†AT&T Bell Laboratories, Murray Hill, NJ 07974

‡Max Planck Institut für Informatik and Universität des Saarlandes; supported in part by ESPRIT II Basic Research Actions Program of the EC under contract no. 3075(project ALCOM)

§Computer Science Division, University of California at Berkeley, Berkeley, CA 94720

• We apply the general results on RIC to the problem of maintaining convex hulls in d-dimensional space; cf. § 3. We show that random insertions and deletions take expected time O(log n) for d ≤ 3 and time O(n^{⌊d/2⌋−1}) otherwise. If the points are in convex position, which is, e.g., the case when Voronoi diagrams are transformed into convex hulls of one higher dimension, the deletion time becomes log log n for d ≤ 3. Schwarzkopf [Sch91] has obtained the same bounds for all d ≥ 6, Mulmuley [Mul91c] has obtained the same bound for all d but with a more complex construction, and Devillers et al [DMT91] have previoulsy obtained the result for 2dimensional Voronoi-diagrams.

• We derive a tail estimate for the number of regions constructed in RICs; cf. § 4.

• We study the complexity of a game related to the O(n log^{∗} n) RICs of [Sei91] and [Dev] and show that the complexity of the game is Θ(n log^{∗} n); cf. § 5.

2 Randomized Incremental Constructions: General Theorems

Let S be a set with |S| = n elements, which we will sometimes call objects. Let F(S) be a multiset whose elements are nonempty subsets of S, and let b be the size of the largest element of F(S). We will call the elements of F(S) regions or ranges. If all the regions have size b, we will say that F(S) is uniform. For a region F ∈ F(S) and an object x, if x ∈ F we say that F relies on x or x supports F. For R ⊆ S, define F(R) = {F ∈ F(S) | F ⊂ R}. (That is, the multiplicity of F in F(R) is the same as in F(S).) We also assume a conflict relation C ⊆ S × F(S) between objects and regions. We postulate that for all x ∈ S and F ∈ F(S), if (x, F) ∈ C then F does not rely on x.

For a subset R ⊆ S, F_{0}(R) will denote the set of F ∈ F(R) having no x ∈ R with (x, F) ∈ C; that is, F_{0}(R) is the set of regions over R which do not conflict with any object in R.

Clarkson and Shor [CS89] analyzed the incremental computation of F_{0}(S). In the general step, F_{0}(R) for some subset R ⊆ S is already available, a random element x ∈ S \ R is chosen, and F_{0}(R ∪ {x}) is constructed from F_{0}(R).

Let (x_{1}, …, x_{j}) be a sequence of pairwise distinct elements of S, and R_{j} the set {x_{1}, …, x_{j}}. Let R_{0} = {}, the empty set. The history H = H(x_{1}, …, x_{r}) for insertion sequence (x_{1}, …, x_{r}) is defined as H = ⋃_{1≤i≤r} F_{0}(R_{i}). Let Π_{S} be

the set of permutations of S. For π = (x_{1}, …, x_{n}) ∈ Π_{S}, H_{r}(π) or simply H_{r} denotes the history H(x_{1}, …, x_{r}).

First, some simple facts about random permutations, whose proofs we leave to the reader:

Lemma 1 If π = (x_{1}, …, x_{n}) is a random permutation of S, then R_{j} is a random subset of S of size j, (x_{1}, …, x_{j}) is a random permutation of R_{j}, x_{j} is a random element of R_{j}, and if δ is a (fixed) permutation, then πδ is a random permutation.

We are now ready for an average case analysis of randomized incremental constructions. All expected values are computed with respect to a random ordering (x_{1}, ⋯, x_{n}) ∈ Π_{S} of the objects in S.

For subset R ⊆ S, r = |R|, and distinct objects x, y ∈ R, let

deg(x, R) = |{F ∈ F_{0}(R); x supports F }|
pdeg(x, y, R) = |{F ∈ F_{0}(R); x and y support F }|
c(R) = \frac{1}{r} ∑_{x∈R} deg(x, R)

p(R) = \frac{1}{r(r − 1)} ∑_{(x,y)∈R^{2}} pdeg(x, y, R) .

We call deg(x, R) the degree of x in R, pdeg(x, y, R) the degree of the ordered pair (x, y) in R, c(R) the average degree of a random object in R and p(R) the average pair degree of a random pair of objects in R. Of course, p(R) is only defined for r ≥ 2.

For integer r, 1 ≤ r ≤ n, let

c_{r} = E[c(R)] = ∑_{R⊆S,|R|=r} c(R)/\binom{n}{r}

and

p_{r} = E[p(R)] = ∑_{R⊆S,|R|=r} p(R)/\binom{n}{r}

be the expected average degree and pair degree for random R_{r} ⊂ S, and let

f_{r} = ∑_{R⊆S,|R|=r} |F_{0}(R)|/\binom{n}{r}

be the expected number of conflict-free regions of F(R), with respect to random R_{r}. Note that c_{1} = f_{1}. It will be convenient to adopt the convention that c_{j} = p_{j} = f_{j} = 0 for j < 1 or j > n, and (almost always) convenient to adopt the convention that p_{1} = f_{1}.

Lemma 2 The expectations c_{r}, p_{r}, and f_{r} satisfy c_{r} ≤ bf_{r}/r, and for r > 1, p_{r} ≤ b(b − 1)f_{r}/r(r − 1), with equality if F(S) is uniform.

Proof: For every region F ∈ F(S) there are at most b objects and at most b(b − 1) ordered pairs of objects which support F, and exactly as many if F(S) is uniform.

Theorem 3 Let C_{r} be the expected size of history H_{r}. Then C_{r} = ∑_{j≤r} c_{j}.

Proof: H_{0} is empty and hence C_{0} = 0. For r ≥ 1 the number of elements of H_{r} which are not already elements of H_{r−1} is equal to deg(x_{r}, R_{r}). Since R_{r} is a random subset of S of size r and x_{r} is a random object in R, we have

E[deg(x_{r}, R_{r})] = E[c(R)] = c_{r}.

In §4 we will strengthen Theorem 3 and prove a tail estimate for |H_{n}|.

Theorem 4 The expected number of regions in H_{r−1} which are in conflict with x_{r} is −c_{r} + ∑_{j≤r} p_{j}.

Proof: Let X be the number of regions F ∈ H_{r−1} with (x_{r}, F) ∈ C. Let H = H_{r−1} = H(x_{1}, …, x_{r−1}) and H′ = H(x_{r}, x_{1}, …, x_{r−1}), i.e., in H′ we “pretend” that x_{r} was put in first. We have

|H| + |H′\H| = |H′| + |H\H′|,

which holds for any two finite sets. Now X = |H\H′| since H\H′ is the set of regions in H which conflict with x_{r}. On the other hand, H′\H comprises regions supported by x_{r}; to count these regions, we count the number that appear when x_{j} is inserted. That is, letting R′_{j} = R_{j} ∪ {x_{r}}, for each region F ∈ H′\H there is exactly one j ≥ 1 such that F ∈ F_{0}(R′_{j}) and x_{j} supports F. Such a region is also supported by x_{r}, and so for given j the number of regions we count is pdeg(x_{r}, x_{j}, R′_{j}). Putting these observations together,

X = |H| − |H′| + |F_{0}({x_{r}})| + ∑_{1≤j≤r−1} pdeg(x_{r}, x_{j}, R′_{j}),

and so

EX = E|H| − E|H′| + E|F_{0}({x_{r}})| + ∑_{1≤j≤r−1} E[pdeg(x_{r}, x_{j}, R′_{j})]

We have E|H| = C_{r−1} by Theorem 3, and E|H′| = C_{r} by Theorem 3 and Lemma 1. Also E|F_{0}({x_{r}})| = f_{1} = p_{1} by convention, and E[pdeg(x_{r}, x_{j}, R′_{j})] = p_{j+1}, since R′_{j} = R_{j} ∪ {x_{r}} is a random subset of S of size j + 1 and x_{r} and x_{j} are random elements of this subset.

The following estimates are also useful.

Lemma 5 For j ≤ r the following holds:

(a) The expected number of regions in F_{0}(R_{j−1}) in conflict with x_{r} is f_{j−1} − f_{j} + c_{j}.

(b) The expected number of regions in F_{0}(R_{j−1}) supported by x_{j−1} and in conflict with x_{r} is at most b(f_{j−1} − f_{j} + c_{j})/(j − 1), with equality if F(S) is uniform.

Proof:

(a) We have

F_{0}(R_{j−1} ∪ {x_{r}}) = F_{0}(R_{j−1})\{F ∈ F_{0}(R_{j−1}); (x_{r}, F) ∈ C}
∪ {F ∈ F_{0}(R_{j−1} ∪ {x_{r}}); x_{r} supports F }

and hence the desired quantity is

E|F_{0}(R_{j−1})|−E|F_{0}(R_{j−1}∪{x_{r}})|+E|{F ∈ F_{0}(R_{j−1}∪{x_{r}}); x_{r} supports F }|

= f_{j−1} − f_{j} + c_{j}

(b) x_{j−1} is a random element of R_{j−1}. Hence a region considered in part (a) is supported by x_{j−1} with probability at most b/(j − 1).

Summation of the bound in Lemma 5b for j from 1 to r − 1 gives an alternative bound on the expected number of regions in H_{r−1} which conflict with x_{r}.

The conflict history G = G_{n} = G(π) for insertion sequence π = (x_{1}, ⋯, x_{n}) is the relation C ∩ (S × H_{n}). We may also describe this relation as a bipartite graph, with an edge between object x ∈ S and region F ∈ H_{n} when x and F conflict. The conflict history corresponds to the union (over time) of the conflict graphs in [CS89]. We use |G| to denote the size of the conflict history, i.e., the number of pairs in it.

Theorem 6 The expected size of the conflict history is

E|G| = −C_{n} + ∑_{j}(n − j + 1)p_{j}

Proof: Theorem 4 counts the expected number of edges incident to node x_{r} ∈ S. The claim follows by summation over r.

We next turn to random deletions. For π = (x_{1}, …, x_{n}) ∈ Π_{S} and r ∈ [1 . . n], let

π\r = (x_{1}, …, x_{r−1}, x_{r+1}, …, x_{n}),

and π\r = π for r ∉ [1 . . n]. We bound the expected size of the difference between H(π) and H(π\r) and between G(π) and G(π\r) for random π ∈ Π_{S} and random r ∈ [1 . . n].

Theorem 7

\frac{1}{n!n} ∑_{π∈Π_{S}} ∑_{r} |H(π) ⊕ H(π\r)| ≤ 2b\frac{C_{n}}{n} − c_{n},

with equality if F(S) is uniform.

Proof: For finite sets A and B,

|B ⊕ A| = |A| − |B| + 2|B\A|,

and so for H = H(π) and H(π\r),

|H ⊕ H(π\r)| = |H(π\r)| − |H| + 2|H\H(π\r)|.

The set H\H(π\r) comprises the regions in H supported by x_{r}. By Theorem 3, E|H| = C_{n}, and any F ∈ H is supported by no more than b objects, with equality if F(S) is uniform. Therefore on average the random x_{r} ∈ S supports no more than bC_{n}/n regions of H. By Theorem 3 and Lemma 1, we have E|H(π\r)| = C_{n−1}, and the theorem follows since C_{n−1} − C_{n} = −c_{n} by definition.

Theorem 8

E|G(π\i)\G(π)| = \frac{1}{n!n} ∑_{π∈Π_{S}} ∑_{i} |G(π\i)\G(π)|
≤ c_{n} − (b + 1)C_{n}/n + ∑_{j} bp_{j} − ∑_{j}(b + 1)(j − 1)p_{j}/n,

with equality if F(S) is uniform.

Proof: Letting G = G(π), we have

|G(π\i)\G| = |G(π\i)| − |G| + |G\G(π\i)|,

and by linearity of expectation,

E|G(π\i)\G| = E|G(π\i)| − E|G| + E|G\G(π\i)|.

Theorem 6 gives an expression for E|G|, and together with Lemma 1 it gives a similar expression for E|G(π\i)|, yielding

E|G(π\i)\G| = E|G\G(π\i)| + c_{n} − ∑_{j} p_{j}.

(Alternatively, note that E|G| − E|G(π\i)| is the expected number of regions of H_{n} conflicting with x_{i}, and use Theorem 4.) We need to find E|G\G(π\i)|. A pair (x, F) is in G\G(π\i) if it is in G and either x_{i} = x or x_{i} ∈ F. At most b+1 choices of x_{i} allow this, for any (x, F) ∈ G, and so E|G\G(π\i)| ≤ (b+1)E|G|/n, with equality if F(S) is uniform. The result follows using Theorem 6 and easy manipulations.

In the convex hull algorithm of §3, the conflicts of G(π\i)\G(π) are not quite all those examined when deleting x_{i}. The following bound will also be useful.

Lemma 9 Let I be the set of conflicts of the form (x_{j}, F) with j > i and F ∈ F_{0}(R_{i−1}) \ F_{0}(R_{i}). Then for random π ∈ Π_{S} and random i ∈ [1 . . n], E|I| = (E|G| − E|H| + f_{n})/n.

Proof: Let I_{i} denote the set I for x_{i}. Then E|I| = ∑_{i} E|I_{i}|/n, and since the I_{i} are disjoint, E|I| = E| ∪_{i} I_{i}|/n. For any conflict (x_{j}, F) ∈ G, either F ∈ F_{0}(R_{j−1}), or there is exactly one i < j such that F ∈ F_{0}(R_{i−1})\F_{0}(R_{i}). In the latter case, (x_{j}, F) ∈ I_{i}. To count the conflicts (x_{j}, F) with F ∈ F_{0}(R_{j−1}), note that each F ∈ H\F_{0}(S) appears this way exactly once. Thus E|G| = E| ∪_{i} I_{i}| + E|H| − |F_{0}(S)|, from which the Lemma follows.

3 Dynamic Convex Hulls

We apply the results of §2 to the problem of maintaining the convex hull in d-dimensional space under insertions and deletions of points. Let X ⊂ IR^{d} be a set of points, which we assume to be in nondegenerate position: no d + 1 lie in a common hyperplane. For R ⊆ X, let conv R denote the convex hull of R. We let x_{1}, x_{2}, …, x_{n} denote the points in X in the order of their insertion, and let R_{i} denote {x_{1}, …, x_{i}}.

3.1 The Insertion Algorithm

To maintain the convex hull of R under insertions, we maintain a triangulation T of the hull: a simplicial complex whose union is conv R. (A simplicial complex is a collection of simplices such that the intersection of any two is a face of each.) The vertices of the simplices of T are points of R. The triangulation is updated as follows when a point x is added to R: if x ∈ conv R, and so is in some simplex S of T, leave T as it was. If x ∉ conv R, then for every facet F of the hull of R visible to x, add to T the simplex S(F, x) = conv(F ∪ {x}). Call F the base facet and x the peak vertex of the simplex. A facet is visible to x or x-visible just when S(F, x) meets the hull only at F. We may also say, for x-visible F, that x is visible to F, and they see each other. Use T_{r} to denote the triangulation after the insertion of x_{1}, x_{2}, …, x_{r}.

This process is called triangulation by “placing” [Ede87]. It should be clear that the stated conditions on the triangulation are preserved. (When r ≤ d + 1, we simply maintain a single (r − 1)–dimensional simplex.) It will be convenient to extend the triangulation so that facets of the current hull are also base facets of simplices; this gives a uniform representation. The peak vertex of these simplices is a “dummy” that in effect is visible to all current facets; we use \overline{O} to denote this dummy vertex and we use O to denote a point inside the first full-dimensional simplex created, when r = d + 1. (Here we use the assumption of nondegenerate position.) Call the first full-dimensional simplex the origin simplex. (In the terminology of ”two-sided space” [Sto87] O and \overline{O} could be called the origin and anti-origin respectively: while the origin sees no facets of the current hull of R, the anti-origin sees all of them.) We use T to also denote the extended triangulation. To carry the uniformity even further, we designate the vertex x_{d+1} the peak of the origin simplex and call its opposite facet the base of the origin simplex. In this way, there are d + 2 simplices in the (extended) triangulation when the first full-dimensional simplex is created: the origin simplex and d + 1 simplices with peak \overline{O}. One facet of the origin simplex (better: its two sides) is base facet of two simplices and all other facets of the origin simplex are base facet of one simplex.

Two simplices of T are neighbors if they share a facet. The neighbor relation defines the neighborhood graph on the set of simplices. Call a neighbor of some simplex S and a vertex x of S opposite to each other, if the common facet does not contain x. In an implementation, we propose to store the directed version of the neighborhood graph augmented by information which supports the following operations in constant time: identification of the neighbor of a simplex sharing the base facet, identification of the peak vertex of a simplex, and identification of the vertex opposite to a facet. We also store for each simplex the equation of the hyperplane supporting the base facet of the simplex. The equation is normalized such that the peak lies in the positive half-space.

We discuss next two search methods for finding the x-visible current facets of conv R.

Here is one method: locate x in T by walking along the segment \overline{Ox} beginning at O. If this walk enters a simplex whose peak vertex is the anti-origin, then an x-visible current facet has been found. Otherwise, a simplex of T containing x has been found, showing that x ∈ conv R. In the former case, find all x-visible hull facets by a search of the simplices incident to the anti-origin. These simplices form a connected set in the neighborhood graph. We call this search method the segment-walking method.

Another search method is the following: starting at the origin simplex and the simplex sharing its base facet explore simplices according to the rule: if a simplex has an x-visible base facet, search its neighbors (not including the neighbor that shares the base facet). Here we say that a base facet F is xvisible if that was true (in the previous sense) at the time that F was a current hull facet. This search procedure reaches all x-visible current hull facets, i.e., all simplices S(F, \overline{O}) with x-visible base facet F, since the base facets of all simplices traversed in the segment-walking search method are x-visible. We call this search scheme the all-visibilities method.

We finally turn to the update procedure. At this point, we have found the current hull facets seeing x, in the form of the simplices whose base facets see x and with the anti-origin as their peak vertex. Let V be the set of such simplices. Now we update T by altering these simplices, and creating some others. The alteration is simply to replace the anti-origin with x in every simplex in V.

The new simplices correspond to new hull facets. Such facets are the hull of x and a horizon ridge f; a horizon ridge is a (d − 2)–dimensional face of conv R with the property that exactly one of the two incident hull facets sees x. Each horizon ridge f gives rise to a new simplex A_{f} with base facet conv(f ∪ {x}) and peak \overline{O}. For each horizon ridge of conv R there is a non-base facet G of a simplex in V such that x does not see the base facet of the other simplex incident to the facet G. Thus the set of horizon ridges is easily determined.

It remains to update the neighbor relationship. Let A_{f} = S(conv(f∪\{x\}), \overline{O}) be a new simplex corresponding to horizon ridge f. In the old triangulation (before adding x) there were two simplices V and N incident to the facet conv(f ∪ \{\overline{O}\}); V ∈ V and N ∉ V. In the updated triangulation V has peak x. The neighbor of A_{f} opposite to x is N and the neighbor opposite to \overline{O} is (the updated version) of V. Now consider any vertex q ∈ f and let S = S_{f,q} be the set of simplices with peak x and including vertex(f) \ {q} ∪ {x} in their vertex set; for a face f we use vertex(f) to denote the set of vertices contained in f. We will show that the neighbor of A_{f} opposite to q can be determined by a simple walk through S. This walk amounts to a rotation about the (d − 2)–face conv(vertex(f) \ {q} ∪ {x}). Note first that V ∈ S. Consider next any simplex S = S(F, x) ∈ S. Th

3.2 Analysis of Insertions

The cost of adding a point to set R is the time needed to locate the point x in the triangulation T, plus the time needed to update the triangulation.

We need some additional notation. Let t_{0} be the number of simplices visited by the walk along segment \overline{Ox}, let t_{1} be the set of simplices with x-visible base facet, let t_{2} be the set of simplices visited by the all-visibilites method, let t_{3} be the number of simplices with peak x, and let t_{4} be the number of new hull facets. Then t_{0} ≤ t_{1}, since the base facets of all simplices traversed by the segment-walking method see x, and t_{2} ≤ (d + 1) · t_{1} since a simplex has d + 1 neighbors.

In the segment-walking method the time spent on the walk is O(d^{2}) · t_{0}, since given the entry point of segment \overline{Ox} into a simplex S the exit point can be found in time O(d^{2}); it takes time O(d) per facet to compute the point of intersection, i.e., O(d^{2}) altogether, and O(d) time to select the first intersection following the entry point. The segment-walk determines the simplex containing x. All visible hull facets can then be determined in time O(d^{2})·t_{3}, since visiblity can be checked in time O(d) per base facet and since a visible facet has at most d invisible neighbors. We define the search time of the segment-walking method to be O(d^{2}) · t_{0} = O(d^{2}) · t_{1} and include the O(d^{2}) · t_{3} term in the update time.

The search time for the all-visibilities method is O(d) · t_{2} = O(d^{2}) · t_{1}, since O(d) per simplex is needed for the visibility check and since the degree of the neighborhood graph is d + 1.

Let’s turn to the update time next. We need to alter t_{3} simplices; this takes time O(1) · t_{3}. For each new simplex we have to compute the equation of the hyperplane supporting the base facet. This takes time O(d^{3}) · t_{4}, since solving the linear systems for the normal vectors requires O(d^{3}) time per simplex (A factor of d can be removed using complicated rank-one updating techniques, if desired.). Finally, we need to update the neighbor relation. Let S = S_{f,q} be defined as in the previous section. The walk through S takes time O(d · |S|), since the neighbors in S of a simplex in S can be determined in time O(d). Next observe, that a simplex S = S(F, x) ∈ V can belong to at most d(d−1) different sets S_{f,q}, since f \ \{q\} can be obtained from F by deleting two vertices (\binom{d}{2} choices) and since there are only two choices for q once f \ {q} is fixed (Note that there are only two horizon ridges containing f \ {q}.). Thus the time to update the neighbor relation is O(d^{3})·t_{3} and total update time is O(d^{3})·(t_{3}+t_{4}).

We next establish the connection to § 2. Our regions are half spaces. More formally, we have b = d and F(X) contains two copies of each subset {x_{1}, …, x_{d}} ⊆ X of cardinality d. These two copies are identified with the two open half-spaces defined by the hyperplane through points x_{1}, x_{2}, …, x_{d}. A point x is said to conflict with a half-space if it is contained in the half-space. In this way, for |R| ≥ d + 1 the regions in F_{0}(R) correspond precisely to the facets of the convex hull of R (recall that we assume our points to be in general position) and a facet F of conv R is visible from x ∉ R if x conflicts with the half-space supporting the facet. Also |F_{0}(R)| = 2 if |R| = d, F_{0}(R) = ∅ for |R| < d, and F(X) is uniform. Using the notation of §2, we therefore have f_{r} = 0 for r < d and f_{d} = 2; for r > d, f_{r} is the expected number of facets of conv R for random subset R ⊆ X with |R| = r.

Theorem 10 (a) The expected number of simplices of T_{r} is C_{r} = ∑_{j≤r} df_{j}/j.

(b) The expected search time for x_{r}, using either search method, is O(d^{2}) times

−c_{r} + ∑_{2≤j≤r} p_{j} = −\frac{d}{r}f_{r} + ∑_{2≤j≤r} \frac{d(d − 1)}{j(j − 1)}f_{j}.

(c) The expected time to construct the convex hull of n points using either search method is

O(d^{3}) ∑_{j} \frac{d}{j}f_{j} + O(d^{3}) ∑_{j} \frac{d(d − 1)}{j(j − 1)}(n − j + 1)f_{j} = O(d^{5}) ∑_{j} \frac{nf_{j}}{j(j − 1)}.

Proof:

(a) Each simplex has a base facet, and so the bound follows from Theorem 3 and Lemma 2.

(b) ¿From the above discussion, we need to find t_{1}, the expected number of facets that are x_{r}–visible. The expected number of visible facets is −c_{r} + ∑_{j≤r} p_{j}, by Theorem 4.

(c) The work per simplex of T_{n} is O(d^{3}), as discussed above. The bound follows, using (a) and summing the bound of (b) over r.

Since f_{r} = O(r^{⌊d/2⌋}) in the worst case, the running time is O(n log n) for d ≤ 3, and O(n^{⌊d/2⌋}) for d ≥ 4. We note also that for many natural probability distributions, the expected complexity of the hull of random points satisfies f_{r} = O(r) for fixed d. For such point sets, our algorithm requires O(n log n) expected time.

3.3 The Deletion Algorithm

The global plan is quite simple. When a point is deleted from R, we change the triangulation T so that in effect x was never added. This is in the spirit of § 2. The effect of the deletion of x on the triangulation T is easy to describe. All simplices having x as a vertex disappear (If x is not a vertex of T then T does not change). The new simplices of T resulting from the deletion of x all have base facets visible to x, with peak vertices inserted after x. These are the simplices that would have been included had x not been inserted into R. Let R(x) be the set of points of R that are contained simplices with vertex x, and also inserted after x. We will, in effect, reinsert the points of R(x) in the order in which they were inserted into R, constructing only those simplices that have bases visible to x. On a superficial level, this describes the deletion process. The details follow.

Let π = (x_{1}, …, x_{n}) be the insertion order and assume that x = x_{i} is deleted. We first characterize the triangulation T (π \ i).

Lemma 11 Assume that x = x_{i} is a vertex of T. The triangulation T (π \ i) can be obtained from the triangulation T (π) as follows:

1. Set T = T (π).

2. Remove all simplices having x_{i} as a vertex.

3. k ← i + 1;

while k ≤ n

do (∗ invariant A holds here ∗)

for all facets F of conv(R_{k−1} \ {x_{i}}) visible to x_{i} and x_{k} do add S(F, x_{k}) to T od; k ← k + 1

od

(∗ invariant A holds here with k = n + 1 ∗)

Proof: It suffices to show that the following statement A is an invariant of the while–loop.

A :  T = T (x_{1}, …, x_{i−1}, x_{i+1}, …, x_{k−1}) ∪ {S; S = S(F, x_{j}) is a simplex in T (π \ i)
with peak x_{j}, j ≥ k, and x_{i}–invisible base facet F }

Assume k = i + 1 first. All simplices in T (x_{1}, …, x_{i−1}) clearly belong to T. Consider next a simplex S = S(F, x_{j}) in T (π \ i) with peak x_{j}, j ≥ k = i + 1, and base facet F invisible to x_{i}. Then F is a facet of conv(R_{j−1} \ {x_{i}}) and, since F is invisible to x_{i}, also a facet of conv R_{j−1}. Thus S belongs to T (π) and is not removed in step 2. Therefore, S ∈ T.

Conversely, let S = S(F, x_{j}) be any simplex of T. If j < i then clearly S ∈ T (x_{1}, …, x_{i−1}). If j > i then F is a facet of conv R_{j−1} and x_{i} is not a vertex of F (since S is not removed). Thus F is a facet of conv(R_{j−1} \ {x_{i}}) and hence S ∈ T (π \ i). Also F is not visible from x_{i}. This completes the case k = i + 1.

For k > i + 1, we only have to observe that T (x_{1}, …, x_{i−1}, x_{i+1}, …, x_{k−1}) can be obtained from T (x_{1}, …, x_{i−1}, x_{i+1}, …, x_{k−2}) by adding all simplices S(F, x_{k−1}) where F is a facet of conv(R_{k−2} \ {x_{i}}) visible to x_{k−1}. If F is also visible to x_{i} then the loop body adds S to T, if F is not visible to x_{i} then S is already in T by the induction hypothesis.

Lemma 11 characterizes the new simplices added to T. We show next that only points in R(x) can contribute new simplices (Lemma 12) and that the set of facets of conv(R_{k−1}\{x_{i}}) visible from x_{i} can be easlily maintained (Lemma 13).

Lemma 12 Let i < k and assume that x = x_{i} is a vertex of T. Then y = x_{k} ∈ R(x_{i}) if some facet F of conv(R_{k−1} \ {x}) is visible to x and y.

Proof: The hyperplane supporting F separates conv(R_{k−1} \ {x}) from y and x and hence y is not the convex combination of points in R_{k−1} \ {x}. If y ∈ conv R_{k−1} then y is the convex combination of points in R_{k−1} and therefore the simplex of T containing y must have x as a vertex. Thus y ∈ R(x). If y ∉ conv R_{k−1} then some facet G of conv R_{k−1} that contains x must be visible from y (e.g. one that intersects the line segment joining y with some point of F, which, being visible from x, is not a facet of conv R_{k−1}). But now S(G; x) is a simplex of T, and hence y ∈ R(x).

Lemma 13 For y ∈ R(x) let B(y) = {conv(f ∪{y}); S(f ∪{x_{i}}, y) is a simplex of T }. Step 3 in Lemma 11 may be replaced by:

B ← set of facets of conv R_{i−1} visible to x; for all y ∈ R(x) in ascending insertion order do (∗ let y = x_{k}; then B is the set of facets of conv(R_{k−1} \ {x_{i}}) visible from x_{i} ∗);

V B ← {F; F ∈ B; F is y-visible }

NB ← {F; F is a non-base facet of S(G, x_{k}) with G ∈ V B, F x_{i}-visible and f = F ∩ G

a horizon ridge of conv(R_{k−1} \ {x_{i}})}

B ← (B \ V B) ∪ NB ∪ B(y) od

Proof: We only need to verify the invariant. By Lemma 12 B changes only when a point y = x_{k} ∈ R(x) is reinserted. Let B be the set of x_{i}-visible facets of conv(R_{k−1} \{x_{i}}) and let B′ be the set of x_{i}-visible facets of conv(R_{k} \{x_{i}}). Then B′ = (B′ ∩ B) ∪ (B′ \ B). Observe next that B′ ∩ B = B \ V B and that each facet F ∈ B′ \ B is incident to x_{k}. Thus f = conv(f ∪ {x_{k}}) for some horizon ridge f of conv(R_{k−1} \ {x_{i}}). Let G be the base facet of the simplex having F as a facet. Then f = F ∩ G. Also, if G is x_{i}-visible then F ∈ NB and if G is not x_{i}-visible then F ∈ B(y).

We are now ready for the algorithmic details.

To handle deletions, we must augment our data structure slightly. We assume that each point can access some simplex containing it in constant time and that every simplex knows the set of points contained in it.

Check first, whether x is a vertex of the simplex pointed to by x. If not, x is removed and we are done. If so, construct the set R(x) by inspection of all simplices incident to x. This takes time proportional to d times |R(x)| plus the number of simplices with peak x. (Note that a simplex which has x in its base facet contributes its peak to R(x) and that a simplex has at most d + 1 neighboring simplices).

Next, sort the points in R(x) by the time of insertion. This takes time O(min{n, |R(x)| log log n}), where the former bound is obtained by bucket sort and the latter bound comes from the use of bounded ordered dictionaries ([vKZ77, MN90]). Also, collect for each point y ∈ {p} ∪ R(x) the set of simplices S(y) with peak y and also having x as a vertex. Next remove all simplices incident to x from T (cf. step 2 in Lemma 11). The set B (cf. Lemma 13) is initialized to the set of base facets of simplices in S(x). The neighborhood graph on the set B is given by the incidence information of the simplices in S(x). The set B(y), for y ∈ R(x), and its neighborhood graph is easily determined from the set S(y).

The points in R(x) are now processed in the insertion order. Consider y = x_{k} ∈ R(x). We first determine all facets in B visible from y. To do so we distinquish cases.

Assume first that y is a vertex. For each simplex S ∈ S(y) let f(S) be the ridge with all the vertices of S but x and y. f(S) is a ridge of conv R_{k−1} not incident to x and hence a ridge of conv(R_{k−1} \ {x}). Also, f(S) is visible from x and y and hence a ridge of B. Thus if we maintain the correspondence (via a dictionary for (d − 2)–tuples representing ridges) between the ridges of removed simplices and ridges of B, we can find the set {f(S); S ∈ S(y)} in B in time proportional to d times the number of simplices in S(y). Starting in the facets of B incident to these ridges a simple graph search of B’s neighborhood graph determines all y-visible facets of B in time proportional to d times their number. This is the content of

Lemma 14 Let y be a vertex. Then all y-visible facets of B can be reached from a ridge in {f(S); S ∈ S(y)} in the neighborhood graph of B.

Proof: Let G be the facet graph of conv R_{k−1} and let G_{x} and G_{y} be the parts of G formed by the facets and ridges of conv R_{k−1} that are visible from x and y, respectively. Note that G_{x} as well as G_{y} is connected (in the topological sense and in the graph theoretic sense). Moreover note that G_{x} is nothing but B. The set {f(S); S ∈ S(y)} comprises exactly all ridges in G_{y} for which exactly one of the containing facets is in G_{x}. Connectedness of G_{y} now ensures that all facets and ridges that are in G_{x} and in G_{y} can be reached from some ridge in {f(S); S ∈ S(y)}.

For non–vertices y one has to work harder. We first show how to identify a single facet in B visible from y and then argue that a graph seach determines all y-visible facets in B. Assume first that y is contained in a simplex S ∈ S(x). Let S = (F, x), and let O be the intersection of F with the line through x and y. Locate y by a walk along \overline{Oy} starting at O. Assume next that y is contained in a simplex S ∈ S(z) for some z ∈ R(x). The ridge f(S) of S with all vertices but x and y is a ridge of B when point z is reinserted and hence the facet spanned by f(S) and z is added to T when point z is reinserted. Let O be the intersection of that facet with the line through x and y. Locate y by a walk along \overline{Oy} starting at O.

Lemma 15 The walk along \overline{Oy} traverses only newly constructed simplices whose base facet is y–visible.

Proof: The line segment \overline{Oy} is contained in the simplex S. This implies that \overline{Oy} traverses only new simplices. Let S′ with base facet G be a simplex traversed. Then G is x–visible. Since S′ is intersected by \overline{Oy} and G is visible from every point in S′, G must be visible from either O or y. But O-visibility and x-visibility of G and the fact that y ∈ \overline{Ox} implies y-visibility of G. Thus G is y-visible.

At this point we have found one y-visible facet in B.

Lemma 16 Let y = x_{k} be a non-vertex. Then all y-visible facets of conv(R_{k−1}\ {x_{i}}) are also x_{i}-visible.

Proof: Assume that there are y-visible facets of conv(R_{k−1} \ {x_{i}}) and let F be one of them. Then x_{i} ∉ conv R_{k−1} and there is a facet G of conv(R_{k−1}\{x_{i}}) such that y ∈ S(G, x_{i}). Then the hyperplane supported by F separates G and y. Thus x_{i} sees F.

The set of y-facets of conv(R_{k−1}\{x_{i}}) is neighbor-connected and is identical to the set of y-visible facets in B. Thus a graph search on B finds all y-visible facets in B.

If the points in S are in convex position, as when computing Voronoi diagrams in one less dimension [Ede87, section 1.8], all points y are vertices and hence the search time is well covered by the time to construct new simplices.

In either case we have now identified the set of y-vertices in B. We now construct new simplices, add B(y) to B and update the neighborhood graph on B.

Having reinserted the points in R(x) the cavity created by the removal of x is filled. A traversal of the new simplices and the boundary of the cavity allows to match (using a dictionary for facets) the new simplices with the old simplices sharing a common facet. This completes the update step.

In summary, the cost of the removal of x is bounded by the sum of the following quantities:

(1) min(n, |R(x)| log log n),

(2) O(d^{3}) times the number of removed and newly constructed simplices,

(3) O(d^{2}) times the sum over all points y ∈ R(x) of the number of y–visible facets ever contained in B.

If the points are in convex position, then the sum of the first two quantities suffices.

3.4 Analysis of Deletions

We analyze the cost of a deletion under the assumption that the points were inserted in random order and that a random point is deleted.

Lemma 17 The expected number of removed simplices is bounded by

∑_{i≤n} d(d + 1)f_{i}/(i · n)

and the expected number of new simplices is no larger.

Proof: The expected number of simplices in T (π) is C_{n} and the expected number of simplices in T (π\i) is C_{n−1} according to Theorem 10 and Lemma 1. Also each simplex of T (π) has d + 1 vertices and therefore the expected number of removed simplices is (d + 1)(C_{n} − f_{n})/n. The expected number of new simplices is thus (C_{n−1} − f_{n−1}) − (C_{n} − f_{n} − (d + 1)(C_{n} − f_{n})/n) which is no larger than the number of removed simplices. The bound now follows from Theorem 3 and Lemma 2.

Lemma 18 The expected size of R(x) is bounded by

(d + 1) (2 + d ∑_{i≤n} f_{i}/(i · n)) .

Proof: Let R_{1}(x) be the set of points y ∈ R(x) which are vertices of T and let R_{2}(x) = R(x) \ R_{1}(x). To bound |R_{1}(x)|, observe that |R_{1}(x)| is at most d plus the number of destroyed simplices. Thus

E [|R_{1}(x)|] ≤ d + ∑_{i≤n} d(d + 1)f_{i}/(i · n).

To bound |R_{2}(x)|, observe that each non–vertex y is incident to exactly one simplex (recall that our points are in general position) and that x is the vertex of such a simplex with probability (d + 1)/n. Thus

E [|R_{2}(x)|] ≤ n(d + 1)/n = (d + 1).

We next bound the sum over y ∈ R(x) of the number of y–visible facets ever contained in B. Such a facet is either a y– and x–visible facet of conv R_{i−1} (recall that x = x_{i}) or a newly constructed base facet visible to y and x.

Lemma 19 (a) The expected number of facets of conv R_{i−1} visible to x_{i} and x_{j} summed over j > i and for random i is (E|G| − E|H| + f_{n})/n.

(b) The expected number of new base facets visible to x_{j} summed over j > i and for random i is E|G(π\i) \ G(π)|.

Proof: Part (a) follows from Lemma 9 and part (b) is obvious.

Theorem 20 The expected time to delete a random point from the convex hull of n points (constructed by random insertions) is

O (min {n, (d + d^{2} ∑_{i≤n} f_{i}/(i · n)) log log n} + d^{5} ∑_{i≤n} f_{i}/(i · n) + d^{5} ∑_{2≤i≤n} f_{i}/(i(i − 1))) .

If the points are in convex position, then time

O (min {n, (d + d^{2} ∑_{i≤n} f_{i}/(i · n)) log log n} + d^{5} ∑_{i≤n} f_{i}/(i · n))

suffices.

Proof: This follows immediately from the summary at the end of § 3.3, Lemmas 17 to 19, and Theorems 3 and 8.

We have f_{i} = O(i^{⌊d/2⌋}). A deletion from a convex hull in IR^{3} therefore takes time O(log n) and a deletion from a Voronoi diagram in IR^{2} takes time O(log log n). For d ≥ 4, a deletion from a convex hull in IR^{d} and a Voronoi diagram in IR^{d−1} takes time O(n^{⌊d/2⌋−1}). We note also that for many natural probability distributions, the expected complexity of the hull of random points satisfies f_{r} = O(r) for fixed d. For such point sets, a random deletion requires O(log n) expected time.

4 A Tail Estimate for the Size of the History

In this section, we derive a tail estimate for the size of the history. We first prove a general lemma and then apply one of its consequences to obtain a tail estimate for the size of the history in randomized incremental constructions.

In the notation of §2, we want to study the random variable X = ∑_{j} deg(y_{j}, R_{j}) for random permutations π = (y_{1}, …, y_{n}) of S, inducing the subsets R_{j} = {y_{1}, …, y_{j}}. Let p(x) = p_{S}(x) be the generating function of this random variable. By the following standard observation, we can use bounds on p(x) to show that X is large only with low probability.

Fact 21 If Z is a non–negative integer random variable with generating function p(x), then for any k ≥ 0

Pr[Z ≥ k] ≤ p(a)/a^{k} for any a ≥ 1.

Suppose for some function M(r) we have b · |F_{0}(R)| ≤ M(r) when |R| = r. Then we have the following bound on p(x).

Claim 22 For all x > 1 we have

p(x) ≤ p_{n}(x) := ∏_{1≤i≤n}(1 + \frac{1}{i}(x^{M(i)} − 1)) .

Proof: We use induction on n, the size of S, looking at corresponding generating functions for subsets of S. The claim holds vacuously for n = 0.

For the random permutation π of S, we know that y_{n} is a random element of S, and so

p(x) = p_{S}(x) = \frac{1}{n} ∑_{y∈S} x^{deg(y,S)}p_{S\\{y\}}(x).

Applying the inductive assumption to every (n − 1)-element subset of S, we get

p(x) = \frac{p_{n−1}(x)}{n} ∑_{y∈S} x^{deg(y,S)}.

Since

∑_{y∈S} deg(y, S) ≤ b|F_{0}(S)| ≤ M(n),

the power sum is maximized for x > 1 when deg(y, S) = M(n) for some y ∈ S and the degrees of the other members of S are zero. Thus

p(x) ≤ \frac{p_{n−1}(x)}{n}(x^{M(n)} + (n − 1)) = (1 + \frac{1}{n}(x^{M(n)} − 1))p_{n−1}(x) = p_{n}(x) .

Theorem 23 For any integer M ≥ 0 and any real x ≥ 1

Pr[X ≥ M] ≤ \frac{∏_{1≤i≤n}(1 + \frac{1}{i}(x^{M(i)} − 1))}{x^{M}} ≤ \frac{e^{∑_{1≤i≤n} \frac{1}{i} (x^{M(i)}−1)}}{x^{M}} .

Proof: This follows from Fact 21 and Claim 22, using the inequality 1+x ≤ e^{x}.

Corollary 24 If M(i)/i is non–decreasing, then for all c > 1

Pr[X ≥ cM(n)] ≤ (1/e) · (e/c)^{c} .

Proof: If M(i)/i is non–decreasing, then for all x ≥ 1 we have \frac{1}{i}(x^{M(i)} − 1) ≤ \frac{1}{n}(x^{M(n)} − 1) for each i ≤ n. (The polynomial \frac{1}{n}(x^{M(n)} − 1) − \frac{1}{i}(x^{M(i)} − 1) has a root at x = 1 and nonnegative derivative for x ≥ 1.) Therefore

Pr[X ≥ cM(n)] ≤ \frac{e^{∑_{1≤i≤n} \frac{1}{i} (x^{M(i)}−1)}}{x^{cM(n)}} ≤ \frac{e^{∑_{1≤i≤n} \frac{1}{n} (x^{M(n)}−1)}}{x^{cM(n)}} = \frac{e^{x^{M(n)}−1}}{x^{cM(n)}} .

Now choose x such that x^{M(n)} = c.

For many RICs, e.g., the construction of convex hulls (in any dimension) ([CS89] and this paper), Delauney triangulations ([GKS90]), abstract Voronoi diagrams ([MMO91]), trapezoidal diagrams for non–intersecting line segments ([CS89, Sei91]), spherical intersections ([CS89]) and the construction of a single face of an arrangement ([CEG^{+}91]), there is a function M(r) such that M(r)/r is non-decreasing, b|F_{0}(R)| ≤ M(r) when |R| = r, and M(r) ≤ dC_{r} for some small constant d. In these situations, Corollary 24 bounds the probability that the size of the history exceeds its expected value by a constant factor.

The following Corollary of Theorem 23 may also be useful.

Corollary 25 If M(i) = m_{0} for all i, then Pr[X ≥ cm_{0}H_{n}] ≤ e^{−H_{n}(1+c log(c/e))} for c > 1, where H_{n} is the n–th harmonic number.

Proof: From Theorem 23 we get

Pr[X ≥ cm_{0}H_{n}] ≤ \frac{e^{∑_{1≤i≤n} \frac{1}{i} (x^{m_{0}} −1)}}{x^{cm_{0}H_{n}}} = \frac{e^{H_{n}(x^{m_{0}} −1)}}{x^{cm_{0}H_{n}}} .

Now choose x such that x^{m_{0}} = c to obtain the desired result.

5 A game related to some randomized incremental constructions

Seidel [Sei91] gave a randomized O(n log^{∗} n) algorithm for the triangulation of simple polygons. Devillers [Dev] recently extended the approach to other problems, e. g., the construction of the Voronoi–diagram for the edges of a simple polygon. The idea behind the O(n log^{∗} n) is as follows: When an object x ∈ S−R is added to R in standard RIC, the object x traces through the history of the construction. This takes time O(log r) for the r–th object to be inserted (apply Theorem 4 with f_{j} = O(j)). On the other hand, in the two examples mentioned above, all conflicts between objects in S−R and regions in F_{0}(R_{i}) can be computed in expected linear time. Seidel and Devillers therefore interrupt the standard algorithm at suitable breakpoints , say after the i–th insertion, and compute all conflicts between S − R_{i} and F_{0}(R_{i}). The crucial observation is now that if object x_{k} ∈ S − R_{i} knows its conflicts with the regions in F_{0}(R_{i}) then its conflicts with the regions in F_{0}(R_{k−1}) can be computed in additional O(log(k/i)) expected time; sum the bound in Lemma 5 for j between i and k to see that only O(log(k/i)) additional conflicts exist on average. A suitable choice of breakpoints yields an O(n log^{∗} n) algorithm. Can this approach yield linear time algorithms? The following game is supposed to shed some light on this question.

The game is played on a sequence of n balls. Initially, all balls have label 1 and color white. There are two players A and B who take turns. The game stops when all balls are black. In its r–th turn player A selects a white ball, turns it black and labels it r. The cost of this move is log(r/r_{old}), where r_{old} is the previous label of the ball. In its turn, B performs one or more of the following moves: She selects an interval of balls and relabels all balls in the interval with the highest label occurring in the interval. The cost of the move is the length of the interval. A tries to maximize cost, B tries to minimize it.

The intended relationship to RIC is as follows: A ball is black if it belongs to R. The label of a ball is i if the ball knows its conflicts with the regions in F_{0}(R_{i}). A move of player A moves a ball from time r_{old} in the history to time r and a move of player B moves an interval of points to the latest time in history occurring in the interval. In the algorithms mentioned above, the interval is always the entire sequence of balls.

Let L = log^{∗} n = max{i; log^{(i)} n > 1}, D_{i} = log^{(i)} n for 1 ≤ i ≤ L, D_{L+1} = 1, and D_{0} = n + 1. Let B_{i} = ⌊n/D_{i}⌋ for 0 ≤ i ≤ L + 1.

Lemma 26 Player B can keep the cost in O(n log^{∗} n).

Proof: B plays the following simple strategy. In its B_{i}–th turn, 1 ≤ i ≤ L, B relabels the complete sequence of balls. The total cost of B’s moves is nL = n log^{∗} n. The total cost of A’s moves is

≤ ∑_{0≤i≤L}(B_{i+1} − B_{i}) log(B_{i+1}/max{B_{i}, 1}) = O(n log^{∗} n)

Lemma 27 Player A can force the cost into Ω(n log^{∗} n).

Proof: We first describe the strategy of player A. A’s game is divided into phases; the i–th phase, 1 ≤ i ≤ L + 1, consists of moves B_{i−1} + 1 to B_{i}. In the i–th phase, A labels all multiples of D_{i} which are not multiples of D_{i−1}. We assume here that the balls are numbered 1 through n.

We show that the total cost of A’s and B’s moves in the i–th phase is Ω(n). Call a multiple of D_{i} interesting if A labels it by one of the moves B_{i}/2 + 1 to B_{i}. If for more than 1/2 of the interesting balls the cost of A’s move is log((B_{i}/2)/ max(1, B_{i−1})), then the total cost of A’s moves in the i–th phase is Ω(B_{i}/2 · log(D_{i−1}/D_{i})) = Ω(B_{i} · (D_{i} − D_{i+1})) = Ω(n). Otherwise, more than half of the interesting points must have been relabeled in the i–th phase by a move of B, since all interesting points have label at most B_{i−1} at the beginning of the i–th phase. Since an interesting point has distance D_{i} from any point touched by A in the i–th phase, the total cost of B’s moves must be at least Ω(B_{i}/2 · D_{i}) = Ω(n). In either case we have shown that the cost of a phase is Ω(n). Since there are log^{∗} n phases, the lower bound follows.

In Lemma 27, player A chooses balls so as to make the life for player B as difficult as possible. In RIC’s objects are chosen randomly. Let us say that player A plays randomly if he always chooses a random white ball.

Lemma 28 If A plays randomly, then the expected cost of the game is Ω(n log^{∗} n).

Proof: Define the division into phases as in Lemma 27. At the end of the i–th phase there are B_{i} black balls. These balls from a random subset of [1 . . n]. In order to lower bound the expected cost of the i–th phase we change the rules of the game in B’s favor. At the end of the i–th phase, player B selects B_{i}/2 black balls and declares that A’s moves in the i–th phase involving these balls are free of charge. We now distinguish two cases. For the remaining B_{i}/2 balls which are black at the end of the i–th phase, either at least B_{i}/4 were relabeled by B before A selects the ball, or this is not the case. In the former case, the cost of B’s moves is clearly lower bounded by the sum of the B smallest distances between black balls. The expected value of this sum is Ω(n). In the latter case, the cost of A’s moves is Ω(n).

References

[BDS^{+}] J.D. Boissonnat, O. Devillers, R. Schott, M. Teillaud, and M. Yvinec. Applications of random sampling to on-line algorithms in computational geometry. Discrete and Computational Geometry. To be published. Available as Technical Report INRIA 1285. Abstract published in IMACS 91 in Dublin.

[CEG^{+}91] B. Chazelle, H. Edelsbrunner, L.J. Guibas, M. Sharir, and J. Snoeyink. Computing a face in an arrangement of line segments. 2nd Ann. ACM-SIAM Symp. on Discrete Algorithms, pages 441 – 448, 1991.

[CS89] K. L. Clarkson and P. W. Shor. Applications of random sampling in computational geometry, II. Journal of Discrete and Computational Geometry, pages 387–421, 1989.

[Dev] O. Devillers. Randomization yields simple o(n log^{⋆} n) algorithms for difficult ω(n) problems. International Journal on Computational Geometry and Aplications. To be published. Full paper available as Technical Report INRIA 1412. Abstract published in the Third Canadian Conference on Computational Geometry 1991 in Vancouver.

[DMT91] O. Devillers, S. Meiser, and M. Teillaud. Fully dynamic Delaunay triangulation in logarithmic expected time per operation. In WADS 91, volume LNCS 519. Springer Verlag, 1991. Full version available as Technical Report INRIA 1349.

[Ede87] H. Edelsbrunner. Algorithms in Combinatorial Geometry. Springer Berlin-Heidelberg, 1987.

[GKS90] L.J. Guibas, D.E. Knuth, and M. Sharir. Randomized incremental construction of Delaunay and Voronoi diagrams. Proc. of ICALP, pages 414 – 431, 1990. also to appear in Algorithmica.

[MMO91] K. Mehlhorn, St. Meiser, and C. Ò’Dunlaing. On the construction of abstract voronoi diagrams. Discrete Comput. Geom., 6:211 – 224, 1991.

[MN90] K. Mehlhorn and St. Näher. Bounded ordered dictionaries in O(log log n) time and O(n) space. Information Processing Letters, 35:183 – 189, 1990.

[Mul88] K. Mulmuley. A fast planar partition algorithm, I. Proc. of the 29th FOCS, pages 580–589, 1988.

[Mul91a] K. Mulmuley. Randomized multidimensional search trees: dynamic sampling. Proc. ACM Symposium on Computational Geometry, 1991.

[Mul91b] K. Mulmuley. Randomized multidimensional search trees: further results in dynamic sampling. 32nd IEEE FOCS, pages 216 – 227, 1991.

[Mul91c] K. Mulmuley. Randomized multidimensional search trees: Lazy balancing and dynamic shuffling. 32nd IEEE FOCS, pages 180 – 194, 1991.

[Sch91] O. Schwarzkopf. Dynamic maintenance of geometric structures made easy. 32nd IEEE FOCS, pages 197 – 206, 1991.

[Sei90] R. Seidel. Linear programming and convex hulls made easy. Proc. 6th Ann. ACM Symp. Computational Geometry, pages 211 – 215, 1990.

[Sei91] R. Seidel. A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons. Computational Geometry: Theory and Applications, 1:51 – 64, 1991.

[Sto87] A. J. Stolfi. Oriented projective geometry (extended abstract). Proceedings of the 3rd Annual ACM Symp. on Computational Geometry, pages 76–85, 1987.

[vKZ77] P. van Emde Boas, R. Kaas, and E. Zijlstra. Design and implementation of an efficient priority queue. Math. Systems Theory, 10:99 – 127, 1977.