PMCCPMCCPMCC

Search tips
Search criteria 

Advanced

 
Logo of nihpaAbout Author manuscriptsSubmit a manuscriptHHS Public Access; Author Manuscript; Accepted for publication in peer reviewed journal;
 
Comput Geom. Author manuscript; available in PMC 2010 December 14.
Published in final edited form as:
Comput Geom. 2006 August 1; 35(1-2): 2–19.
doi:  10.1016/j.comgeo.2005.10.001
PMCID: PMC3001688
NIHMSID: NIHMS197037

Deformable spanners and applications

Abstract

For a set S of points in Rd, an s-spanner is a subgraph of the complete graph with node set S such that any pair of points is connected via some path in the spanner whose total length is at most s times the Euclidean distance between the points. In this paper we propose a new sparse (1 + ε)-spanner with O(nd) edges, where ε is a specified parameter. The key property of this spanner is that it can be efficiently maintained under dynamic insertion or deletion of points, as well as under continuous motion of the points in both the kinetic data structures setting and in the more realistic blackbox displacement model we introduce. Our deformable spanner succinctly encodes all proximity information in a deforming point cloud, giving us efficient kinetic algorithms for problems such as the closest pair, the near neighbors of all points, approximate nearest neighbor search (aka approximate Voronoi diagram), well-separated pair decompositions, and approximate k-centers.

Keywords: Spanner graphs, Kinetic data structures, Proximity maintenance, Collision detection, Approximate nearest neighbor, Well-separated pair decomposition, Geometric k-center

1. Introduction

A subgraph G′ is a spanner of a graph G if πG (p, q) ≤ s · πG(p, q) for some constant s and for all pairs of nodes p and q in G, where πG(p, q) denotes the shortest path distance between p and q in the graph G. The factor s is called the stretch factor of G′ and the graph G′ an s-spanner of G. If G is the complete graph of a set of n points S in a metric space (S, | · |) with πG(p, q) = |pq|, we call G′ an s-spanner of the metric (S, | · |). We will focus on collections of points in Rd, in settings where proximity information among the points is important. Spanners are of interest in such situations because sparse spanners with stretch factor arbitrarily close to 1 exist and provide an efficient encoding of distance information. In particular, continuous proximity queries requiring a geometric search can be replaced by more efficient graph-based queries using spanners.

There is a vast literature on spanners that we will not attempt to review in any detail here because our intent is to pursue a relatively new direction: spanner maintenance under point motion. The readers are referred to a number of survey papers for background material [2,14,33]. Extant spanner constructions are all static, based on sequential centralized algorithms. Our interest is in devising spanner data structures for points in a Euclidean space that can be maintained efficiently under dynamic insertion/deletion as well as continuous motion of the point set.

Maintaining proximity information is crucial in many physical simulations, as most forces in nature are short range—things interact when they are near. This is true across all scales, from smoothed particle hydrodynamics in astronomy to molecular dynamics in biology. We regard collision detection as a special case of proximity maintenance—indeed many extant approaches to collision detection already noted the similarity between that task and that of distance estimation between objects [29]. Of special importance to us is collision or self-collision detection among deformable objects. We came upon the deformable spanners that form the topic of this paper while searching for a lightweight combinatorial data structure that can address the needs of such simulations. Proximity is also important in many aspects of distributed mobile computing, as in ad hoc mobile communication networks. Nodes typically can communicate only where they are within a certain range. Proximity-based clustering has been widely used as a way to structure networks and economize on resources [17].

The aspect ratio of a point set S, defined by the ratio of the maximum pairwise distance to the minimum pairwise distance of points in S, is denoted by α. Our spanner structure, which we call a DefSpanner (or deformable spanner), is built on point sets with bounded aspect ratio, i.e., ones where α is polynomially bounded by the number of points. In terms of simulations, these points can be thought of as the centers of small elements on which the physical simulation model acts. The bounded aspect ratio condition naturally applies to modeling deformable shapes such as vines, ropes, cloth, tissue and proteins [21,30,32]. In all these cases, a deformable object is modeled as a connected collection of small non-overlapping elements of roughly the same size. Thus the aspect ratio is linear in the number of elements. Even when connectivity or disjointness is not required, other physical constraints usually prevent the elements from penetrating too much or drifting too far apart. An example of a spanner for the backbone of a protein is shown in Fig. 1.

Fig. 1
A spanner of a protein backbone. The spanner consists of the backbone edges (black) and a number of additional edges, the shortcuts (light gray). There is a path between any two backbone atoms with length at most 3 times their Euclidean distance.

We propose in this paper a new deformable (1 + ε)-spanner (given any ε > 0) for a set of n points in Rd under the Euclidean metric. We study the properties and applications of such a spanner. Our spanner has O(nd) edges. If the point set has bounded aspect ratio, our spanner will have low degree and low weight, i.e., the maximum number of spanner edges incident to any point is O(lg α/εd),2 and the total weight (length) of all edges is O(MST · lg α/εd+1), where MST denotes the weight of the minimum spanning tree of the point set. Furthermore, the DefSpanner enjoys the additional advantage that it can be updated efficiently under both dynamic and kinetic situations. Most previously proposed algorithms to compute (1 + ε)-spanners are all sequential and efficient updates are difficult. To be specific, in the DefSpanner, insertion or deletion of any point can be done in time O(lg α/εd) in the worst case. When the points move continuously, we study the kinetic properties of our spanner in the Kinetic Data Structures (KDSs for short) framework [8,22]. The kinetic spanner changes only at discrete times and has all the properties of a good KDS: efficiency, locality, responsiveness and compactness. To our knowledge, this is the first kinetic spanner data structure. Under the assumption of bounded aspect ratio, lgα can be replaced by lg n in all the above bounds. A distributed implementation of a variant of this spanner structure is also possible; see [18].

It turns out that our DefSpanner construction only depends on a packing property of Euclidean metrics: a ball with radius r can be covered by at most a constant number of balls of radius r/2. Therefore, the spanner, as well as the applications on all the proximity problems, can be directly extended to the metrics with such properties, which were defined as metrics with constant doubling dimension [23]. Independently, Krauthgamer and Lee [26] proposed a quite similar hierarchical structure for proximity search in such metrics. They use the hierarchical structure to answer (1 + ε) nearest neighbor search in O(lgα + (1/ε)O(1)) time. Their data structure can be maintained so that each insertion and deletion takes O(lgα lg lg α) time. That work however does not address the maintenance of the structure under motion, which is a major issue in this paper.

The focus of this paper are the theoretical and combinatorial properties of our DefSpanner. We plan to report elsewhere on an implementation and comparisons with other proximity maintenance methods. However, we discuss certain aspects of the use of the spanner in physical simulations when appropriate to motivate and justify the choices we have made. In particular, one of our goals has been to address a deficiency of kinetic data structures in the physical simulation setting.

In the classical KDS presentation, all objects are assumed to move according to known motion plans. This may be a good model for air-traffic, but it is not well-suited for modeling deformable objects. In a typical deformable simulation, elements are moved in discrete time steps by an integrator implementing the physical model, typically an ordinary or partial differential equation. Thus, after an integrator step, the KDS has to recover the structure being maintained, even though the intermediate motions of the elements are hidden from view and possibly multiple certificates have failed. We call this the blackbox displacement model: a ‘black box’ moves the points and we need to repair the spanner structure after these small displacements. The general issue of how to repair a geometric structure after small perturbations of its defining elements can be quite hard. We might hope that we can correlate the amount of repair needed in the structure to, for example, the size of the displacements or the number of failed KDS certificates. But this may not be always possible. As Figs. 2 and and33 show, another well-known proximity structure, the Delaunay triangulation, behaves in highly discontinuous ways.

Fig. 2
The points shown are nearly cocircular. The Delaunay triangulation could change dramatically even when the points move ever so slightly.
Fig. 3
The points on top move to the left. While only one edge (the dashed edge) in the triangulation after the motion fails the local Delaunayhood test, repairing the triangulation is very expensive—Ω(n2) flips are required.

