Self-improving Algorithms for Delaunay Triangulations

Kenneth L. Clarkson

IBM Almaden Research Center

C. Seshadhri

Dept. of Computer Science Princeton University

July 22, 2008

Abstract

We study the problem of two-dimensional Delaunay triangulation in the self-improving algorithms model [1]. We assume that the n points of the input each come from an independent, unknown, and arbitrary distribution. The first phase of our algorithm builds data structures that store relevant information about the input distribution. The second phase uses these data structures to efficiently compute the Delaunay triangulation of the input. The running time of our algorithm matches the information-theoretic lower bound for the given input distribution, implying that if the input distribution has low entropy, then our algorithm beats the standard Ω(n log n) bound for computing Delaunay triangulations.

Our algorithm and analysis use a variety of techniques: ε-nets for disks, entropy-optimal pointlocation data structures, linear-time splitting of Delaunay triangulations, and information-theoretic arguments.

1 Introduction

Data in the real world often has some structure. Suppose the inputs to an algorithm are generated by a probability distribution. Even if the distribution cannot be represented by a closed form expression, it may have some structural properties which can be exploited to speed up the algorithm. A standard algorithm will not be able to exploit this extra structure.

The model of self-improving algorithms was defined by Ailon et al. [1] to capture these scenarios. Suppose we wish to compute a function f on a sequence of inputs I_{1}, I_{2}, ⋯ which are being generated from an unknown and arbitrary time-invariant distribution D. A self-improving algorithm for computing f initially only gives standard worst-case guarantees. As it handles more and more inputs, it learns about the distribution. Eventually, it tunes itself to be more efficient for D, and may beat the worst-case running time. Self-improving algorithms have two phases: the initial learning phase, where the algorithm learns about D and builds data structures storing this information, and the limiting phase, where the algorithm uses the information obtained to speed up the running time. The main parameters of a self-improving algorithm are the number of rounds (number of problem instances) in the learning phase, the space used to store information about the distribution, and the running time in the limiting phase.

The basic intuition is that if D has low entropy, then the self-improving algorithm should be able to make a significant improvement. Of course, it may take too long to learn D as a whole, or even to learn a reasonable approximation of it. The challenge is to learn as little as possible about D and still glean enough to improve the running time. If the entropy of the input distribution for a sorting problem is low, for example, then a self-improving algorithm for sorting the resulting input will do better than the standard Ω(n log n) lower bound.

We take the concept of self-improving algorithms to the geometric realm, and the problem of computing Delaunay triangulations. The most relevant result is that of [1], where a self-improving sorter was constructed. We borrow some ideas from there, and use geometric techniques to design a self-improving algorithm for Delaunay triangulations. In this new mode of algorithmic analysis, our algorithm is optimal, as its running time in the limiting phase matches the information-theoretic lower bound for computing the output over inputs from a fixed distribution.

We now formally define the problem. Let

I := (x_{1}, ⋯, x_{n})

denote an input instance, where each x_{i} is a point in the plane, generated by a point distribution D_{i}. The distributions D_{i} are arbitrary, and may be continuous, although we never explicitly use such a condition. Each x_{i} is independent of the others, and so the input I is drawn from the product distribution D := ∏_{i} D_{i}. In each round, a new input I is drawn from D, and we wish to compute the Delaunay triangulation T (I) of I. We use the comparison model, so any operation consists of evaluating a polynomial at some point (more details about this are given in Section 3). Although it is not critical, for the sake of simplicity, we will assume that the points of I are in general position, which is true with probability one when all the D_{i}’s are continuous.

The distribution D also induces a (discrete) distribution on the set of Delaunay triangulations, viewed as labeled graphs on the vertex set [1, n]. Consider the entropy of this distribution: for each graph G on [1, n], let p_{G} be the probability that it represents the Delaunay triangulation of I ∈_{R} D. Let the output entropy H(T (I)) := − ∑_{G} p_{G} log p_{G}. By information-theoretic arguments, this quantity is a lower bound on the expected time required by any comparison-based algorithm to compute the Delaunay triangulation of I ∈_{R} D. An optimal algorithm will be one that has an expected running time of O(H(T (I)) + n).

Our main result is the following.

Theorem 1.1 For inputs I_{1}, I_{2}, … drawn from the product distribution D = ∏_{i} D_{i}, and for any constant ε > 0, there is a self-improving algorithm for finding the Delaunay triangulations of the I_{j} that has a learning phase of O(n^{ε}) rounds and uses O(n^{1+ε}) space ^{1}. The limiting-phase running time is O(ε^{−1}(H(T (I)) + n)), and therefore optimal.

Why is the independence of the D_{i}’s important? A lower bound from [1] shows that any optimal selfimproving sorter that handles all possible distributions requires exponential space. From the reduction of sorting to Delaunay triangulations, the following is an immediate corollary of Lemma 2.1 in [1].

Corollary 1.2 There is an input distribution D such that any self-improving algorithm computing the Delaunay triangulation of inputs from D in O(H(D) + n) limiting running time requires Ω(2^{n}) space.

Furthermore, by Lemma 2.5 of [1], the time-space tradeoff we provide is essentially optimal.

2 The algorithm

We describe the algorithm in two parts. The first part explains the learning phase and the data structures that are constructed. The second part explains how these data structures are used to speed up the computation in the limiting phase. The expected running time will be expressed in terms of certain parameters of the data structures obtained in the learning phase. In the next section, we will prove that these parameters are comparable to the output entropy H(D). We will assume in this section that the distributions D_{i} are known to us. Furthermore, the data structures described here will use O(n^{2}) space. Section 4 shows how to remove this assumption and give the space-time tradeoff bounds of Theorem 1.1.

