×

Deformable spanners and applications. (English) Zbl 1102.65024

Summary: For a set \(S\) of points in \(\mathbb 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+\varepsilon )\)-spanner with O\((n/\varepsilon ^{d})\) edges, where \(\varepsilon\) 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.

MSC:

65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
05C85 Graph algorithms (graph-theoretic aspects)

Software:

Strands
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Agarwal, P.; Basch, J.; Guibas, L.; Hershberger, J.; Zhang, L., Deformable free space tilings for kinetic collision detection, Internat. J. Robot. Res., 21, 3, 179-197 (2002)
[2] S. Arya, G. Das, D.M. Mount, J.S. Salowe, M. Smid, Euclidean spanners: Short, thin, and lanky, in: Proc. 27th ACM Symposium on Theory Computing, 1995, pp. 489-498; S. Arya, G. Das, D.M. Mount, J.S. Salowe, M. Smid, Euclidean spanners: Short, thin, and lanky, in: Proc. 27th ACM Symposium on Theory Computing, 1995, pp. 489-498 · Zbl 0968.68533
[3] S. Arya, T. Malamatos, Linear-size approximate Voronoi diagrams, in: Proc. of the 13th ACM-SIAM Symposium on Discrete Algorithms, 2002, pp. 147-155; S. Arya, T. Malamatos, Linear-size approximate Voronoi diagrams, in: Proc. of the 13th ACM-SIAM Symposium on Discrete Algorithms, 2002, pp. 147-155 · Zbl 1058.65019
[4] S. Arya, T. Malamatos, D.M. Mount, Space-efficient approximate Voronoi diagrams, in: Proc. of the 34th ACM Symposium on Theory of Computing, 2002, pp. 721-730; S. Arya, T. Malamatos, D.M. Mount, Space-efficient approximate Voronoi diagrams, in: Proc. of the 34th ACM Symposium on Theory of Computing, 2002, pp. 721-730 · Zbl 1192.68727
[5] Arya, S.; Mount, D. M.; Netanyahu, N. S.; Silverman, R.; Wu, A. Y., An optimal algorithm for approximate nearest neighbor searching fixed dimensions, J. ACM, 45, 6, 891-923 (1998) · Zbl 1065.68650
[6] S. Arya, D.M. Mount, M. Smid, Randomized and deterministic algorithms for geometric spanners of small diameter, in: Proc. 35th IEEE Symposium on Foundations of Computer Science, 1994, pp. 703-712; S. Arya, D.M. Mount, M. Smid, Randomized and deterministic algorithms for geometric spanners of small diameter, in: 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, 17, 33-54 (1997) · Zbl 0864.68108
[8] Basch, J.; Guibas, L.; Hershberger, J., Data structures for mobile data, J. Alg., 31, 1, 1-28 (1999) · Zbl 0928.68034
[9] Callahan, Kosaraju, Faster algorithms for some geometric graph problems in higher dimensions, in: Proc. 4th ACM-SIAM Symposium on Discrete Algorithms, 1993, pp. 291-300; Callahan, Kosaraju, Faster algorithms for some geometric graph problems in higher dimensions, in: Proc. 4th ACM-SIAM Symposium on Discrete Algorithms, 1993, pp. 291-300 · Zbl 0801.68136
[10] P.B. Callahan, Optimal parallel all-nearest-neighbors using the well-separated pair decomposition, in: Proc. 34th IEEE Symposium on Foundations of Computer Science, 1993, pp. 332-340; P.B. Callahan, Optimal parallel all-nearest-neighbors using the well-separated pair decomposition, in: Proc. 34th IEEE Symposium on Foundations of Computer Science, 1993, pp. 332-340
[11] P.B. Callahan, S.R. Kosaraju, Algorithms for dynamic closest-pair and \(n\); P.B. Callahan, S.R. Kosaraju, Algorithms for dynamic closest-pair and \(n\) · Zbl 0849.68091
[12] Callahan, P. B.; Kosaraju, S. R., A decomposition of multidimensional point sets with applications to \(k\)-nearest-neighbors and \(n\)-body potential fields, J. ACM, 42, 67-90 (1995) · Zbl 0886.68078
[13] Dickerson, M. T.; Drysdale, R. L.; Sack, J. R., Simple algorithms for enumerating interpoint distances and finding \(k\) nearest neighbors, Internat. J. Comput. Geom. Appl., 2, 3, 221-239 (1992) · Zbl 0759.68033
[14] Eppstein, D., Spanning trees and spanners, (Sack, J.-R.; Urrutia, J., Handbook of Computational Geometry (2000), Elsevier Science Publishers B.V., North-Holland: Elsevier Science Publishers B.V., North-Holland Amsterdam), 425-461 · Zbl 0944.05021
[15] J. Erickson, Dense point sets have sparse Delaunay triangulations, in: Proc. 13th ACM-SIAM Symposium on Discrete Algorithms, 2002, pp. 125-134; J. Erickson, Dense point sets have sparse Delaunay triangulations, in: Proc. 13th ACM-SIAM Symposium on Discrete Algorithms, 2002, pp. 125-134 · Zbl 1058.65025
[16] T. Feder, D.H. Greene, Optimal algorithms for approximate clustering, in: Proc. 20th Annu. ACM Symposium on Theory Comput., 1988, pp. 434-444; T. Feder, D.H. Greene, Optimal algorithms for approximate clustering, in: 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., 30, 1, 45-63 (2003) · Zbl 1038.68131
[18] J. Gao, L.J. Guibas, A. Nguyen, Distributed proximity maintenance in ad hoc mobile networks, in: Proceedings of the IEEE International Conference on Distributed Computing in Sensor Systems (DCOSS), 2005, pp. 4-19; J. Gao, L.J. Guibas, A. Nguyen, Distributed proximity maintenance in ad hoc mobile networks, in: 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., 38, 293-306 (1985) · Zbl 0567.62048
[20] J. Gudmundsson, C. Levcopoulos, G. Narasimhan, M. Smid, Approximate distance oracles for geometric graphs, in: Proc. 13th ACM-SIAM Symposium on Discrete Algorithms, 2002, pp. 828-837; J. Gudmundsson, C. Levcopoulos, G. Narasimhan, M. Smid, Approximate distance oracles for geometric graphs, in: Proc. 13th ACM-SIAM Symposium on Discrete Algorithms, 2002, pp. 828-837 · Zbl 1058.65028
[21] L. Guibas, A. Nguyen, D. Russel, L. Zhang, Collision detection for deforming necklaces, in: Proc. 18th ACM Symposium on Computational Geometry, 2002, pp. 33-42; L. Guibas, A. Nguyen, D. Russel, L. Zhang, Collision detection for deforming necklaces, in: Proc. 18th ACM Symposium on Computational Geometry, 2002, pp. 33-42 · Zbl 1077.68105
[22] Guibas, L. J., Kinetic data structures—a state of the art report, (Agarwal, P. K.; Kavraki, L. E.; Mason, M., Proc. Workshop Algorithmic Found. Robot. (1998), A.K. Peters: A.K. Peters Wellesley, MA), 191-209 · Zbl 0948.70502
[23] A. Gupta, R. Krauthgamer, J.R. Lee, Bounded geometries, fractals, and low-distortion embeddings, in: Proc. the 44th Annual IEEE Symposium on Foundations of Computer Science, 2003, pp. 534-543; A. Gupta, R. Krauthgamer, J.R. Lee, Bounded geometries, fractals, and low-distortion embeddings, in: Proc. the 44th Annual IEEE Symposium on Foundations of Computer Science, 2003, pp. 534-543
[24] J. Hershberger, Smooth kinetic maintenance of clusters, in: Proc. ACM Symposium on Computational Geometry, 2003, pp. 48-57; J. Hershberger, Smooth kinetic maintenance of clusters, in: Proc. ACM Symposium on Computational Geometry, 2003, pp. 48-57 · Zbl 1377.68283
[25] P. Indyk, R. Motwani, Approximate nearest neighbors: Towards removing the curse of dimensionality, in: Proc. 30th Annu. ACM Sympos. Theory Comput., 1998, pp. 604-613; P. Indyk, R. Motwani, Approximate nearest neighbors: Towards removing the curse of dimensionality, in: Proc. 30th Annu. ACM Sympos. Theory Comput., 1998, pp. 604-613 · Zbl 1029.68541
[26] Krauthgamer, R.; Lee, J. R., Navigating nets: Simple algorithms for proximity search, (Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms (2004), Society for Industrial and Applied Mathematics), 798-807 · Zbl 1318.68071
[27] Lenhof, H. P.; Smid, M., Sequential and parallel algorithms for the \(k\) closest pairs problem, Internat. J. Comput. Geom. Appl., 5, 273-288 (1995) · Zbl 0939.68877
[28] Levcopoulos, C.; Narasimhan, G.; Smid, M. H.M., Improved algorithms for constructing fault-tolerant spanners, Algorithmica, 32, 1, 144-156 (2002) · Zbl 0998.68226
[29] M.C. Lin, J.F. Canny, A fast algorithm for incremental distance calculation, in: IEEE International Conference on Robotics and Automation, 1991, pp. 1008-1014; M.C. Lin, J.F. Canny, A fast algorithm for incremental distance calculation, in: IEEE International Conference on Robotics and Automation, 1991, pp. 1008-1014
[30] I. Lotan, F. Schwarzer, D. Halperin, J.-C. Latombe, Efficient maintenance and self-collision testing for kinematic chains, in: Proc. of the 18th ACM Symposium on Computational Geometry, 2002, pp. 43-52; I. Lotan, F. Schwarzer, D. Halperin, J.-C. Latombe, Efficient maintenance and self-collision testing for kinematic chains, in: Proc. of the 18th ACM Symposium on Computational Geometry, 2002, pp. 43-52 · Zbl 1414.68132
[31] Narasimhan, G.; Smid, M., Approximating the stretch factor of Euclidean graphs, SIAM J. Comput., 30, 978-989 (2000) · Zbl 0966.68205
[32] Pai, D. K., STRANDS: Interactive simulation of thin solids using Cosserat models, Computer Graphics Forum, 21, 3, 347-352 (2002)
[33] Peleg, D., Distributed Computing: A Locality Sensitive Approach, Monographs on Discrete Mathematics and Applications (2000), SIAM · Zbl 0959.68042
[34] Salowe, J. S., Enumerating interdistances in space, Internat. J. Comput. Geom. Appl., 2, 49-59 (1992) · Zbl 0764.68179
[35] Sullivan, J. M., Sphere packings give an explicit bound for the Besicovitch covering theorem, J. Geom. Anal., 2, 2, 219-230 (1994) · Zbl 0797.52011
[36] Vazirani, V. V., Approximation Algorithms (2001), Universitext: Universitext Springer-Verlag · Zbl 1138.90417
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.