Home | About | Journals | Submit | Contact Us | Français |

**|**HHS Author Manuscripts**|**PMC3001688

Formats

Article sections

- Abstract
- 1. Introduction
- 2. Specific contributions
- 3. The deformable spanner
- 4. Construction and dynamic maintenance
- 5. Maintenance under motion
- 6. Applications
- 7. Conclusion and future work
- References

Authors

Related links

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.001PMCID: PMC3001688

NIHMSID: NIHMS197037

Jie Gao: ude.bsynus.sc@oagj; Leonidas J. Guibas: ude.drofnats.scihparg@sabiug; An Nguyen: ude.drofnats.scihparg@neyugna

See other articles in PMC that cite the published article.

For a set *S* of points in ^{d}, 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(*n*/ε^{d}) 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.

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 ^{d}, 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.

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 ^{d} under the Euclidean metric. We study the properties and applications of such a spanner. Our spanner has O(*n*/ε^{d}) 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.

The points shown are nearly cocircular. The Delaunay triangulation could change dramatically even when the points move ever so slightly.

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—Ω(*n*^{2}) 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.

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

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.

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(*n*^{4/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(*n*/ε^{d}) that allows self-collision detection in O(*n*) time.

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.

The concept of a well-separated pair decomposition for a set of points in ^{d} was first proposed by Callahan and Kosaraju [12]. A pair of point sets (*A, B*) is *s-well-separated* if the distance^{3} 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,9–12,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.

The DefSpanner we propose can be used to output the approximate nearest neighbor of any point *p* ^{d} with respect to the point set *S*, in time O(lg *n*/ε^{d}). There has been a lot of work on data structures to answer approximate nearest neighbor queries quickly [3–5,25]. However, they all try to minimize the storage or query cost and do not consider points in motion.

For a set *S* of points in ^{d}, the *k*-center is a set *K* of points, *K* *S*, |*K*| = *k*, such that max_{pS} min_{qK} |*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.

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 ^{d} with aspect ratio α, we have,

- A (1 + ε)-spanner with O(
*n*/ε^{d}) 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(
*n*/ε^{d}); - 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 <*k*≤*n*.

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.

In this paper we focus on a set *S* of points in the Euclidean space ^{d}. 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 α.

A set of *discrete centers* with radius *r* for a given point set *S* is defined as a maximal subset *S*′ *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 *S*_{0} ⊃ *S*_{1} ⊃ ⊃ *S _{h}* such that

For a discrete center hierarchy {*S _{i}*}, the DefSpanner

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 *S _{i}*. A center q

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

**Lemma 3.1**

*S*_{i}*S*_{i−1}.*For any two points p, q**S*, |_{i}*pq*| ≥ 2^{i}.*If**q*^{(i)}*C*(_{i}*p*^{(i+1)})*and q*≠*p*,*then**q*^{(i)}*N*(_{i}*p*^{(i)}),*i.e. there is an edge from each point q to its parent*.*The hierarchy has at most*lgα*levels*.*For any point p, define the parent chain from p**S*_{0}*to its ancestor**P*^{(i)}(*p*)*S*_{i}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*2^{i+1}.*Thus p’s ancestor**P*^{(i)}(*p*)*S*_{i}*is of a Euclidean distance at most*2^{i+1}*away from p*.

**Proof.** The first three claims are obvious. For the fourth claim, an *i*th level center *p* *S _{i}* has radius 2

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* *S*_{0} we find the smallest level *i* so that there is an edge between their ancestors *P*^{(i)}(*p*) and *P*^{(i)}(*q*). Define *p _{i}* =

First, we have that |*p _{i}q_{i}*| ≤

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* ^{d} *are of at least a distance r away from each other, then there are at most* (2*R/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} = (2*R/r* + 1)^{d} such balls.

Using Lemma 3.3, we have:

**Lemma 3.4.** *Each point in S _{i} covers at most* 5

**Lemma 3.5.** *A point p* _{Si} *has at most* (1 + 2*c*)^{d} − 1 *edges with other points of S _{i}*.

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 *S*_{i−1} covered by a point in *S _{i}* is 19 in

**Lemma 3.6.** *The maximum degree of G is* (1 + 2*c*)^{d}lgα.

**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(4*c*)^{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(4*c*)^{d} edges.

Let *p* and *q* be the closest pair of points in *G* and let *k* = lg|*pq*|. As *p* and *q* cannot be both in *S*_{k+1}, we assume without lost of generality that *p* is not in *S*_{k+1}. Since *p* is at least 2^{k} 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 + 2*c*/2^{j})^{d} − 1 ≤ (4*c*/2^{j})^{d} − 1 edges in *S*_{k−j}, for all 0 ≤ *j* ≤ lg *c*. The total number of edges incident on *p* is thus at most $\sum}_{j=0}^{\text{lg}\phantom{\rule{thinmathspace}{0ex}}c}({(4c/{2}^{j})}^{d}-1)<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 *S _{i}*. We charge the edges in

To summarize, we have,

**Theorem 3.9.** *For a set of n points in* ^{d} *with aspect ratio* α, *we can construct a* (1 + ε)-*spanner G so that the total number of edges in G is* O(*n*/ε^{d}), *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 lgα 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 *S _{i}*, |

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 *S _{i}* for −∞ <

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)} *N _{i}*(

**Proof.** If *q*^{(i)} *N _{i}*(

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 *n*th 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* · 2^{M}, 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 *S _{i}*, we compute

We then traverse the hierarchy from the bottom up and clean up the hierarchy of discrete centers. We find the highest level *S _{i}* and the point

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

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)}, *q* ≠ *p*. 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 *S*^{i+1}, it must be inserted into *S*_{i+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(lg^{2} α/ε^{d}). However notice that for any level *S _{i}*, all children of

**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}).

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.

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.