Unlike the Delaunay triangulation, however, our DefSpanner is a highly non-canonical structure: for a given configuration of points, many roughly equally good spanner structures are possible. Because of that, we can show that our spanner can be provably and efficiently updated in the blackbox displacement model. The essential reason is that, among all valid spanners for the current configuration we can always choose one that is very similar to the one from the previous time step. In fact, the DefSpanner is the first non-trivial data structure that can be provably maintained under the blackbox displacement model.

In addition to basic proximity maintenance, our DefSpanner can be used to give efficient kinetic and blackbox displacement algorithms for several related problems. For example, we can maintain the closest pair of points and thus have a collision detection mechanism. We can maintain the near neighbors of all points (to within a specified distance), and perform approximate nearest neighbor searches (aka get the functionality of approximate Voronoi diagrams). We also get the first kinetic algorithms for maintaining well-separated pair decompositions and approximate k-centers of our point set. So this one simple combinatorial structure provides a ‘one-stop shopping’ mechanism for a wide variety of proximity problems and queries on moving points.

2. Specific contributions

We now discuss in greater detail the specific problems we address and the contributions that the DefSpanner data structure makes.

Closest pair and collision detection

The crucial insight here is that before a pair of elements can collide in a deformable model, any spanner must put an edge between them (otherwise the bounded spanning ratio condition would be violated)—see Fig. 4. Note also that the closest pair of elements must have an edge in any (1 + ε)-spanner, if ε < 1. Thus the DefSpanner naturally contains the information we need for closest pair maintenance and collision detection.

Fig. 4
Before a collision happens, a spanner edge must connect the colliding elements.

Again, there is a huge literature on collision detection, but relatively little of it deals with collision detection for deformable objects. The standard approaches based on rigid bounding volume hierarchies do not extend easily to deformable shapes. Such hierarchies would need to be recomputed as an object deforms, often at considerable cost. One can mitigate the frequency of recomputing the hierarchies by using larger or looser bounding volumes to allow for some deformation, but then the efficiency of the intersection tests suffers. Some efforts towards better deformable bounding volume hierarchies for ‘linear’ objects are the kinematic chains of Lotan et al. [30], where the hierarchy allows for quick updates after a single, or few, joints in the chain move, and the combinatorial sphere hierarchy of Guibas et al. [21], where bounding spheres are defined implicitly through feature points on the surface of an object. Both of these structures can perform intersection tests in O(n4/3) time in 3-D. There has also been work based on deformable tilings of the free space among moving objects [1], but this is currently limited to 2-D.

Compared to these structures, the DefSpanner is much lighter weight. It is a purely combinatorial structure (edges, specified by pairs of points) of size O(nd) that allows self-collision detection in O(n) time.

All near neighbors search

The all near neighbors search problem is to find all the pairs of points with distance less than a given value r, i.e., for each point, we must return the list of points inside the ball with radius r. In physical simulations such search is often used to limit interactions to only pairs of elements that are sufficiently near each other. For example, most molecular dynamics (MD) systems maintain such ‘neighbor-lists’ for each atom and update them every few integration steps.

A typical MD algorithm performs this task by voxelizing space into tiles of size comparable to the size of a few atoms and tracks which atoms intersect which voxels. Since many voxels may be empty, a hash table is normally used to avoid huge voxel arrays. Atoms are reallocated to voxels after each time step. The simplicity of this method is appealing, but its performance is intimately tied to a prespecified interaction distance.

With the DefSpanner, to find all the points within a certain distance r from a point p, we start from p and follow the spanner edges until the total length is greater than s · r. We then filter the points thus collected and keep only those that are within distance r of p. We can show that the cost of this is O(n + k), where k is the number of pairs in the answer set—thus the method is output sensitive and the cost of filtering does not dominate.

Well-separated pair decompositions

The concept of a well-separated pair decomposition for a set of points in Rd was first proposed by Callahan and Kosaraju [12]. A pair of point sets (A, B) is s-well-separated if the distance3 between A, B is at least s times the diameters of both A and B. A well-separated pair decomposition (WSPD) of a point set consists of a set of well-separated pairs that ‘cover’ all the pairs of distinct points, i.e., any two distinct points belong to the different sets of some pair of the decomposition. In [12], Callahan and Kosaraju showed that for any point set in a Euclidean space and for any positive constant s, there always exists an s-well-separated pair decomposition with linearly many pairs. This fact has been very useful in obtaining nearly linear time algorithms for many problems such as computing k-nearest neighbors, n-body potential fields, geometric spanners and approximate minimum spanning trees [2,6,912,15,20,28,31].

In fact, many of the spanner constructions for points in Euclidean space use the well-separated pair decomposition as a tool [2,6,28,31]. The basic idea is this: the graph defined by taking an arbitrary edge connecting each s-well-separated pair must be a spanner [9]. The spanning ratio can be made arbitrarily close to 1 as long as we choose a large enough s. Here we show that the other direction is also true: the DefSpanner we build can be used to generate an s-well-separated pair decomposition, for any positive s—it suffices to take ε = 4/s in the spanner construction. The size of the WSPD is linear, which matches the bound by Callahan and Kosaraju [12]. Since the spanner can be maintained in dynamic and kinetic settings, the well-separated pair decomposition can also be maintained efficiently for a set of moving points.

(1 + ε)-nearest neighbor query/approximate Voronoi diagram

The DefSpanner we propose can be used to output the approximate nearest neighbor of any point p [set membership] Rd with respect to the point set S, in time O(lg nd). There has been a lot of work on data structures to answer approximate nearest neighbor queries quickly [35,25]. However, they all try to minimize the storage or query cost and do not consider points in motion.

k-centers

For a set S of points in Rd, the k-center is a set K of points, K [subset, dbl equals] S, |K| = k, such that maxp[set membership]S minq[set membership]K |pq| is minimized. The geometric k-center problem, where the points lie in the plane and the Euclidean metric is used, is approximable within 2, but is not approximable within 1.822 [16]. However, the usual algorithms to compute approximate k-center are of a greedy nature [16,19], and thus not easy to kinetize. For the dual problem of k-centers, i.e., minimizing the number of centers when the radius of each cluster is prespecified, efficient kinetic maintenance schemes are available [17,24]. Here we show how to compute an 8-approximate k-center by using the DefSpanner. Furthermore, we are first to give a kinetic approximate k-center as the points move.

2.1. Result summary

We summarize the results below. All the algorithms/data structures are deterministic and we consider the worst-case behavior. For a set S of n points in Rd with aspect ratio α, we have,

  • A (1 + ε)-spanner with O(nd) edges, maximum degree bounded by O(lg α/εd), and total weight bounded by O(MST · lg α/εd+1), where MST is the weight of the minimum spanning tree of S;
  • An O(n) structure for finding all near neighbors in time O(k + n), where k is the size of the output;
  • A (1/ε)-well-separated pair decomposition of size O(nd);
  • An O(n) structure for (1 + ε)-nearest neighbor queries in O(lg α/εd) time;
  • An O(n) data structure for closest pair and collision detection;
  • An 8-approximate k-center, for any 0 < kn.

Furthermore, if the point set also has bounded aspect ratio, we have efficient kinetic and dynamic maintenance for the spanner so that each operation takes O(lg α/εd) time—in fact lgα can be replaced by lg n in all the above bounds. The kinetic data structures for maintaining the (1 + ε)-spanner, the (1/ε)-well-separated pair decomposition, the 8-approximate k-center, have the four desirable kinetic properties of efficiency, compactness, locality, and responsiveness.

3. The deformable spanner

In this paper we focus on a set S of points in the Euclidean space Rd. Recall that the aspect ratio α of S is defined by the ratio of the maximum pairwise distance to the minimum pairwise distance between points in S. Without loss of generality, we assume that the closest pair of points has distance 1 and the furthest pair of S has distance α.

3.1. Spanner definition

A set of discrete centers with radius r for a given point set S is defined as a maximal subset S[subset, dbl equals] S such that the balls with radius r centered at the discrete centers contain all the points of S but any two centers are of a distance greater than r away from each other.