2.1 Learning Phase

For each round in the learning phase, we use a standard algorithm to compute the output Delaunay triangulation. We also perform some extra computation to build some data structures that will allow speedup in the limiting phase. These data structures are easily described.

The learning phase is as follows. Take the first k := c log n input lists I_{1}, I_{2}, ⋯, I_{k}, where c is a sufficiently large constant. Merge them into one list S of kn = cn log n points. Setting ε := 1/n, find an ε-net V for the set of all open disks. In other words, find a set V ⊆ S such that for any open disk C that contains more than εkn = c log n points of S, C contains at least one point of V. Matousek, et al. show that [7] there exist ε-nets of size O(1/ε) for disks, where here O(1/ε) = O(n). Furthermore, a construction and analysis similar to that of Clarkson and Varadarajan [6] yields a randomized construction that takes n(log n)^{O(1)} expected time.

1The total time required for the learning phase is also O(n^{1+ε}).

We construct the Delaunay triangulation of V, which we denote by T (V). We build an optimal planar point location structure (called Γ) for T (V): given a point, we can find the triangle of T (V) that it lies in O(log n) time. Define the random variable t_{i} to be the triangle of T (V) that x_{i} falls into. Now let the entropy of t_{i} be H_{i}^{V}. If the probability that x_{i} falls in triangle t of T (V) is p_{i}^{t}, then H_{i}^{V} = − ∑_{t} p_{i}^{t} log p_{i}^{t}. For each i, we construct a search structure Γ_{i} of size O(n) that finds t_{i} in expected O(H_{i}^{V}) time. These Γ_{i}’s can be constructed using the results of Arya et al. [3], for which the number of primitive comparisons is H_{i}^{V} + o(H_{i}^{V})).

We will show that the triangles of T (V) do not contain many points of a new input I ∈_{R} D on the average. Consider a triangle t of T (V) and let C_{t} be its circumscribed Delaunay disk. Let X_{t} := |I ∩ C_{t}|, the random variable that is the number of points of I ∈_{R} D that fall inside C_{t}. Note that the randomness comes from the random distribution of S, and so V and T (V), as well as the randomness of I. We are interested in the expectation E_{I}[X_{t}] over I of X_{t}.

Claim 2.1 With probability at least 1 − 1/n^{3} over the construction of T (V), for every triangle t of T (V), E_{I}[X_{t}] = O(1).

Proof: Let the list of points S be s_{1}, ⋯, s_{kn}, the concatenation of I_{1} through I_{k}. Consider the triangle t with vertices s_{1}, s_{2}, s_{3}. Note that all the remaining kn − 3 points are chosen independently of these three, from some distribution D_{ℓ}. For each j ∈ [4, kn], let Y_{j}^{(t)} be the indicator variable for the event that s_{j} is inside C_{t}. Let Y^{(t)} = ∑_{j} Y_{j}^{(t)}. By the Chernoff bound, for any β ∈ (0, 1],

Pr[Y^{(t)} ≤ (1 − β)E[Y^{(t)}]] ≤ e^{−β^{2}E[Y^{(t)}]/2}

Setting β = 1/2, if E[Y^{(t)}] > 48 log n, then Y^{(t)} > 24 log n with probability at least 1 − n^{−6}. We can now consider any triangle generated by some triple of points s_{i}, s_{j}, s_{m}, for i, j, m ∈ [4, kn], and apply the same argument as above. Taking a union bound over all triples of the points in S, we obtain that with probability at least 1 − n^{−3}, for any triangle t generated by the points of S, if E[Y^{(t)}] > 48 log n, then Y^{(t)} > 24 log n. We henceforth assume that this event happens.

Consider a triangle t of T (V) and its circumcircle C_{t}. Since T (V) is Delaunay, C_{t} contains no point of V in its interior. Since V is a (1/n)-net for all disks with respect to S, C_{t} contains at most c log n points of S, that is, Y^{(t)} ≤ c log n. This implies that E[Y^{(t)}] = O(log n), as in the previous paragraph. Since E[Y^{(t)}] > (log n − 3)E_{I}[X_{t}], we obtain E_{I}[X_{t}] = O(1), as claimed. □

2.2 Limiting Phase

Suppose that we are done with the learning phase, and have T (V) with the property given in Claim 2.1: for every triangle t ∈ T (V), E_{I}[X_{t}] = O(1). We have reached the limiting phase where the algorithm is expected to compute the Delaunay triangulation with the optimal running time. We will prove the following lemma in this section.

Lemma 2.2 Using the data structures from the learning phase, and the properties of them that hold with probability 1 − O(1/n), in the limiting phase the Delaunay triangulation of input I can be generated in expected O(n + ∑_{i=1}^{n} H_{i}^{V}) time.

The algorithm, and the proof of this lemma, has two steps. In the first step, T (V) is used to quickly compute T (V ∪ I), with the time bounds of the lemma. In the second step, T (I) is computed from T (V ∪ I), using a randomized splitting algorithm proposed by Chazelle et al [5], whose Theorem 3 is as follows.

Theorem 2.3 Given a set of n points P and its Delaunay triangulation, for any partition of P into two disjoint subsets P_{1} and P_{2}, the Delaunay triangulations T (P_{1}) and T (P_{2}) can be computed in O(n) expected time, using a randomized algorithm.