- A
*parent-child certificate*certifies that a child*p*is within distance 2^{i+1}from its parent in level*i*+ 1. - An
*edge certificate*certifies that a neighbor*q*of*p*at level*i*is within distance*c*· 2^{i}. - A
*separation certificate*certifies that a neighbor*q*of*p*at level*i*is of distance 2^{i}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. - A
*potential neighbor certificate*certifies that a potential neighbor of*p*at level*i*is of distance*c*· 2^{i}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*), *N _{i}*(

*Addition of a spanner edge*. When a potential neighbor certificate fails, i.e., a potential neighbor*q*of*p*comes within a distance*c*· 2^{i}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*.*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*· 2^{i}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*.*Promotion of a node*. When a parent-child certificate fails, i.e.,*q*=*P*(*p*) no longer covers*p*, |*pq*| > 2^{i+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.*Demotion of a node*. When a separation certificate fails, i.e., a neighbor*q*of*p*comes within a distance of 2^{i}, 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(*n*/ε^{d}), 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(*n*^{2} lg α) since an event only happens when the distance between two points becomes either 2^{i} or *c* · 2^{i} 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)).

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* Ω(*n*^{2}/*c*^{2}) *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 2*c*. The two segments are connected by a bent segment with 2*n* balls. The total number of balls in the necklace is 10*n*. 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.

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 Ω(*n*^{2}/*c*^{2}). Since the spanner starts with O(*n*) edges. there must be at least Ω(*n*^{2}/*c*^{2}) changes of any linear-size *c*-spanner.

On the other hand, there are O(*n*^{2}) pairs of points, and each pair of points can generate at most O(lg α) events when the distance between them equals either 2^{i} or *c* · 2^{i} for some integer *i*, 0 ≤ *i* ≤ lgα. The number of events that our spanner KDS has to handle is thus at most O(*n*^{2} 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(*n*^{2} 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*.

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 2^{i}, 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) · 2^{i} *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 *p*_{1}, *q*_{1}, *r*_{1}, *s*_{1} and *p*_{2}, *q*_{2}, *r*_{2}, *s*_{2} be the positions of the centers in the two time frames respectively. If *p*_{2} and *q*_{2} are neighbors, then |*r*_{2}*s*_{2}| ≤ |*r*_{2}*r*_{1}| + |*r*_{1}*p*_{1}| + |*p*_{1}*p*_{2}| + |*p*_{2}*q*_{2}| + |*q*_{2}*q*_{1}| + |*q*_{1}*s*_{1}| + |*s*_{1}*s*_{2}| ≤ (*c* − 4) · 2^{i} + 2 · 2^{i+1} + *c* · 2^{i} = *c* · 2^{i+1}, and thus *r*_{2} = *s*_{2} or *r*_{2} and *s*_{2} 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.

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(*n*/ε^{d}).