The DefSpanner is defined on a hierarchy of discrete centers S0S1(...)Sh such that S0 is the original point set S and Si is a set of discrete centers of Si−1 with radius 2i, for i > 0. Intuitively, the hierarchical discrete centers are well-distributed samplings of the point set at different spatial scales.

For a discrete center hierarchy {Si}, the DefSpanner G is the collection of edges between pairs of points in each level Si within a distance at most c · 2i, where c = 4 + 16/ε. In other words, the DefSpanner edges connect centers on the same level within a distance threshold that is comparable to the radius of that level.

We note that for a given set S and a radius r, there may be different sets of discrete centers of S with radius r, and thus, the DefSpanner of a given set S is not uniquely determined.

We use the following notations throughout the paper. Since a point p may appear in many levels in the discrete center hierarchy, when it is not clear, we use p(i) to denote the node p in level Si. A center q(i) is said to cover p(i−1) if |pq| ≤ 2i. A point p(i−1) may be covered by many centers in Si. We denote by P(p(i−1)) one of those centers and call it the parent of p(i−1). When the level is clear from the context, we simply denote P(p) the parent of p. We also call p a child of P(p). The choice of the parent P(p) is arbitrary but fixed. If p is in Si, then p(i) is taken as the parent of P(i)(p(i−1)). We call P(i)(p) the ancestor of p in level Si, p [set membership] S0. For a node p(i), we denote by Ci−1(p) the set of p’s children in Si−1, i.e., Ci−1(p) = {q [set membership] Si−1 | P(q) = p}; and denote by Ni(p) the set of neighbors of p in Si, i.e., Ni(p) = {q [set membership] Si| |pq| ≤ c · 2i}.

3.2. Spanner property

We first prove some properties about the discrete center hierarchy and the DefSpanner.

Lemma 3.1

  1. Si [subset, dbl equals] Si−1.
  2. For any two points p, q [set membership] Si, |pq| ≥ 2i.
  3. If q(i) [set membership] Ci(p(i+1)) and qp, then q(i) [set membership] Ni(p(i)), i.e. there is an edge from each point q to its parent.
  4. The hierarchy has at most [left ceiling]lgα[right ceiling] levels.
  5. For any point p, define the parent chain from p [set membership] S0 to its ancestor P(i)(p) [set membership] Si by following the edge to the parent at a higher level until P(i)(p) is reached, i.e., pP(p)P(2)(p) (...)P(i)(p). The parent chain has total length no more than 2i+1. Thus p’s ancestor P(i)(p) [set membership] Si is of a Euclidean distance at most 2i+1 away from p.

Proof. The first three claims are obvious. For the fourth claim, an ith level center p [set membership] Si has radius 2i. So if 2i ≥ α, the ball centered at a point p [set membership] S with radius 2i contains all the points in S. Therefore the height of the hierarchy h is at most [left ceiling]lgα [right ceiling]. For the last claim, by the definition of the parent chain between p and its ancestor P(i)(p), the total length of this path is at most 2 + 22+(...)+2i ≤ 2i+1. By triangular inequality, the Euclidean distance between p and P(i)(p) can only be smaller than that.

We are now ready to prove that G is a spanner.

Theorem 3.2. G is a (1 + ε)-spanner.

Proof. For a pair of points p, q [set membership] S0 we find the smallest level i so that there is an edge between their ancestors P(i)(p) and P(i)(q). Define pi = P(i)(p), qi = P(i)(q), pi−1 = P(i−1)(p), qi−1 = P(i−1)(q). We take the path Λ(p, q) as the concatenation of the parent chain from p to pi, the edge between pi, qi and the parent chain between qi and q. To prove that G is a spanner, we show that the path Λ(p, q) has length at most (1 + ε)|pq|.

First, we have that |piqi| ≤ c · 2i and |pi−1qi−1| > c · 2i−1. By Lemma 3.1, |ppi−1| ≤ 2i, |qqi−1| ≤ 2i. So |pq| ≥ |pi−1qi−1| − |ppi−1| − |qqi−1| > (c −4) · 2i−1. Also the length of Λ(p, q) is at most 2i+1 + |piqi| + 2i+1 ≤ |pq| + 8 · 2i ≤ (1 + 16/(c −4))|pq| = (1 + ε)|pq|. This proves that G is a (1 + ε)-spanner.

3.3. Size and weight of the spanner

We first prove a simple result that is used repeatedly in our paper.

Lemma 3.3 (Packing Lemma). If all points in a set U [subset or is implied by] Rd are of at least a distance r away from each other, then there are at most (2R/r + 1)d points in U within any ball X of radius R.

Proof. Let X′ be a ball co-centric with X with radius R + r/2. The balls of radius r/2 centered at points of U inside X are all disjoint and are inside X′. By a volume argument, there can be at most ((R + r/2)/(r/2))d = (2R/r + 1)d such balls.

Using Lemma 3.3, we have:

Lemma 3.4. Each point in Si covers at most 5d points in Si−1.

Lemma 3.5. A point p [set membership] Si has at most (1 + 2c)d − 1 edges with other points of Si.

Note that the bound in Lemma 3.4 can be improved. A more careful analysis, e.g., by Sullivan [35], shows that the maximum number of points in Si−1 covered by a point in Si is 19 in R2; 87 in R3; and O(2.641d) in dimension d.

Lemma 3.6. The maximum degree of G is (1 + 2c)d[left ceiling]lgα[right ceiling].

Proof. It follows from Lemmas 3.5 and 3.1(4).

Lemma 3.7. The total number of edges in G is less than 2(4c)d · n.

Proof. Note that if G is a DefSpanner and p is a point in G that does not have any children, then removing p and all edges incident on p from G gives us another DefSpanner G′ with one less vertex. The lemma follows if we can show that we can always find a childless point p in G that is incident to at most 2(4c)d edges.

Let p and q be the closest pair of points in G and let k = [left floor]lg|pq|[right floor]. As p and q cannot be both in Sk+1, we assume without lost of generality that p is not in Sk+1. Since p is at least 2k away from all points, it does not have any children in level k − 1 or below, and thus it is childless. By Lemma 3.3, p is incident to at most (1 + 2c/2j)d − 1 ≤ (4c/2j)d − 1 edges in Skj, for all 0 ≤ j ≤ lg c. The total number of edges incident on p is thus at most j=0lgc((4c/2j)d1)<2(4c)d.

Lemma 3.8. Denote by the weight of a graph as the total lengths of all the edges. The total weight of the DefSpanner is O(MST · lg α/εd+1).

Proof. First we bound the total lengths of all edges in a certain level Si. We charge the edges in Si to the minimum spanning tree (MST) of Si: an edge incident on p(i) is charged to one of the MST edges incident on p(i). Since each node in Si has at most O(1/εd) edges with other nodes in Si, each edge of the MST is charged at most O(1/εd) times. Since the edges of the DefSpanner on Si have lengths at most c · 2i and the points of Si are at least 2i away from each other, the length of an edge in Si is at most c = O(1/ε) times the length of the charged edge in the MST of Si. Thus the total lengths of the edges in Si is at most O(1/εd+1 · MST(Si)). The weight of the MST of Si is at most twice the weight of the minimum Steiner Tree4 (MStT) of Si [36]. Furthermore if a point is added, the weight of the MStT can only become larger. Thus we have MST(Si) ≤ 2MStT(Si) ≤ 2MStT(S) ≤ 2MST(S). It follows that the total weight of the spanner is at most O(MST · lg α/εd+1).

To summarize, we have,

Theorem 3.9. For a set of n points in Rd with aspect ratio α, we can construct a (1 + ε)-spanner G so that the total number of edges in G is O(nd), the maximum degree of G is O(lg α/εd), and the total weight of G is O(lg α/εd+1 · MST).

Remark Notice that the hierarchy has at most [left ceiling]lgα[right ceiling] levels. We can replace the logarithm base with any number greater than 1. Specifically if we choose β > 1, we can build the hierarchy so that for any two points p, q in Si, |pq| ≥ βi. The hierarchy has at most [left ceiling]logβ α[right ceiling] levels. Similar to Theorem 3.2, we can show that the graph constructed is a (1 + ε) spanner when c>max(β,4β2(β1)ε+2ββ1).