The remainder of the proof of the lemma, and of this subsection, is devoted to showing that T (V ∪ I) can be computed in the time bound of the lemma. The algorithm is as follows. For each x_{i}, we use Γ_{i} to find the triangle t_{i} of T (V) that contains it. By the arguments given in the previous section, this takes time O(∑_{i=1}^{n} H_{i}^{V}). We now need to argue that given the t_{i}’s, the Delaunay triangulation T (V ∪ I) can be computed in expected linear time. For each x_{i}, we walk through T (V) and find all the Delaunay disks of T (V) that contain x_{i}, as in incremental constructions of Delaunay triangulations. This is done by breadth-first search of the dual graph of T (V), starting from t_{i}. Let S_{i} denote the set of circumcircles containing x_{i}. The following claim implies that this procedure will work.

Claim 2.4 The set of t ∈ T (V) with C_{t} ∈ S_{i} is a connected set in the dual graph of T (V).

Proof: Omitted.

Claim 2.5 Given all t_{i}’s, all S_{i} sets can be found in expected O(n) time.

Proof: To find all circles containing x_{i}, do a breadth-first search from t_{i}. For any triangle t encountered, check if C_{t} contains x_{i}. If it does not, then we do not look at the neighbors of t. By Claim 2.4, we will visit all C_{t}’s that contain x_{i}. The time taken to find S_{i} is O(|S_{i}|). The total time taken to find all S_{t}’s (once all the t_{i}’s are found) is O(∑_{i=1}^{n} |S_{i}|). Define the indicator function χ(t, x_{i}) that takes value 1 if x_{i} ∈ t and zero otherwise. We have

∑_{i=1}^{n} |S_{i}| = ∑_{i=1}^{n} ∑_{t∈T (V)} χ(t, x_{i}) = ∑_{t∈T (V)} ∑_{i=1}^{n} χ(t, x_{i}) = ∑_{t} X_{t}.

Therefore, by Claim 2.1,

E[∑_{i=1}^{n} |S_{i}|] = E[∑_{t} X_{t}] = ∑_{t} E[X_{t}] = O(n).

This implies that all S_{i}’s can be found in expected linear time. □

Our aim is to build the Delaunay triangulation of V ∪ I in linear time using the S_{i} sets. This is done by a standard incremental construction where the x_{i}’s are added in order x_{1}, x_{2}, ⋯, x_{n}. We will show how we can get the set of edges that each x_{i} will “kill” using the S_{i} sets. We will assume that given any triangle t, we can get all the S_{i} sets that t belongs to.

Let V_{i} := V ∪ {x_{1}, ⋯, x_{i}}. When we add x_{1}, the edges of T (V) that will be affected are the edges of triangles in S_{1}. Therefore, T (V_{1}) can be obtained in O(|S_{1}|) time. Now suppose we have T (V_{i−1}) and we add x_{i}. Again, we can show that if some edge from T (V) is affected, it must be an edge of S_{i}.

Claim 2.6 When x_{i} is added to T (V_{i−1}), suppose that edge e is removed. If the endpoints of e are both in V, then e is an edge of some triangle in S_{i}.

This is proved in the appendix.

The claim above shows that only O(|S_{i}|) time is required to find edges from T (V) that are removed. But now, we have the additional problem of finding affected edges which may not have an endpoint in V, and therefore are not present in T (V).

Claim 2.7 Suppose e has an endpoint in I. There is an edge f ∈ T (V) such that, for the two triangles t, t′ incident on f, the point x_{i} and the endpoints of e lie in either C_{t} or C_{t′}.

The proof is given in the appendix.

This now gives us a method of finding edges of T (V_{i−1}) affected by the addition of x_{i}. Take a triangle t ∈ S_{i} and choose an edge e of t (for ease of notation, we will say e ∈ t). Let the neighbor of t incident to e be t′. Look at the points in {x_{1}, ⋯, x_{i−1}} that are in C_{t} and C_{t′}, and take the edges of T (V_{i−1}) between them. These are the edges that need to be checked.

Claim 2.8 Given all S_{i} sets and T (V), T (V_{n}) can be generated in expected linear time.

Proof: The total time taken to handle all edges of T (V) that get killed is E[∑_{i=1}^{n} |S_{i}|] = O(n). Consider some t ∈ T (V) and edge e of t. Let t^{e} ∈ T (V) be incident to e. The random variable Z_{t,e} is set to be X_{t}X_{t^{e}}. By Claim 2.7, the total time to find all (other) affected edges is bounded above by

∑_{i=1}^{n} ∑_{t∈S_{i}} ∑_{e∈t} Z_{t,e}.

For a triangle t, we define the indicator random variable χ(t, i), as before, for the event that x_{i} falls in C_{t}. Thus, X_{t} = ∑_{i=1}^{n} χ(t, i).

∑_{i=1}^{n} ∑_{t∈S_{i}} ∑_{e∈t} Z_{t,e} = ∑_{i=1}^{n} ∑_{t} χ(t, i) ∑_{e∈t} X_{t}X_{t^{e}}

= ∑_{i=1}^{n} ∑_{t} ∑_{e∈t} χ(t, i)X_{t}X_{t^{e}},

and

E[χ(t, i)X_{t}X_{t^{e}}] = E[χ(t, i) ∑_{j=1}^{n} χ(t, j) ∑_{k=1}^{n} χ(t^{e}, k)]

= ∑_{j=1}^{n} E[χ(t, i)χ(t, j)χ(t^{e}, j)]

+ ∑_{j≠k} E[χ(t, i)χ(t, j)χ(t^{e}, k)]

Since χ(t, i) is an indicator, χ(t, j)χ(t^{e}, j) ≤ χ(t, j). For j ≠ k, χ(t, j) and χ(t^{e}, k) are independent. For the second summation in the equation above, we can separate out the case i = j and i = k.

E[χ(t, i)X_{t}X_{t^{e}}]