**Proof.** For nodes *p*^{(i)} and *q*^{(i)} in the spanner, we denote by *P _{i}* and

Note that all points in *P _{i}* (or

By Lemma 3.4, each point covers at most 5^{d} 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 5^{2d} the number of edges in DefSpanner. Thus *C* has size O(*n*/ε^{d}).

**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 (*P _{i}, Q_{i}*) where

On the other hand, there exists a set of *n* points such that any linear-size *c*-well-separated pair decomposition has to change Ω(*n*^{2}/*c*^{2}) 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 Ω(*n*^{2}/*c*^{2}), so is the total number of changes.

The near neighbors query for a set of points, i.e., for each point *p*, returning all the points within distance 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* · , where *s* is the stretch factor. Due to the spanning property, this guarantees that we find all the points within distance from *p*. Furthermore, we only check the pairs with distance at most *s* · . 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* · will not differ significantly with the number of pairs within distance . 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* ^{d}, *denote by* χ () *the number of ordered pairs* (*p, q*), *p, q* *S such that* |*pq*| ≤ , *then* χ (*s* · ) ≤ (2(2*s* + 3)^{d} + 1) χ () + *n*(2*s* + 3)^{d}.

**Proof.** We first select a set of discrete centers *S*_{/2} with radius /2 from points *S*. We then assign a point *q* to a center *p* if |*pq*| ≤ /2. A point can be within distance /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* *S*_{/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*)), *p* ≠ *q* such that the distance between *H*(*p*) and *H*(*q*) is at most *s* · . By triangular inequality, |*pq*| ≤ (*s* + 1) · . Using Lemma 3.3, the number of such *q*’s that (*H*(*p*), *H*(*q*)) Ψ is at most (2*s* + 3)^{d}. Thus Ψ has at most (2*s* + 3)^{d}*n* ordered pairs.

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

$$\chi (\ell )\ge {\displaystyle \sum _{p\in {S}_{\ell /2}}k(p)(k(p)-1).}$$

(1)

Furthermore, any ordered pairs (*p*′, *q*′) with < |*p*′*q*′| ≤ *s* · are covered by some pair (*H*(*p*), *H*(*q*)) Ψ. Thus we have

$$\chi (s\xb7\ell )-\chi (\ell )\le {\displaystyle \sum _{(H(p),H(q))\in \Psi}k(p)k(q)}.$$

(2)

Using the inequality *ab* ≤ *a*(*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

$$\sum _{(H(p),H(q))\in \Psi}k(p)k(q)}\le 2{(2s+3)}^{d}{\displaystyle \sum _{p\in {S}_{\ell /2}}k(p)(k(p)-1)}+n{(2s+3)}^{d}.$$

(3)

Combining (3) with inequalities (1) and (2), we have χ (*s* · )− χ () ≤ 2(2*s* + 3)^{d} χ () + *n*(2*s* + 3)^{d}, which implies χ (*s* · ) ≤ (2(2*s* + 3)^{d} + 1) χ () + *n*(2*s* + 3)^{d}.

**Theorem 6.4.** *For a set S of points in* ^{d}, *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* *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* · that include all pairs with distance no more than . We then filter out unnecessary pairs and only keep the pairs within distance . From Theorem 6.3, χ (*s*) ≤ (2(2*s* + 3)^{d} + 1)*k* + *n*(2*s* + 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* · is not proportional to those within distance

An *s*-approximate nearest neighbor of a point *p* ^{d} with respect to a point set *S* is a point *q* *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* ^{d}, *we can perform the* (1 + ε)-*nearest neighbors query in* O(lg α/ε^{d}) *time, i.e., given a point p* ^{d} *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* · 2^{i−1} < |*pq*| ≤ *c* ·2^{i}. Then for the level *j* ≤ *i* − 1, there is no edge attached with point *p*. Otherwise that edge would have shorter distance than *pq*. Therefore for each point *p* *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* *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* ^{d}, *we can maintain a kinetic data structure of size* O(*n*/ε^{d}) *that keeps the* (1 + ε)-*nearest neighbor in S of any node p* *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 Ω(*n*^{2}ε^{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* ^{d}, *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* ^{d}, *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 *W _{i}* = {

First of all, we notice that |*W _{i}*| = O(

At the end of the traversal of the DefSpanner, let *q* be the point closest to *p* in *W*_{0}. We will show that *q* is a (1 + ε)-nearest neighbor of *p*. Let *q** *S*_{0} be the closest point to *p* among all points in the spanner. If *q** is in *W*_{0}, then clearly |*pq*| = |*pq**|, and we are done. If not, let *j* be the level such that *P*^{(j−1)}(*q**) *W*_{j−1} and *P*^{(j)}(*q**) *W _{j}*. By definition of

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.

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* ^{d}, ε < 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* ^{d}, *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(lg^{2} *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(*n*^{2} lg α) edge changes in the DefSpanner. The kinetic tournament tree for an input with size *m* processes O(*m*lg*m*) events. By the efficiency of the kinetic tournament tree, the total number of events processed altogether can be bounded by O(*n*^{2} lgα lg *n*). Thus our KDS for maintaining the closest pair is efficient. This finishes the proof.

For a set *S* of points in ^{d}, we choose a set *K* of points, *K* *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, max_{pS} min_{qK} |*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 |*S _{i}*| ≤

**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 2^{i−1} pairwise apart. So in the optimal solution, at least two points in *S*_{i−1} are assigned to the same center. Thus the optimal *k*-center has maximum radius at least 2^{i−2}. But *K* has radius at most 2^{i+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* ^{d}, *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* (*n* − *t*)-*center is efficient*.

**Proof.** We first maintain a DefSpanner under motion. When the nodes in *S _{i}* move, we update the approximate

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

Let *m* = *n*/(2*t*) 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 *G _{i}*, 0 ≤

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 (*n* − *t*)-center must change. It follows that any *c*-approximate (*n* − *t*)-center must change at least *m*(*m* − 1) = Ω(*n*^{2}/*t*^{2}) 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 *K*_{1}, *K*_{2},…, *K*_{j} such that *K*_{i} is an 8-approximation of the optimal *k _{i}*-center, where 0 ≤

We also note that there exists a situation and a certain *k* where the optimal *k*-center undergoes Ω(*n*^{3}) 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 Ω(*n*^{3}) 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.

In this paper we have introduced a hierarchical construction that yields a spanner for a set of *n* points in ^{d} 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.

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.

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

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

^{3}The distance between two point sets *A, B* is defined as the minimum distance of two points *p, q*, with *p* *A* and *q* *B*.

^{4}For 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*.

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.

PubMed Central Canada is a service of the Canadian Institutes of Health Research (CIHR) working in partnership with the National Research Council's national science library in cooperation with the National Center for Biotechnology Information at the U.S. National Library of Medicine(NCBI/NLM). It includes content provided to the PubMed Central International archive by participating publishers. |