4. Construction and dynamic maintenance

The previous section defines a set of properties such that a graph with those properties is a spanner. In this section we show that we can efficiently construct the spanner in O(n lg α) time, where n is the number of points and α is the aspect ratio of the point set. We also show that we can dynamically insert or remove a point from our hierarchy, at a cost of O(lg α) for each operation. In practical settings where α is a polynomial function of n, the construction of the hierarchy is O(n lg n), and dynamic update operations are done in O(lg n) time each.

To describe the dynamic maintenance of the spanner, we adopt a slightly different setting. We assume that the aspect ratio α is always bounded by a polynomial of the number of points. However, as the points are inserted and deleted, the minimum separation of the point set may change. To address this, we imagine that we virtually keep sets of points Si for −∞ < i < ∞, such that Si is a set of discrete centers of Si−1 with radius 2i. Since the aspect ratio is bounded, there exist m and M such that there are spanner edges only on Si, miM, Mm = O(lg n). We refer to Sm and SM the bottom and the top of the hierarchy respectively. For each point p other than the root of the hierarchy, we store the maximum number Mp such that level SMp contains p, and store its parent P(p(Mp)). We also store the minimum number mp such that p has a neighbor in Smp, non-empty lists of neighbors of p in each of the levels between Smp and SMp, and non-empty lists of children of p in all levels below SMp. We also store the value of m and M for the hierarchy. Notice that we can always scale the point set so that the minimum separation is 1 and thus return to the previous setup.

We begin with the following simple yet crucial observation which is used repeatedly in this section. It asserts that if there is an edge between two nodes, then there is also an edge between their parents:

Lemma 4.1. If q(i) [set membership] Ni(p(i)) then P(q) [set membership] Ni+1(P (p)).

Proof. If q(i) [set membership] Ni(p(i)), |pq| ≤ c · 2i. Thus |P(p)P(q)| ≤ |P(p)p| + |pq| + |qP(q)| ≤ (c + 4) · 2ic · 2i+1.

4.1. Spanner construction

We construct the hierarchy incrementally by inserting points one by one. Suppose that we already have a hierarchy of n − 1 points. We insert the nth point p in two passes, one top down and one bottom up. In the first pass, we travel down the hierarchy and find potential spanner edges of p at each level of the hierarchy. In the second pass, we travel up the hierarchy, locate the highest level that p appears, and clean up all the levels above it. We’ll describe the two passes in the following separately.

We first pretend that p appears in all levels of the hierarchy and find potential spanner edges of p on each level. We set p(i)’s parent as p(i+1). From Lemma 4.1, p can only have edges to nodes on level i whose parents on level i + 1 have already got edges with p. In the top level, there is a single root r. If the distance from p to r is longer than c · 2M, we increase M and extend the hierarchy upward so that the root r is a neighbor of p on the top level. For subsequent levels Si, we compute Ni(p) by checking the distance from p to all its ‘cousins’, i.e., the children of the neighbors of its parent. We stop if p does not have any neighbor. Intuitively, in this step we do point location from top down by using Lemma 4.1 and connect edges no longer than c · 2i to p on each level i. If p has a neighbor in the bottom level, we check whether p has any neighbors in even lower levels and if such neighbors exist, we decrease m and extend the hierarchy downward.

We then traverse the hierarchy from the bottom up and clean up the hierarchy of discrete centers. We find the highest level Si and the point q [set membership] Ni(p) such that |pq| < 2i. We set the parent of p in Si−1 to be q, and remove p from all levels Si and above. If p still remains in the top level, we increase M and extend the hierarchy upward.

Note that we are making two passes through the hierarchy. In each level in each pass, the work is at most 5d (1 + 2c)d = O(1/εd), and thus the cost of one insertion is O(hd), and the total cost of the construction is O(nhd), where h = O(lg α) is the height of the hierarchy.

4.2. Dynamic updates

From the previous subsection, it is clear that we can insert points into the hierarchy at the cost of O(lg α/εd) each. In this section, we show that points can be removed from the hierarchy, again at the cost of O(lg α/εd) each.

To remove a point p from the hierarchy, we remove p from bottom up. If p has no children (except itself), we can simply remove p and all edges incident on p in each level. If p has children, its children would become orphans, and we need to find new parents for them before we can remove p. We assume q(i) is a child of p(i+1), qp. From (3) in Lemma 3.1, q(i) is a neighbor of p(i) on level i.

From Lemma 4.1, we know the parent of q(i) must be a neighbor of the parent of p(i), i.e., p(i+1). If there is a neighbor w of p(i+1) that covers q(i), we set q(i)’s parent to be w and we are done. If q(i) is not covered by any centers on level Si+1, it must be inserted into Si+1. Notice that q(i+1) is a neighbor of p(i+1), we can recursively either find a parent for q(i+1) or promote q further up. The neighbors of q can then be computed from top down in a way similar to point insertion in the previous subsection.

Note that the cost of raising a child of p up one level is O(1/εd), and as the child may end up in the top level, the cost of fixing a child of p is O(lg α/εd). Since p could appear in O(lg α) levels and has O(lg α) children, a trivial bound on the cost of removing p is O(lg2 α/εd). However notice that for any level Si, all children of p on or below the level are inside a disk of radius 2 · 2i, and the minimum separation in Si is 2i. By Lemma 3.3, at most O(1) of the children can end up being in Si. The total cost of removing a point is thus O(lg α/εd).

Theorem 4.2. Dynamic insertion and deletion of points in the spanner take O(lg α/εd) each, where α is the aspect ratio. The spanner can be constructed in time O(n lg α/εd).

5. Maintenance under motion

5.1. Kinetic data structure overview

We analyze the maintenance of the spanner in the kinetic data structure (KDS) framework [8,22]. A KDS tracks an attribute of a moving system over time by maintaining a set of certificates as a proof of attribute value correctness. In our case, we would like to maintain a set of certificates showing that the discrete centers hierarchy is valid, and that the edges are connecting precisely the appropriate nearby pairs of points in each level. When the points move, the certificates may become invalid. A KDS event happens when a certificate fails. At each event, we need to update the certificate set and possibly the spanner. In the KDS framework, the motion of the points are assumed to be explicitly known, so that the failure times of the certificates can be predicted precisely. The KDS processes the certificate failures in order of the failure time, jumping from one event to the next.

We will show how we maintain the spanner in the KDS framework and verify that our spanner enjoys all the desirable properties of a good KDS. We will then discuss how to maintain the spanner in practice, when the motion of the points are given by a black box.

5.2. KDS maintenance

To maintain the spanner G in the KDS framework, we need to maintain the discrete centers hierarchy and the edges between the centers at each level. First, we keep the neighborhood information for each node p. We have three kinds of certificates for this purpose.

  1. A parent-child certificate certifies that a child p is within distance 2i+1 from its parent in level i + 1.
  2. An edge certificate certifies that a neighbor q of p at level i is within distance c · 2i.
  3. A separation certificate certifies that a neighbor q of p at level i is of distance 2i away.
    These three certificates prove the validity of the discrete centers hierarchy and also detect when the near neighbors move further away. However, the more difficult part is to detect when two currently far away points move close to each other for the first time. The key observation on the spanner hierarchy is that before two points can become neighbors at some level i, their parents are already neighbors at level i + 1, as shown in Lemma 4.1. Therefore we only need to keep track of the potential neighbors of a point p, which are the ‘cousins’ of p, i.e., the centers that are not neighbors of p but their parents are P(p)’s neighbors.
  4. A potential neighbor certificate certifies that a potential neighbor of p at level i is of distance c · 2i further away.