= ∑_{j=1}^{n} E[χ(t, i)χ(t, j)χ(t^{e}, j)] + ∑_{k≠i} E[χ(t, i)^{2}χ(t^{e}, k)]

+ ∑_{j≠i} E[χ(t, i)χ(t^{e}, i)χ(t, j)]

+ ∑_{i≠j≠k} E[χ(t, i)χ(t, j)χ(t^{e}, k)]

≤ ∑_{j=1}^{n} E[χ(t, i)χ(t, j)] + E[χ(t, i)] ∑_{k≠i} E[χ(t^{e}, k)]

+ ∑_{j≠i} E[χ(t, i)χ(t, j)]

+ E[χ(t, i)] ∑_{i≠j≠k} E[χ(t, j)]E[χ(t^{e}, k)]

= E[χ(t, i)] + E[χ(t, i)] ∑_{j≠i} E[χ(t, j)]

+ E[χ(t, i)] ∑_{k≠i} E[χ(t^{e}, k)]

+ E[χ(t, i)] ∑_{j≠i} E[χ(t, j)]

+ E[χ(t, i)] ∑_{i≠j≠k} E[χ(t, j)]E[χ(t^{e}, k)]

≤ E[χ(t, i)] + 2E[χ(t, i)] ∑_{j=1}^{n} E[χ(t, j)]

+ E[χ(t, i)] ∑_{k=1}^{n} E[χ(t^{e}, k)]

+ E[χ(t, i)](∑_{j=1}^{n} E[χ(t, j)])(∑_{k=1}^{n} E[χ(t^{e}, k)])

= E[χ(t, i)](1 + 2E[X_{t}] + E[X_{t^{e}}] + E[X_{t}]E[X_{t^{e}}])

By Claim 2.1, we get that E[χ(t, i)X_{t}X_{t^{e}}] ≤ αE[χ(t, i)], for some fixed constant α. The expected running time is bounded by

E[∑_{i=1}^{n} ∑_{t∈S_{i}} ∑_{e∈t} Z_{t,e}] = ∑_{i=1}^{n} ∑_{t} ∑_{e∈t} E[χ(t, i)X_{t}X_{t^{e}}]

≤ α ∑_{i=1}^{n} ∑_{t} ∑_{e∈t} E[χ(t, i)]

= 3α ∑_{i=1}^{n} E[∑_{t} χ(t, i)]

= 3α ∑_{i=1}^{n} E[|S_{i}|] = O(n)
□

With this claim, it follows that T (V_{n}) can be computed in expected O(n + ∑_{i=1}^{n} H_{i}^{V}) time, and hence, as discussed at the beginning of this subsection, Lemma 2.2 follows.

3 Limiting Phase Optimality

In this section, we prove that the running time bound in Lemma 2.2 is indeed optimal. Before we get into the analysis of the various entropies that represent the running time, it is important to clarify the model of computation. We are using comparison based algorithms, where a single step (or “comparison”) involves evaluating a point (z_{1}, z_{2}, ⋯, z_{d}) ∈ ℝ^{d} (for constant d) at some polynomial f(z_{1}, z_{2}, ⋯, z_{d}) : ℝ^{d} → ℝ and checking if the result is positive or negative. Based on this result, the algorithm chooses the next comparison to make. An algorithm can be completely represented by a decision tree, with each node representing some comparison. In this model, we get an information-theoretic lower bound of H(T (I)) for computing the Delaunay triangulation of input I ∈_{R} D.

Recall that by Lemma 2.2, the running time of the our algorithm is expected O(n + ∑_{i} H_{i}^{V}). The aim of this section is to prove the optimality of the algorithm by the following theorem.

Theorem 3.1 For H_{i}^{V} the entropy of the triangle t_{i} of T (V) containing x_{i}, and H(T (I)) the entropy of the Delaunay triangulation of I, considered as labeled graph,

∑_{i} H_{i}^{V} = O(H(T (I)) + n).

This theorem will be proven through a chain of lemmas, which will eventually connect ∑_{i=1}^{n} H_{i}^{V} to H(T (I)). Note that V is a fixed set and there is no randomness in T (V). As a result, for the sake of information theory bounds, we can assume that T (V) is known in advance: indeed, any computation whatsoever can be done in advance on the points in V and is not charged as a comparison.

