期刊
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS
卷 35, 期 1-2, 页码 2-19出版社
ELSEVIER
DOI: 10.1016/j.comgeo.2005.10.001
关键词
spanner graphs; kinetic data structures; proximity maintenance; collision detection; approximate nearest neighbor; well-separated pair decomposition; geometric k-center
资金
- NIGMS NIH HHS [U54 GM072970-05, U54 GM072970] Funding Source: Medline
For a set S of points in R-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+epsilon)-spanner with O(n/epsilon(d)) edges, where E 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. (c) 2005 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据