All certificates are simple distance comparisons among pairs of points. To summarize, the four kinds of certificates make sure that for each center p in level i, the values P(p) (if P(p) ≠ p), Ni(p), and Ci−1(p) we maintain are valid. The failure of the four types of certificates generates four types of events, which are discussed separately as follows. Let p be a point in level i:

  1. Addition of a spanner edge. When a potential neighbor certificate fails, i.e., a potential neighbor q of p comes within a distance c · 2i of p, we add an edge between p and q, making q a neighbor of p. We also update the list of potential neighbors of the children of p and q.
  2. Deletion of a spanner edge. When an edge certificate fails, i.e., a neighbor q of p moves such that it is further than c · 2i from p, we drop the edge between p and q, making them potential neighbors. We also update the list of potential neighbors of the children of p and q.
  3. Promotion of a node. When a parent-child certificate fails, i.e., q = P(p) no longer covers p, |pq| > 2i+1. p becomes an orphan, and we need to find a new parent for p or promote it into higher levels. We deal with orphans in the same way as in dynamic updates. We then update the potential neighbors of p in level i and above.
  4. Demotion of a node. When a separation certificate fails, i.e., a neighbor q of p comes within a distance of 2i, we need to remove one of the two points from level i. Assume without lost of generality that p is not in level i + 1. We demote p, i.e., removing p from level i. Each former child t of p in level i − 1 becomes an orphan, and we deal with each of them as in the previous event.

The number of certificates for a point in any level it participates is O(1/εd), and thus the total number of certificates is O(nd), and the number of certificates associated with any point is O(lg α/εd). Assuming that the motion preserves the bounded aspect ratio α, the total number of events in maintaining the spanner under pseudo-algebraic motion is bounded by O(n2 lg α) since an event only happens when the distance between two points becomes either 2i or c · 2i for i = 0,…, lgα.

Note that both the dynamic and kinetic maintenance can also be done exactly in the same way for spanners with hierarchy expansion ratio β > 1 and c > max(β, 2β/(β − 1)).

5.3. Quality of the kinetic spanner

There are four desirable properties that a good KDS should have [8,22]: (i) compactness: the KDS has a small number of certificates; (ii) responsiveness: when a certificate fails, the KDS can be updated quickly; (iii) locality: each point participates in a small number of certificates so that when the motion plan of that point changes, the KDS can be updated quickly; (iv) efficiency: there are not too many certificate failures compared with the number of combinatorial changes of the attribute being tracked in the worst case.

As pointed out in the previous subsection, our kinetic spanner has linear number of certificates, and that each point participates in at most O(lg α/εd) certificates. It is also easy to see that the cost to repair the KDS when a certificate fails is either O(1) or O(lg α/εd). Our spanner KDS is thus compact, responsive, and local. As for the efficiency, we first have the following result:

Lemma 5.1. There exists a set of n points so that any linear-size c-spanner has to change Ω(n2/c2) times.

Proof. We consider a necklace of balls in the plane. The necklace consists of three segments. For the two segments close to the ends, each contains n/c bumps, where each bump has height c and the distance along the necklace between adjacent bumps is 2c. The two segments are connected by a bent segment with 2n balls. The total number of balls in the necklace is 10n. The top segment with bumps is moving linearly towards the left; the bottom segment remains static. The balls on the middle segment move accordingly to keep the necklace connected. Fig. 6 shows the configuration of the necklace at the starting and ending point.

Fig. 6
Motion of the points.

Consider the time when a top bump is directly above a bottom bump, so that the distance between their peaks is 1. See Fig. 7. For any c-spanner, there must be a path connecting the two peaks with length no more than c. Therefore there must be an edge between some point in the top bump and some point in the bottom bump, since otherwise any path between the two peaks will be longer than c. So the total number of edges in the c-spanner that ever appear during the motion is at least Ω(n2/c2). Since the spanner starts with O(n) edges. there must be at least Ω(n2/c2) changes of any linear-size c-spanner.

Fig. 7
Lower bound Ω(n2/c2) for the changes of any linear-size spanner.

On the other hand, there are O(n2) pairs of points, and each pair of points can generate at most O(lg α) events when the distance between them equals either 2i or c · 2i for some integer i, 0 ≤ i ≤ lgα. The number of events that our spanner KDS has to handle is thus at most O(n2 lg α), only a lgα factor more than the minimum number of times any spanner on the points has to change. We have established:

Theorem 5.2. The kinetic spanner is efficient, responsive, local and compact. Specifically, the total number of events in maintaining G is O(n2 lg α) under pseudo-algebraic motion. Each event can be updated in O(lg α/εd) time. A flight-plan change can be handled in O(lg α/εd) time. Each point is involved in at most O(lg α/εd) certificates. When the aspect ratio of the point set is bounded, the lgα in the above formulas can be replaced by lg n.

5.4. Maintenance in a physical simulation setting

In practice, the motion of the points may not be known in advance. Instead, the new point positions are given by some physics black box after every time step, and we are called in to repair the spanner. When the points don’t move too much, we can repair the spanner efficiently, since the spanner depends only on the pairwise distances of the points.

We first verify and update the hierarchy from the top down, using update operations as in the KDS setting. Suppose that we have updated all levels above level i and we would like to update level i. First we verify that all centers in level i are still covered by their parent centers in level i + 1. For each center in level i that became an orphan, we find a new parent for it. Then for each pair of neighbors in level i that are closer than 2i, we demote one of the two centers and find new parents for the orphans. Edges in level i are then verified and updated if necessary.

To show that the hierarchy is correct after the update, we need the following lemma which extends Lemma 4.1.

Lemma 5.3. Let p, q be centers in level i and r = P(p), s = P(q) in a time frame. If p, q, r, s do not move more than (c/4 − 1) · 2i in each time step, then in the next time frame p and q are neighbors only if r = s or r and s are neighbors.

Proof. Let p1, q1, r1, s1 and p2, q2, r2, s2 be the positions of the centers in the two time frames respectively. If p2 and q2 are neighbors, then |r2s2| ≤ |r2r1| + |r1p1| + |p1p2| + |p2q2| + |q2q1| + |q1s1| + |s1s2| ≤ (c − 4) · 2i + 2 · 2i+1 + c · 2i = c · 2i+1, and thus r2 = s2 or r2 and s2 are neighbors.

Note that the cost of the update consists of the cost of traversing the hierarchy, the cost of verifying all edges, and the cost of fixing orphans. The cost of traversing and the cost of verifying all edges is proportional to the number of edges, which is O(n). The total cost of the update is thus O(n + k lg α) where k is the number of changes to the hierarchy. If we know more about the motions of the points, we can lower the spanner update cost by computing conservative bounds on the failure times of various spanner certificates and using the bounds to avoid examining these certificates for a series of steps. The topic of tighter coupling between the spanner maintenance and the integrator module will be discussed in a future paper.

6. Applications

6.1. Spanners and well-separated pair decomposition

We show by the following theorem that the spanner implies a linear size well-separated pair decomposition.

Lemma 6.1. The spanner can be turned into an s-well-separated pair decomposition, so that s = c/4 − 1 = 4/ε. The size of this well-separated pair decomposition is O(nd).

Proof. For nodes p(i) and q(i) in the spanner, we denote by Pi and Qi, respectively, the sets of all decedents of p(i) and q(i) including p(i) and q(i). Consider the set C of pairs (Pi, Qi) where p(i) and q(i) are not neighbors in level i, but their parents in level i + 1 are neighbors. We now argue that C is an s-well-separated pair decomposition with s = c/4 − 1 = 4/ε.

Note that all points in Pi (or Qi) are within a distance of 2i+1 from pi (or qi), and thus the diameter of Pi (or Qi) is at most 2i+2. Since p(i) and q(i) are not neighbors in Si, |pq| > c · 2i, and thus the distance between Pi and Qi is at least (c − 4)2i. It follows that Pi and Qi are s-separated, where s = (c − 4)/4. On the other hand, for each pair of points in S, there is only one level i in the hierarchy such that their ancestors on level i is connected by an edge but their ancestors on level i + 1 are not connected by an edge. Thus any pair of points is covered by exactly one pair (Pi, Qi) in C. This shows that C is an s-well-separated pair decomposition.