The chain of lemmas begins with H(T (V_{n})), which is bounded above by O(H(T (I) + n) in the next lemma. The entropy H(T (V_{n})) is used to bound ∑_{i} E[H_{i}] in the following lemma, where H_{i} is the entropy of w_{i}, the triangle of T (V_{i−1}) that contains x_{i}. After some preliminary lemmas, the final lemma in the chain uses ∑_{i} E[H_{i}] to bound ∑_{i} H_{i}^{V}, as needed for the theorem.

By analogy to H(T (I)), let H(T (V_{n})) be the entropy of T (V_{n}) as a labeled graph, under the distribution induced by that of I. (Recall that V_{n} := V ∪ I.) The entropy H(T (V_{n})) is a lower bound for the expected running time of any comparison-based algorithm that computes T (V_{n}).

The first lemma in the chain is the following.

Lemma 3.2

H(T (V_{n})) = O(H(T (I)) + n).

Proof: Using Chazelle’s linear-time algorithm to compute the intersection of two three-dimensional convex polyhedra [4], we can compute T (V_{n}) in O(n) time, given T (V) and T (I). Suppose we represent every graph induced by a Delaunay triangulation on n points by some string, denoted by s(T). By information theory, there exists some string encoding such that E[|s(T (I))|] = O(H(T (I))). Suppose, for input I, we are given the string s(T (I)), so we can uniquely identify T (I). Now, we use the linear-time algorithm to compute T (V_{n}). Obviously, this algorithm only performs O(n) comparisons. Therefore, the output T (V ∪ I) can be uniquely identified by s(T (I)) and cn more bits, for some constant c. By definition, E[|s(T (I))| + cn] ≥ H(T (V_{n})). This completes the proof. □

Let us consider an incremental construction of T (V_{n}). At the ith step, x_{i} is added to T (V_{i−1}). We can consider a random process associated with this step. The points x_{1}, ⋯, x_{i−1} are already fixed, thereby fixing T (V_{i−1}). We can consider the entropy of the random variable w_{i} that is the triangle of T (V_{i−1}) in which x_{i} falls. More precisely, we define

H_{i}^{T (V_{i−1})} := H(w_{i}) = − ∑_{t∈T (V_{i−1})} p(i, t) log p(i, t)

p(i, t) is the probability that x_{i} lies in t. Note that this entropy itself is a random variable, since T (V_{i−1}) depends on x_{1}, ⋯, x_{i−1} which are randomly chosen. But w_{i} is independent of this randomness (since the distributions D_{i} are all independent). Therefore, we can take the expectation over the random choices {x_{1}, ⋯, x_{i−1}}, E_{x_{1},··· ,x_{i−1}}[H_{i}^{T (V_{i−1})}]. Again, let us explain what this means. Given any set of points x_{1}, ⋯, x_{i−1}, we can define the entropy H_{i}^{T (V_{i−1})}. Now, because the randomness of w_{i} only depends on the randomness of x_{i}, w_{i} is independent of x_{1}, ⋯, x_{i−1}. Obviously, H_{i}^{T (V_{i−1})} is a function of x_{1}, ⋯, x_{i−1}. We take the expectation over the random choices of x_{1}, ⋯, x_{i−1} to get E[H_{i}^{T (V_{i−1})}]. For clarity, we drop the subscripts and denote this by E[H_{i}].

In the next lemma, we relate the entropy of this incremental procedure of constructing T (V_{n}) to the actual entropy of the T (V_{n}).

Lemma 3.3

∑_{i} E[H_{i}] = O(H(T (V_{n})) + n)

To prove the lemma, we need a claim and a lemma. The claim follows from the proof of Claim 2.8, and the lemma is proven in the appendix.

Claim 3.4 For all j ≤ i, the expected degree of x_{j} in T (V_{i}) is O(E[|S_{j}|]).

Lemma 3.5

H(w_{1}, ⋯, w_{n}) ≥ ∑_{i=1}^{n} E[H_{i}]

Here H(w_{1}, ⋯, w_{n}) is the joint entropy of all w_{1}, ⋯, w_{n}, and a lower bound on the expected length of any string representation of w_{1}, ⋯, w_{n}. Proof: (of Lemma 3.3) Before giving the details of the proof, let us first sketch out the main idea. Suppose all the random choices x_{1}, ⋯, x_{n} have been made. We would like to argue that if we know T (V_{n}), then in linear time we can determine the w_{i}’s for all i. This will be done by a procedure that goes backwards: it first removes x_{n}, and then computes the Delaunay triangulation T (V_{n−1}). This can be done in time linear in the degree of x_{n} [2]. The triangle w_{n} can be determined in time linear in the degree of x_{n}. Now, we remove x_{n−1} and so on, thereby finding all w_{i}’s. It seems that by a standard backwards analysis argument, we should remove the x_{i}’s in random order. By a planarity argument, we should get that the expected degree (over the random order) is constant at every step. But because we remove only the points in I, which is a strict subset of V_{n}, this argument will not hold.

However, using the properties of V and the randomness of I, we can still argue that these degrees will be expected constant. From Claim 3.4, it is easy to see that we can get the w_{i}’s in O(∑_{i} E[|S_{i}|]) time. Let us now apply an argument similar to that in Lemma 3.2. Let there be a string representation s(T (V_{n})) for each possible T (V_{n}). By definition of entropy, we can assume that E[|s(T (V_{n}))|] = O(H(T (V_{n}))). Using the procedure described above, we can uniquely identify w_{1}, ⋯, w_{n} by a string of expected length E[|s(T (V_{n}))|] + O(E[∑_{i} |S_{i}|]) = O(H(T (V_{n})) + n).

The proof now follows by Lemma 3.5, since H(w_{1}, ⋯, w_{n}) is no more than E_{I}[|s(T (V_{n}))|. □

We now come to the final lemma in our chain of entropy inequalities.

Lemma 3.6

∑_{i} H_{i}^{V} = O(∑_{i} E[H_{i}] + n)

Proof: Consider x_{1}, ⋯, x_{i−1} to be chosen, fixing the triangulation T (V_{i−1}). The entropy H_{i} is now well defined. As before, w_{i} ∈ T (V_{i−1}) and t_{i} ∈ T (V) are the triangles that x_{i} falls into. We will describe a procedure that given w_{i} finds t_{i} using O(|S_{i}|) comparisons. First, we look at the Delaunay triangulations as 3-dimensional polytopes. By projecting onto the paraboloid z = x^{2} + y^{2}, each point of the Delaunay triangulation is represented by a halfspace in 3-dimensions. Every vertex of the polytope corresponds to a Delaunay triangle (or disk). Abusing notation, T (V) and T (V_{i−1}) are going to be the respective polytopes. We start by tetrahedralizing T (V). Since T (V_{i−1}) is completely contained in T (V), for every vertex of T (V_{i−1}), we can determine a tetrahedron of T (V) that contains it (maybe on the boundary). Note that all of this can be done before we look at point x_{k}. Given w_{i}, we can determine the tetrahedron that it lies in without any comparisons. Since the triangle w_{i} will certainly be destroyed on the addition of x_{i}, the vertex corresponding to w_{i} (in the polytope) will be removed by the addition of the plane x_{i}. Obviously, there is some vertex of the tetrahedron would also be removed by the addition of x_{i} to T (V). In a constant number of queries, this vertex can be determined. Now, let us go back to the Delaunay triangulations. This vertex corresponds to some Delaunay disk of T (V) killed by x_{i}. By doing a walk through T (V), we can find t_{i} in O(|S_{i}|) time. This implies that

H_{i}^{V} ≤ H_{i} + O(|S_{i}| + 1).

Taking expectations over I and summing,

∑_{i} H_{i}^{V} ≤ ∑_{i} E[H_{i}] + O(E[∑_{i} |S_{i}|] + n) ≤ ∑_{i} E[H_{i}] + O(n).

□

As discussed above, Theorem 3.1 now follows by combining Lemmas 3.2, 3.3, and 3.6.

4 The time-space tradeoff

We show how to remove the assumption that we have prior knowledge of the D_{i}’s (to build the search trees Γ_{i}) and prove the time-space tradeoff given in Theorem 1.1. These techniques are identical to those used in [1] for their self-improving sorter. Let ε > 0 be any constant. The first O(log n) rounds of the learning phase are used as before to construct the Delaunay triangulation T (V). To construct the tree Γ_{i}, we would need to know the exact probability with which x_{i} falls in every triangle of T (V). Since these probabilities cannot be determined in a sublinear number of learning rounds, we build some suitable approximations for these search structures. We first build a standard search structure Γ over the triangles of T (V). Given a point x, we can find the triangle of T (V) that contains x in O(log n) time.

The learning phase goes on for O(n^{ε} log n) rounds. The main trick is to observe that (up to constant factors), the only probabilities that are relevant are those that are > n^{−ε}. In each round, for each x_{i}, we record the triangle of T (V) that x_{i} falls into. At the end of O(n^{ε} log n) rounds, we take the set R_{i} of triangles such that for t ∈ R_{i}, x_{i} was in t for at least Ω(log n) rounds. We remind the reader that p_{i}^{t} is the probability that x_{i} lies in triangle t. For every triangle in R_{i}, we have an estimate of the probability p̂_{i}^{t} (obtained by simply taking the total number of times that x_{i} lay in t, divided by the total number of rounds). By a standard Chernoff bound argument, for all t ∈ R_{i}, p̂_{i}^{t} = Θ(p_{i}^{t}). Furthermore, for any triangle t, if p_{i}^{t} = Ω(n^{−ε}), then t ∈ R_{i}.

For each x_{i}, we build the approximate search structure Γ_{i}. Consider the following probability distribution p̄_{i} over the triangles of T (V): if t ∈ R_{i}, set p̄_{i}^{t} := p̂_{i}^{t}/N_{i}, where N_{i} := ∑_{t∈R_{i}} p̂_{i}^{t}, and otherwise p̄_{i}^{t} := 0. Using the construction of [3], we can build the optimal planar point location structure Γ_{i} according to the distribution p̄_{i}. The limiting phase uses these structures to find t_{i} for every x_{i}: given x_{i}, we use Γ_{i} to search for it. If the search does not terminate in log n steps or Γ_{i} fails to find t_{i} (since t_{i} ∉ R_{i}), then we use the standard search structure, Γ, to find t_{i}. Therefore, we are guaranteed to find t_{i} in O(log n) time. Without loss of generality, we can assume that each Γ_{i} deals with only n^{ε} triangles (and therefore, a planar subdivision of size n^{ε}). By the bounds given in [3], each Γ_{i} can be constructed with size n^{ε} in n^{ε} log n time. The total space is bounded by n^{1+ε} and the time required to build them is at most n^{1+ε} log n.

Let s_{i}^{t} denote the time to search for x_{i} given that x_{i} ∈ t. By the properties of Γ_{i}, and noting that N_{i} ≤ 1,

∑_{t∈R_{i}} p̄_{i}^{t}s_{i}^{t} = ∑_{t∈R_{i}} p̄_{i}^{t} log(1/p̄_{i}^{t})
= N_{i}^{−1} ∑_{t∈R_{i}} p̂_{i}^{t} log(N_{i}/p̂_{i}^{t})
= N_{i}^{−1}[ ∑_{t∈R_{i}} p̂_{i}^{t} log N_{i} − ∑_{t∈R_{i}} p̂_{i}^{t} log p̂_{i}^{t}]
≤ −N_{i}^{−1} ∑_{t∈R_{i}} p̂_{i}^{t} log p̂_{i}^{t}
= O(N_{i}^{−1}(− ∑_{t∈R_{i}} p_{i}^{t} log p_{i}^{t} + 1))

We now bound the expected search time for x_{i}.

∑_{t} p_{i}^{t}s_{i}^{t} = ∑_{t∈R_{i}} p_{i}^{t}s_{i}^{t} + ∑_{t∉R_{i}} p_{i}^{t}s_{i}^{t}
= O( ∑_{t∈R_{i}} p̂_{i}^{t}s_{i}^{t} + ∑_{t∉R_{i}} p_{i}^{t} log n)
= O(N_{i} ∑_{t∈R_{i}} p̄_{i}^{t}s_{i}^{t} + ∑_{t∉R_{i}} p_{i}^{t} log n)

Noting that for t ∉ R_{i}, p_{i}^{t} = O(n^{−ε}) and therefore log p_{i}^{t} ≤ −ε log n + O(1), and so

∑_{t}p_{i}^{t}s_{i}^{t}

= O((− ∑_{t∈R_{i}} p_{i}^{t} log p_{i}^{t} + 1) + ∑_{t∉R_{i}} p_{i}^{t}ε^{−1}(− log p_{i}^{t} + 1))

= O(ε^{−1}(− ∑_{t} p_{i}^{t} log p_{i}^{t} + 1))

= O(ε^{−1}(H_{i}^{V} + 1))

The total expected search time is O(ε^{−1}(∑_{i} H_{i}^{V} + n)). By the analysis of Section 2 and Theorem 3.1, we have that the expected running time in the limiting phase is O(ε^{−1}(H(D) + n)). This completes the proof of Theorem 1.1.

References

[1] Ailon, N., Chazelle, B., Comandur, S., Liu, D., Self-Improving Algorithms, Proc. 17th SODA (2006), 261–270.

[2] Aggarwal, A., Guibas, L., Saxe, J., Shor, P., A Linear Time Algorithm for Computing the Voronoi Diagram of a Convex Polygon, Discrete and Computational Geometry 4, 1989, 591–604.

[3] Arya, S., Malamatos, T., Mount, D. M., Wong, K.-C. Optimal Expected-Case Planar Point Location, SIAM J. Comput. 37, 2007, 584–610

[4] Chazelle, B., An Optimal Algorithm for Intersecting Three-Dimensional Convex Polyhedra, SIAM J. Computing 21, 1992, 671–696.

[5] Chazelle, B., Devillers, O.,Hurtado, F., Mora, M., Sacristan, V., Teillaud, M. Splitting a Delaunay Triangulation in Linear Time, Algorithmica 34, 2002, 39–46.

[6] Clarkson, K., Varadarajan, K. Improved Approximation Algorithms for Geometric Set Cover Discrete and Computation Geometry 37, 2007, 43–58.

[7] Matousek, J., Seidel, R., Welzl, E. How to Net a Lot with Little: Small epsilon-Nets for Disks and Halfspaces, Proc. 6th SOCG (1990), 16–22.

A Proofs for Section 2.2

PSfrag replacements

t
e
x_{i}
y
t′

Figure 1:

Proof: (Claim 2.6) The edge e must be an edge in T (V). Also, e is an edge of triangle t in T (V_{i−1}). Refer to Figure 1. The point x_{i} is in the sector bounded by C_{t} and e. Since e ∈ T (V), there must be a point y ∈ V such that e and y form a triangle t′ of T (V) and x_{i} and y are on the same side of e. The point y cannot be inside C_{t}, since t is a Delaunay triangle of T (V_{i−1}). Therefore, the angle subtended by y at e is smaller than that of x_{i}. The circle C_{t′} must contain x_{i} and t′ ∈ S_{i}. □

Proof: (Claim 2.7) Suppose some edge e in triangle t ∈ T (V_{i−1}) is killed by x_{i}. We will denote the vertices of t by u_{1}, u_{2}, and u_{3}, and for ease of notation, we will denote x_{i} by u_{4}. The point x_{i} is inside C_{t}. Consider the set of edges of T (V) that intersect C_{t}. We can impose a natural linear ordering on these edges. If none of these edges separate the set points U = {u_{1}, ⋯, u_{4}}, then they all lie in a triangle t of T (V).

PSfrag replacements

C
C_{t}
f
f′

Figure 2:

Consider the first edge f that separates U into U_{ℓ} and U_{r}. Refer to Figure 2. Assume that the next edge after f to the right (in the ordering) that intersects C_{t} does not separate U. Let the two triangles of T (V) that share f as an edge be t_{ℓ}, t_{r} (the left and right triangles). The triangle t_{r} contains U_{r}. Let C be the circle tangential to C at the left of f and having f as a chord. (Note that if f is actually an edge of t, then C_{t} and C are just the same, and we will end up with Claim 2.6.) If the vertex of t_{ℓ} not on f lies outside C, then C_{t_{ℓ}} will contain all of C_{t} which lies to the left of f. This implies that C_{t_{ℓ}} contains U_{ℓ}. The situation is as follows: triangles t_{ℓ} and t_{r} in T (V) share edge f. Edge f divides U into U_{ℓ} and U_{r} and they are contained in C_{t_{ℓ}} and C_{t_{r}}, respectively, proving the claim (for this case).

Suppose the third vertex of t_{ℓ} is inside C. The triangle t_{ℓ} is shown by the dashed triangle in Figure 2 to the left of f. Let the angle to f be θ_{ℓ}. Let the angle subtended by any point in the right part of C_{t} be θ_{r}. Note that θ_{ℓ} + θ_{r} > π. Therefore, the circle C_{t_{ℓ}} will contain the right part of C_{t} (and, as a result, U_{r}).

The edge f′ is in T (V) and intersects C_{t}. Also, f′ is larger than f in the ordering of edges. If f′ does not separate U, then C_{t_{ℓ}} must contain U_{ℓ} and we are done. If not, then suppose f′ divides U into U′_{ℓ} and U′_{r}. The triangle t_{ℓ} is actually to the right of f′ and C_{t_{ℓ}} contains U′_{r}. This leaves us in a situation analogous to f: the circumcircle of triangle to the right of f′ contains all points in U to the right of f′. Therefore, we can apply the same argument as above: either we will stop, getting our desired triangles, or we will move to the edge to the right of f′. □

B Proof for Lemma 3.5

Proof: (Lemma 3.5) We will prove by induction on k that H(w_{1}, ⋯, w_{k}) ≥ ∑_{i=1}^{k} E[H_{i}]. Recall that w_{k} is the triangle of T (V_{k−1}) that contains x_{k}. The claim is a consequence of the independence of the x_{i}’s. The reason why we cannot immediately use independence is that the random variable w_{i} does depend on the choices of x_{1}, ⋯, x_{k−1}, because w_{k} depends on T (V_{k−1}), which depends on x_{1}, ⋯, x_{k−1}. In some sense, we are just stating a well known fact about conditional entropies, but this small technical problem forces us to reprove it for our setting. We proceed with a proof by induction.

base case: For k = 1, H(w_{1}) = H_{1} (note that H_{1} is not a random variable).

induction step: Assume the claim is true up to k − 1. For any triangle t (which is specified by a triple of vertex labels), let p(i, t) be the probability that x_{i} falls in t. Suppose that x_{1}, ⋯, x_{k−1} are fixed. We have

H_{k+1} = − ∑_{t∈T (V_{k−1})} p(k, t) log p(k, t).

Let γ(k−1, t) be the indicator variable of the event that T (V_{k−1}) has triangle t. This is a random variable, depending on x_{1}, ⋯, x_{k−1}. Removing the assumption that x_{1}, ⋯, x_{k−1} are fixed, we take the expectation of H_{k}:

E[H_{k}] = −E[∑_{t} γ(k − 1, t)p(k, t) log p(k, t)]
= − ∑_{t} E[γ(k − 1, t)]p(k, t) log p(k, t)

Consider some sequence of triangles Δ_{k} = ⟨t_{1}, ⋯, t_{k}⟩. For i ≤ k, let E_{i}(Δ) denote the event that w_{1} = t_{1}, w_{2} = t_{2}, ⋯, w_{i−1} = t_{i−1}.

Pr[E_{k}(Δ_{k})] = Pr[E_{k−1}(Δ_{k})] × Pr[w_{k} = t_{k}|E_{k−1}(Δ_{k})]
= Pr[E_{k−1}(Δ_{k})]
× p(k, t_{k})Pr[γ(k − 1, t_{k}) = 1|E_{k−1}(Δ_{k})].

This is just a consequence of the independence of x_{k} from x_{1}, ⋯, x_{k−1}. As a result, the probability p(k, t_{k}) is not affected by the values of w_{1}, ⋯, w_{k−1}. Note also that Pr[w_{k} = t_{k}|E_{k−1}(Δ_{k})] = Pr[w_{k} = t_{k}|E_{k−1}(Δ_{k−1})]. Taking the convention that 0 log 0 = 0, we can now express as a sum the entropy H(w_{1}, ⋯, w_{k}).

H(w_{1}, ⋯, w_{k})

= − ∑_{Δ_{k}} Pr[E_{k}(Δ_{k})] log Pr[E_{k}(Δ_{k})]

= − ∑_{Δ_{k}} Pr[E_{k}(Δ_{k})] log(Pr[E_{k−1}(Δ_{k})]

× p(k, t_{k})Pr[γ(k − 1, t_{k}) = 1|E_{k−1}(Δ)])

= − ∑_{Δ_{k}} Pr[E_{k}(Δ_{k})](

log(Pr[E_{k−1}(Δ_{k})])
+ log p(k, t_{k})

+ log(Pr[γ(k − 1, t_{k}) = 1|E_{k−1}(Δ)]))

We now open the parentheses and consider each sum separately.

− ∑_{Δ_{k}} Pr[E_{k}(Δ_{k})] log(Pr[E_{k−1}(Δ_{k})])

= − ∑_{Δ_{k}} log(Pr[E_{k−1}(Δ_{k})])Pr[E_{k−1}(Δ_{k})]

× Pr[w_{k} = t_{k}|E_{k−1}(Δ_{k−1})]

= − ∑_{Δ_{k−1},t_{k}} log(Pr[E_{k−1}(Δ_{k−1})])Pr[E_{k−1}(Δ_{k−1})]

× Pr[w_{k} = t_{k}|E_{k−1}(Δ_{k−1})]

= − ∑_{Δ_{k−1}} Pr[E_{k−1}(Δ_{k−1})] log(Pr[E_{k−1}(Δ_{k−1})])

× ∑_{t_{k}} Pr[w_{k} = t_{k}|E_{k−1}(Δ_{k−1})]

= − ∑_{Δ_{k−1}} Pr[E_{k−1}(Δ_{k−1})] log(Pr[E_{k−1}(Δ_{k−1})]) × 1

= H(w_{1}, ⋯, w_{k−1}).

Now consider the next sum in a similar manner:

− ∑_{Δ_{k}} log p(k, t_{k})Pr[E_{k−1}(Δ_{k})]
× p(k, t_{k})Pr[γ(k − 1, t_{k}) = 1|E_{k−1}(Δ_{k})]

= − ∑_{t_{k}} p(k, t_{k}) log p(k, t_{k}) ∑_{Δ_{k−1}} Pr[E_{k−1}(Δ_{k−1})]

× Pr[γ(k − 1, t_{k}) = 1|E_{k−1}(Δ_{k−1})]

= − ∑_{t_{k}} p(k, t_{k}) log p(k, t_{k}) ∑_{Δ_{k−1}} Pr[γ(k − 1, t_{k}) = 1]

= − ∑_{t_{k}} E[γ(k − 1, t_{k})]p(k, t_{k}) log p(k, t_{k}) = E[H_{k}]

The third sum is always positive. This implies that

H(w_{1}, ⋯, w_{k}) ≥ H(w_{1}, ⋯, w_{k−1}) + E[H_{k}] ≥ ∑_{i=1}^{k} E[H_{i}].

□