By Lemma 3.4, each point covers at most 5d points in one level below. The number of well-separated pairs in C equals to the number of non-connected cousin pairs in the DefSpanner hierarchy, which is at most a factor of 52d the number of edges in DefSpanner. Thus C has size O(nd).

Theorem 6.2. The s-well-separated pair decomposition can be maintained by a KDS which is efficient, responsive, local and compact.

Proof. We construct and maintain the DefSpanner. By using the DefSpanner as a supporting data structure, we maintain the well-separated pair decomposition implicitly by marking the pairs (Pi, Qi) where p(i) and q(i) are not connected by an edge in some level i, but their parents in level i + 1 are connected by an edge. They only change when the edges are inserted/deleted. So the total number of events is O(n2 lg α), as per Theorem 5.2. Upon request, a well-separated pair can be output in time proportional to the number of points it covers.

On the other hand, there exists a set of n points such that any linear-size c-well-separated pair decomposition has to change Ω(n2/c2) times. For the setting in Fig. 7, there must be a well-separated pair that contains only the points of the upper bump and lower bump. The total number of such pairs is Ω(n2/c2), so is the total number of changes.

6.2. All near neighbors query

The near neighbors query for a set of points, i.e., for each point p, returning all the points within distance [ell] from p, has been studied extensively in computational geometry. A number of papers use spanners and their variants to answer near neighbors query in almost linear time [7,13,27,34]. Specifically, on a spanner, we do a breadth-first search starting at p until the graph distance to p is greater than s · [ell], where s is the stretch factor. Due to the spanning property, this guarantees that we find all the points within distance [ell] from p. Furthermore, we only check the pairs with distance at most s · [ell]. Notice that unlike the previous papers that focus only on static points, the DefSpanner can be maintained under motion, so the near neighbors query can be answered at any time during the movement of the points.

Before we bound the query cost of the algorithm, we first show that the number of pairs within distance s · [ell] will not differ significantly with the number of pairs within distance [ell]. A similar result has been proved in [34]. The following theorem is more general with slightly better results and the proof is much simpler.

Theorem 6.3. For a set S of points in Rd, denote by χ ([ell]) the number of ordered pairs (p, q), p, q [set membership] S such that |pq| ≤ [ell], then χ (s · [ell]) ≤ (2(2s + 3)d + 1) χ ([ell]) + n(2s + 3)d.

Proof. We first select a set of discrete centers S[ell]/2 with radius [ell]/2 from points S. We then assign a point q to a center p if |pq| ≤ [ell]/2. A point can be within distance [ell]/2 of more than 1 centers. In this case, we assign it to one of them arbitrarily. Any point is assigned to one and only one discrete center. We say q is covered by p if p is the assigned center for q. The set of points covered by p [set membership] S[ell]/2 is denoted by H (p). Define k(p) = |H(p)|.

Define the distance between two sets A, B of points as the minimum distance between two points in each set. We consider the set Ψ of ordered pairs (H(p), H(q)), pq such that the distance between H(p) and H(q) is at most s · [ell]. By triangular inequality, |pq| ≤ (s + 1) · [ell]. Using Lemma 3.3, the number of such q’s that (H(p), H(q)) [set membership] Ψ is at most (2s + 3)d. Thus Ψ has at most (2s + 3)dn ordered pairs.

An edge pq′ is said to be covered by (H(p), H(q)) if p[set membership] H(p) and q[set membership] H(q). We note that any pair of points within the same H(p) for any p are within a distance of [ell] of each other. Thus we have

χ()pS/2k(p)(k(p)1).
(1)

Furthermore, any ordered pairs (p′, q′) with [ell] < |pq′| ≤ s · [ell] are covered by some pair (H(p), H(q)) [set membership] Ψ. Thus we have

χ(s·)χ()(H(p),H(q))Ψk(p)k(q).
(2)

Using the inequality aba(a − 1) + b(b − 1) + 1 for all real numbers a and b, k(p)k(q) ≤ k(p)(k(p) − 1) + k(q)(k(q) − 1) + 1. Summing this inequality over all pairs in Ψ, we obtain

(H(p),H(q))Ψk(p)k(q)2(2s+3)dpS/2k(p)(k(p)1)+n(2s+3)d.
(3)

Combining (3) with inequalities (1) and (2), we have χ (s · [ell])− χ ([ell]) ≤ 2(2s + 3)d χ ([ell]) + n(2s + 3)d, which implies χ (s · [ell]) ≤ (2(2s + 3)d + 1) χ ([ell]) + n(2s + 3)d.

Theorem 6.4. For a set S of points in Rd, we can organize the points into a structure of size O(n) so that we can perform the near neighbors query, i.e., for each point p, find all the points within distance [ell] of p, in time O(k + n), if the size of the output is k.

Proof. As we described before, we traverse the s-spanner G by a breadth-first search and collect the pairs with distance at most s · [ell] that include all pairs with distance no more than [ell]. We then filter out unnecessary pairs and only keep the pairs within distance [ell]. From Theorem 6.3, χ (s[ell]) ≤ (2(2s + 3)d + 1)k + n(2s + 3)d, where k is the size of the output. For a fixed s, G has linear size by Theorem 3.9, and the cost of traversing and filtering is O(k + n).

We remark that this output sensitivity is not valid on a per point basis. Fig. 8 shows an example situation where for point p the number of neighbors within distance s · [ell] is not proportional to those within distance [ell]

Fig. 8
The number of neighbors of point p increases abruptly.

6.3. (1 + ε)-nearest neighbor

An s-approximate nearest neighbor of a point p [set membership] Rd with respect to a point set S is a point q [set membership] S such that |pq| ≤ s · |pq*|, where q* is the nearest neighbor of p. We first show that a (1 + ε) nearest neighbor is embedded in a (1 + ε) DefSpanner.

Lemma 6.5. For a (1 + ε) DefSpanner on a set S of points in Rd, we can perform the (1 + ε)-nearest neighbors query in O(lg α/εd) time, i.e., given a point p [set membership] Rd and a real number ε > 0, we can find a point q in S such that |pq| ≤ (1 + ε)|pq*|, where q* is the nearest neighbor of p.

Proof. We construct the (1 + ε) DefSpanner G as before. Firstly, we do a fake insertion of p. Assume q is the direct neighbor of p in the spanner with the closest distance. Then q is a (1 + ε)-approximate nearest neighbor. To see this, we assume that q* is the nearest neighbor of p. From the spanner property we know that πG(p, q*) ≤ (1 + ε) · |pq*|. On the other hand, since pq is the shortest edge attached with p in the graph G, then we must have πG(p, q*) ≥ |pq|. This implies that |pq| ≤ (1 + ε) · |pq*|.

We find such a q, i.e., the closest neighbor of p on the spanner, as follows. Suppose i is the lowest level where the edge pq appears, c · 2i−1 < |pq| ≤ c ·2i. Then for the level ji − 1, there is no edge attached with point p. Otherwise that edge would have shorter distance than pq. Therefore for each point p [set membership] S, we take the lowest level i where p has an edge in the spanner. We take the shortest edge pq among all the level i edges. q is the (1 + ε)-approximate neighbor of p. The theorem then follows from Theorems 3.9 and 4.2.

Furthermore, if we keep for each point its shortest edge in the spanner, we can get the (1 + ε)-nearest neighbor of any point p [set membership] S by a single lookup. The maintenance of the DefSpanner implies the maintenance of the (1 + ε)-nearest neighbor information as well. So we have,

Theorem 6.6. For a set S of points in Rd, we can maintain a kinetic data structure of size O(nd) that keeps the (1 + ε)-nearest neighbor in S of any node p [set membership] S. The structure is efficient, responsive, local and compact.

Proof. All we need to prove is the efficiency of the KDS. The example in Lemma 5.1 shows that any linear-size structure maintaining the (1 + ε)-approximate neighbor has to change Ω(n2ε2) times.

So far we build a (1 + ε) DefSpanner to answer and maintain the (1 + ε)-approximate nearest neighbor query for a specific ε. In fact, to answer the (1 + ε)-approximate nearest neighbor query, we can decouple the dependency of the DefSpanner on the parameter ε by using a O(1) DefSpanner as an auxiliary structure.

Theorem 6.7. For a set S of points in Rd, we can organize the n points into a structure of size O(n) so that we can perform the (1 + ε)-nearest neighbor query in O(lg α/εd) time, i.e., given a point p [set membership] Rd, find a point q in S such that |pq| ≤ (1 + ε)|pq*|, where q* is the nearest neighbor of p.

Proof. Fix a constant c > 4 and construct a DefSpanner using that constant. Given an ε > 0 and a query point p, we let t = 2 + 4/ε. To answer the (1 + ε) approximate nearest neighbor of p, we traverse the DefSpanner top down and keep track of the set Wi = {q | q [set membership] Si, |pq| < t · 2i} as the level i decreases.

First of all, we notice that |Wi| = O(td) for any i, since the points in Si are at least distance 2i apart. Secondly, we observe that for a point q [set membership] Si, if |pq| < t · 2i, by triangular inequality |pP(q)| ≤ |pq| + |qP(q)| < t · 2i + 2i+1t · 2i+1. Therefore Wi must be included in the set of the children of Wi+1. So we can construct Wi from Wi+1 in O(td) time, by checking the children of all the points in Wi+1. The total running time of such a traversal is bounded by O(td lg α) = O(lg α/εd).

At the end of the traversal of the DefSpanner, let q be the point closest to p in W0. We will show that q is a (1 + ε)-nearest neighbor of p. Let q* [set membership] S0 be the closest point to p among all points in the spanner. If q* is in W0, then clearly |pq| = |pq*|, and we are done. If not, let j be the level such that P(j−1)(q*) [negated set membership] Wj−1 and P(j)(q*) [set membership] Wj. By definition of q and Lemma 3.1, |pq| ≤ |pP(j)(q*)| ≤ |pq*| + |q*P(j)(q*)| ≤ |pq*| + 2j+1. On the other hand, |pq*| ≥ |pP(j−1)(q*)| − 2j ≥ (t − 2) · 2j−1. Thus |pq| ≤ (1 + 4/(t − 2))|pq*| = (1 + ε)|pq*|. The theorem is proved.

We note that while we need c > 4 in order to construct and maintain the DefSpanner, if we are only interested in static nearest neighbor queries a DefSpanner with c > 2 would be sufficient, even though a DefSpanner may not be a spanner when c ≤ 4.

6.4. Closest pair and collision detection

Any (1 + ε)-spanner with ε < 1 must contain the edge between the closest pair, as shown in the following lemma. Thus a maintainable (1 + ε)-spanner, e.g., the DefSpanner, can be used to predict collisions between any pairs of points, since two points must have an edge in the spanner before they collide to each other.

Lemma 6.8. For a (1 + ε)-spanner G on a set S of points in Rd, ε < 1, the edge between the closest pair must be present in the spanner.

Proof. Assume that the closest pair p, q are not connected by an edge in G. Since the shortest path between p, q in G contains at least 2 edges, each of them is longer than |pq|, πG(p, q) > 2|pq|. This contradicts with the spanner property that πG(p, q) ≤ (1 + ε)|pq| < 2|pq|.

Theorem 6.9. For a set S of moving points in Rd, we have a linear-size kinetic data structure to maintain the closest pair of the point set. The KDS is efficient, local, compact and responsive.

Proof. We construct and maintain the (1 + ε) DefSpanner G as before with ε < 1. The edge between the closest pair is the shortest spanner edge. The DefSpanner has only linear number of edges. We simply use a kinetic tournament tree [22] to keep track of the shortest edge among all the spanner edges. The kinetic tournament tree is known to be efficient, local, compact and responsive. Thus our KDS to maintain the closest pair, by using the kinetic DefSpanner and the kinetic tournament tree, has all those good properties as well. Namely, the total size of the KDS is of linear size in the number of points. The update cost on a certificate failure is O(lg2 n). Each point is involved in O(lg n + lg α/εd) certificates. Each edge change in the DefSpanner triggers an edge insertion or deletion in the kinetic tournament tree. There are at most O(n2 lg α) edge changes in the DefSpanner. The kinetic tournament tree for an input with size m processes O(mlgm) events. By the efficiency of the kinetic tournament tree, the total number of events processed altogether can be bounded by O(n2 lgα lg n). Thus our KDS for maintaining the closest pair is efficient. This finishes the proof.

6.5. k-center

For a set S of points in Rd, we choose a set K of points, K [subset, dbl equals] S, |K| = k, and assign all the points in S to their closest point in K. The k-center problem is to find a K such that the maximum radius of the k-center, maxp[set membership]S minq[set membership]K |pq|, is minimized.

The discrete center hierarchy of DefSpanner implies an 8-approximate k-center for any k. We take the lowest level i such that |Si| ≤ k. If |Si| = k, then we take K = Si. If |Si| < k, we also add some (arbitrary) children of Si to K so that |K| = k.

Lemma 6.10. K is an 8-approximation of the optimal k-center.

Proof. On level i − 1 we have more than k points with distance at least 2i−1 pairwise apart. So in the optimal solution, at least two points in Si−1 are assigned to the same center. Thus the optimal k-center has maximum radius at least 2i−2. But K has radius at most 2i+1. So K is an 8-approximation to the optimal k-center solution.

Theorem 6.11. For a set S of n moving points in Rd, we can maintain an 8-approximate k-center via a kinetic data structure. This KDS is responsive, local and compact. Furthermore, for any fixed integer t ≥ 1, the KDS for the 8-approximate (nt)-center is efficient.

Proof. We first maintain a DefSpanner under motion. When the nodes in Si move, we update the approximate k-center as well. If a node p [set membership] Si is deleted from level i, we add children of Si to K to keep |K| = k. The only problem that needs to be clarified is when the number of centers at level i − 1 becomes k or less. However, since Si [subset, dbl equals] Si−1 and we take K to be Si and some children of Si, we thus smoothly switch from level i to level i − 1. The other event is when |Si| = k + 1, we simply take Si+1. Notice that Si+1 [subset, dbl equals] Si [subset, dbl equals] Si−1 so the update to K is O(1) per event. And K is changed at most O(n2 lg α) times.

To prove the efficiency of our KDS for k = nt where t ≥ 1 is a constant, we show that there exists a setting in which any c-approximate (nt)-center, where c > 1, has to change Ω(n2) times.

Let m = n/(2t) and fix a value γ > c. We arrange n points on a plane as in Fig. 9. First we group the n points into t groups Gi, 0 ≤ i < t. Each group Gi consists of m lower points at positions (γjm, 2γti), 0 ≤ j < m, and m upper points at positions (γj (m − 1), 2γti + 1), 0 ≤ j < m. Note that there are exactly t matched pairs of points that are exactly 1 unit distance apart in this arrangement, and the distance between all other pairs of points are at least γ > c. As a result, the radius of the optimal (nt)-center is 1, and any c-approximate (nt)-center must contain exactly one point in each of the t matched pairs (and the remaining n − 2t points are the unmatched points).

Fig. 9
Any c-approximate (nt)-centers must change Ω(n2/t2) times.

If we fix the lower points in all groups and let the upper points move to the right with the same velocity, every time the upper points move a distance xγ for each integer value of x between 1 and m(m − 1), we have a different set of t matched pairs of points, and thus any c-approximate (nt)-center must change. It follows that any c-approximate (nt)-center must change at least m(m − 1) = Ω(n2/t2) times.

Remark Notice that the spanner actually gives an approximate solution to a set of k-center problems with different k simultaneously. We can maintain j subsets K1, K2,…, Kj such that Ki is an 8-approximation of the optimal ki-center, where 0 ≤ kin. The update cost per event is O(j + lg α).

We also note that there exists a situation and a certain k where the optimal k-center undergoes Ω(n3) changes, as the example in [17]. In fact, that example shows that there is a value k such that k-center with approximation ratio < 1.5 has to change Ω(n3) times. On the other hand, any point is a 2-approximation 1-center and thus 2-approximation 1-center does not have to change when the points move. The efficiency of our KDS for approximate k-center for a full spectrum of k is still not well understood.

7. Conclusion and future work

In this paper we have introduced a hierarchical construction that yields a spanner for a set of n points in Rd under the Euclidean metric. The key property of this spanner is that it can be maintained easily under point insertion, deletion, or motion. We have shown that the DefSpanner allows a wide variety of proximity queries to be answered efficiently and provides the first known such structure that can be maintained under motion.

A theoretical weakness of our structure is that, while our structure always has linear size, the efficiency of its maintenance under motion depends on the assumption that the aspect ratio α of the point set is bounded by a polynomial in the number of points. Removing this assumption is a topic for future research.

Fig. 5
There exists a path in G between any two points p and q with length at most (1 + ε)|pq|.

Acknowledgements

This research was supported in part by NSF grants CCR-0204486 and ITR-0205671, NIH Simbios Center grant 1091129-1-PABAE, ONR MURI grant N0014-02-1-0720, and the Defense Advanced Research Projects Agency (DARPA) under contract number F30602-00-C-0139 through the Sensor Information Technology Program. Jie Gao was also supported by an IBM Ph.D. fellowship. The authors wish to thank John Hershberger for useful discussions and in particular his contributions to Section 6.2, as well as anonymous reviewers for their suggestions to improve the paper.

Footnotes

1Work was done when the author was with Computer Science Department, Stanford University.

2Unless explicitly specified, we assume the base of log is 2, denoted by lg.

3The distance between two point sets A, B is defined as the minimum distance of two points p, q, with p [set membership] A and q [set membership] B.

4For a set of points S in the plane, the minimum Steiner tree is a tree in the plane with minimum total weight that connects all the points in S.

References

1. Agarwal P, Basch J, Guibas L, Hershberger J, Zhang L. Deformable free space tilings for kinetic collision detection. Internat. J. Robot. Res. 2002;21(3):179–197.
2. Arya S, Das G, Mount DM, Salowe JS, Smid M. Euclidean spanners: Short, thin, and lanky; Proc. 27th ACM Symposium on Theory Computing; 1995. pp. 489–498.
3. Arya S, Malamatos T. Linear-size approximate Voronoi diagrams; Proc. of the 13th ACM-SIAM Symposium on Discrete Algorithms; 2002. pp. 147–155.
4. Arya S, Malamatos T, Mount DM. Space-efficient approximate Voronoi diagrams; Proc. of the 34th ACM Symposium on Theory of Computing; 2002. pp. 721–730.
5. Arya S, Mount DM, Netanyahu NS, Silverman R, Wu AY. An optimal algorithm for approximate nearest neighbor searching fixed dimensions. J. ACM. 1998;45(6):891–923.
6. Arya S, Mount DM, Smid M. Randomized and deterministic algorithms for geometric spanners of small diameter; Proc. 35th IEEE Symposium on Foundations of Computer Science; 1994. pp. 703–712.
7. Arya S, Smid M. Efficient construction of a bounded-degree spanner with low weight. Algorithmica. 1997;17:33–54.
8. Basch J, Guibas L, Hershberger J. Data structures for mobile data. J. Alg. 1999;31(1):1–28.
9. Callahan, Kosaraju Faster algorithms for some geometric graph problems in higher dimensions; Proc. 4th ACM-SIAM Symposium on Discrete Algorithms; 1993. pp. 291–300.
10. Callahan PB. Optimal parallel all-nearest-neighbors using the well-separated pair decomposition; Proc. 34th IEEE Symposium on Foundations of Computer Science; 1993. pp. 332–340.
11. Callahan PB, Kosaraju SR. Algorithms for dynamic closest-pair and n-body potential fields; Proc. 6th ACM-SIAM Symposium on Discrete Algorithms; 1995. pp. 263–272.
12. Callahan PB, Kosaraju SR. A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields. J. ACM. 1995;42:67–90.
13. Dickerson MT, Drysdale RL, Sack JR. Simple algorithms for enumerating interpoint distances and finding k nearest neighbors. Internat. J. Comput. Geom. Appl. 1992;2(3):221–239.
14. Eppstein D. Spanning trees and spanners. In: Sack J-R, Urrutia J, editors. Handbook of Computational Geometry. North-Holland, Amsterdam: Elsevier Science Publishers B.V.; 2000. pp. 425–461.
15. Erickson J. Dense point sets have sparse Delaunay triangulations; Proc. 13th ACM-SIAM Symposium on Discrete Algorithms; 2002. pp. 125–134.
16. Feder T, Greene DH. Optimal algorithms for approximate clustering; Proc. 20th Annu. ACM Symposium on Theory Comput; 1988. pp. 434–444.
17. Gao J, Guibas L, Hershberger J, Zhang L, Zhu A. Discrete mobile centers. Discrete Comput. Geom. 2003;30(1):45–63.
18. Gao J, Guibas LJ, Nguyen A. Distributed proximity maintenance in ad hoc mobile networks; Proceedings of the IEEE International Conference on Distributed Computing in Sensor Systems (DCOSS); 2005. pp. 4–19.
19. Gonzalez T. Clustering to minimize the maximum intercluster distance. Theoret. Comput. Sci. 1985;38:293–306.
20. Gudmundsson J, Levcopoulos C, Narasimhan G, Smid M. Approximate distance oracles for geometric graphs; Proc. 13th ACM-SIAM Symposium on Discrete Algorithms; 2002. pp. 828–837.
21. Guibas L, Nguyen A, Russel D, Zhang L. Collision detection for deforming necklaces; Proc. 18th ACM Symposium on Computational Geometry; 2002. pp. 33–42.
22. Guibas LJ. Kinetic data structures—a state of the art report. In: Agarwal PK, Kavraki LE, Mason M, editors. Proc. Workshop Algorithmic Found. Robot. Wellesley, MA: A.K. Peters; 1998. pp. 191–209.
23. Gupta A, Krauthgamer R, Lee JR. Bounded geometries, fractals, and low-distortion embeddings; Proc. the 44th Annual IEEE Symposium on Foundations of Computer Science; 2003. pp. 534–543.
24. Hershberger J. Smooth kinetic maintenance of clusters; Proc. ACM Symposium on Computational Geometry; 2003. pp. 48–57.
25. Indyk P, Motwani R. Approximate nearest neighbors: Towards removing the curse of dimensionality; Proc. 30th Annu. ACM Sympos. Theory Comput; 1998. pp. 604–613.
26. Krauthgamer R, Lee JR. Navigating nets: Simple algorithms for proximity search; Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics; 2004. pp. 798–807.
27. Lenhof HP, Smid M. Sequential and parallel algorithms for the k closest pairs problem. Internat. J. Comput. Geom. Appl. 1995;5:273–288.
28. Levcopoulos C, Narasimhan G, Smid MHM. Improved algorithms for constructing fault-tolerant spanners. Algorithmica. 2002;32(1):144–156.
29. Lin MC, Canny JF. A fast algorithm for incremental distance calculation; IEEE International Conference on Robotics and Automation; 1991. pp. 1008–1014.
30. Lotan I, Schwarzer F, Halperin D, Latombe J-C. Efficient maintenance and self-collision testing for kinematic chains; Proc. of the 18th ACM Symposium on Computational Geometry; 2002. pp. 43–52.
31. Narasimhan G, Smid M. Approximating the stretch factor of Euclidean graphs. SIAM J. Comput. 2000;30:978–989.
32. Pai DK. STRANDS: Interactive simulation of thin solids using Cosserat models. Computer Graphics Forum. 2002;21(3):347–352.
33. Peleg D. Distributed Computing: A Locality Sensitive Approach, Monographs on Discrete Mathematics and Applications. SIAM. 2000
34. Salowe JS. Enumerating interdistances in space. Internat. J. Comput. Geom. Appl. 1992;2:49–59.
35. Sullivan JM. Sphere packings give an explicit bound for the Besicovitch covering theorem. J. Geom. Anal. 1994;2(2):219–230.
36. Vazirani VV. Approximation Algorithms. Universitext, Springer-Verlag; 2001.