More Web Proxy on the site http://driver.im/

Article

Deformable spanners and applications

Authors:

Leonidas J. Guibas,

An NguyenAuthors Info & Claims

SCG '04: Proceedings of the twentieth annual symposium on Computational geometry

Pages 190 - 199

https://doi.org/10.1145/997817.997848

Published: 08 June 2004 Publication History

Abstract

For a set S of points in ℝ³, an s-spanner is a graph on 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 ofpoints, 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 decomposition, and approximate k-centers.

References

[1]

P. Agarwal, J. Basch, L. Guibas, J. Hershberger, and L. Zhang. Deformable free space tilings for kinetic collision detection. International Journal of Robotics Research, 21(3):179--197, 2002.

[2]

S. Arya, G. Das, D. M. Mount, J. S. Salowe, and M. Smid. Euclidean spanners: short, thin, and lanky. In Proc. 27th ACM Symposium on Theory Computing, pages 489--498, 1995.

Digital Library

[3]

S. Arya and T. Malamatos. Linear-size approximate voronoi diagrams. In Proc. of the 13th ACM-SIAM Symposium on Discrete Algorithms, pages 147--155, 2002.

Digital Library

[4]

S. Arya, T. Malamatos, and D. M. Mount. Space-efficient ap-proximate voronoi diagrams. In Proc. of the 34th ACM Sym-posium on Theory of Computing, pages 721--730, 2002.

Digital Library

[5]

S. Arya, D. M. Mount, N. S. Netanyahu, R. Silverman, and A.Y. Wu. An optimal algorithm for approximate nearest neighbor searching fixed dimensions. J. ACM, 45(6):891--923, 1998.

Digital Library

[6]

S. Arya, D. M. Mount, and M. Smid. Randomized and deter-ministic algorithms for geometric spanners of small diameter. In Proc. 35th IEEE Symposium on Foundations of Computer Science, pages 703--712, 1994.

Digital Library

[7]

S. Arya and M. Smid. Efficient construction of a bounded-degree spanner with low weight. Algorithmica, 17:33--54, 1997.

[8]

J. Basch, L. Guibas, and J. Hershberger. Data structures for mobile data. J. Alg., 31(1):1--28, 1999.

Digital Library

[9]

Callahan and Kosaraju. Faster algorithms for some geometric graph problems in higher dimensions. In Proc. 4th ACM-SIAM Symposium on Discrete Algorithms, pages 291--300, 1993.

Digital Library

[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, pages 332--340, 1993.

Digital Library

[11]

P. B. Callahan and S. R. Kosaraju. Algorithms for dynamic closest-pair and n-body potential fields. In Proc. 6th ACM-SIAM Symposium on Discrete Algorithms, pages 263--272, 1995.

Digital Library

[12]

P. B. Callahan and S. R. Kosaraju. Adecomposition of multidimensional point sets with applications to n-nearest-neighbors and n-body potential fields. J. ACM, 42:67--90, 1995.

Digital Library

[13]

M. T. Dickerson, R. L. Drysdale, and J. R. Sack. Simple algorithms for enumerating interpoint distances and finding k nearest neighbors. Internat. J. Comput. Geom. Appl., 2(3):221--239, 1992.

[14]

D. Eppstein. Spanning trees and spanners. In J.-R. Sack and J. Urrutia, editors, Handbook of Computational Geometry, pages 425--461. Elsevier Science Publishers B.V. North-Holland, Amsterdam, 2000.

[15]

J. Erickson. Dense point sets have sparse Delaunay triangulations. In Proc. 13th ACM-SIAM Sympos. Discrete Algorithms, pages 125--134, 2002.

Digital Library

[16]

T. Feder and D. H. Greene. Optimal algorithms for approximate clustering. In Proc. 20th Annu. ACM Sympos. Theory Comput., pages 434--444, 1988.

Digital Library

[17]

J. Gao, L. Guibas, J. Hershberger, L. Zhang, and A. Zhu. Discrete mobile centers. Discrete and Computational Geometry, 30(1):45--63, 2003.

[18]

T. Gonzalez. Clustering to minimize the maximum intercluster distance. Theoret. Comput. Sci., 38:293--306, 1985.

[19]

J. Gudmundsson, C. Levcopoulos, G. Narasimhan, and M. Smid. Approximate distance oracles for geometric graphs. In Proc. 13th ACM-SIAM Symposium on Discrete Algorithms, pages 828--837, 2002.

Digital Library

[20]

L. Guibas, A. Nguyen, D. Russel, and L. Zhang. Collision detection for deforming necklaces. In Proc. 18th ACM Symposium on Computational Geometry, pages 33--42, 2002.

Digital Library

[21]

L. J. Guibas. Kinetic data structures --a state of the art report. In P. K. Agarwal, L. E. Kavraki, and M. Mason, editors, Proc. Workshop Algorithmic Found. Robot., pages 191--209. A. K. Peters, Wellesley, MA, 1998.

Digital Library

[22]

J. Hershberger. Smooth kinetic maintenance of clusters. In Proc. ACM Symposium on Computational Geometry, pages 48--57, 2003.

Digital Library

[23]

P. Indyk and R. Motwani. Approximate nearest neighbors: Towards removing the curse of dimensionality. In Proc. 30th Annu. ACM Sympos. Theory Comput., pages 604--613, 1998.

Digital Library

[24]

H. P. Lenhof and M. Smid. Sequential and parallel algorithms for the k closest pairs problem. Internat. J. Comput. Geom. Appl., 5:273--288, 1995.

[25]

C. Levcopoulos, G. Narasimhan, and M. H. M. Smid. Improved algorithms for constructing fault-tolerant spanners. Algorithmica, 32(1):144--156, 2002.

Digital Library

[26]

M. C. Lin and J. F. Canny. A fast algorithm for incremental distance calculation. In IEEE International Conference on Robotics and Automation, pages 1008--1014, Apr. 1991.

[27]

I. Lotan, F. Schwarzer, D. Halperin, and J.-C. Latombe. Efficient maintenance and self-collision testing for kinematic chains. In Proc. of the 18th ACM Symposium on Computational geometry, pages 43--52, 2002.

Digital Library

[28]

G. Narasimhan and M. Smid. Approximating the stretch factor of Euclidean graphs. SIAM J. Comput., 30:978--989, 2000.

Digital Library

[29]

D. K. Pai. STRANDS: Interactive simulation of thin solids using cosserat models. In Eurographics, 2002.

[30]

D. Peleg. Distributed Computing: A Locality Sensitive Approach. Monographs on Discrete Mathematics and Applications. SIAM, 2000.

Digital Library

[31]

J. S. Salowe. Enumerating interdistances in space. Internat. J. Comput. Geom. Appl., 2:49--59, 1992.

[32]

J. M. Sullivan. Sphere packings give an explicit bound for the besicovitch covering theorem. The Journal of Geometric Analysis, 2(2):219--230, 1994.

Cited By

Le HSolomon SThan C(2023)Optimal Fault-Tolerant Spanners in Euclidean and Doubling Metrics: Breaking the Ω (log n) Lightness Barrier2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00013(77-97)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00013
Bartal YFandina ONeiman O(2022)Covering metric spaces by few treesJournal of Computer and System Sciences10.1016/j.jcss.2022.06.001130(26-42)Online publication date: Dec-2022
https://doi.org/10.1016/j.jcss.2022.06.001
Le HSolomon S(2019)Truly Optimal Euclidean Spanners2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS.2019.00069(1078-1100)Online publication date: Nov-2019
https://doi.org/10.1109/FOCS.2019.00069
Show More Cited By

Index Terms

Deformable spanners and applications
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
2. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

Deformable spanners and applications

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 ...
Geometric Spanners for Weighted Point Sets

Let ( S , d ) be a finite metric space, where each element p S has a non-negative weight w ( p ). We study spanners for the set S with respect to the following weighted distance function: $$\mathbf{d}_{\omega}(p,q)=\left\{\begin{array}{ll}0&\...
Kinetic spanners in R^d
SCG '09: Proceedings of the twenty-fifth annual symposium on Computational geometry

We present a new (1+ε)-spanner for sets of n points in R^d. Our spanner has size O(n/ε^d-1) and maximum degree O(log^d n). The main advantage of our spanner is that it can be maintained efficiently as the points move: Assuming the trajectories of the ...

Reviews

Reviewer: Jerzy W. Jaromczyk

An s -spanner graph in Euclidean space provides a sparse network of paths between pairs of points; the paths are at most s times longer than the distance between their endpoints. This paper presents the first data structure for sparse graphs that can be efficiently maintained when points are inserted, deleted, or continuously moved (as in a kinetic structure). The resulting 1+e-spanner, with O ( n /e d ) edges for points in R d , can be additionally used for the closest pair problem, approximate nearest neighbor searches, maintaining well-separated pair decompositions, and finding approximate k -centers. The spanners assume a bounded ratio between the greatest and least distances between points in the input set. Such a restriction is natural for modeling deformable shapes (vines, ropes, cloth, or proteins), and whenever physical constraints prevent too-close interactions, or too distant a separation of particles. Co-authored by L. Guibas, an authority in kinematic data structures, this paper sets a new direction of research, to study spanner maintenance under point motion. Online Computing Reviews Service

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SCG '04: Proceedings of the twentieth annual symposium on Computational geometry

June 2004

468 pages

ISBN:1581138857

DOI:10.1145/997817

Conference Chairs:
Jack Snoeyink
UNC Chapel Hill
,
Jean-Daniel Boissonnat
INRIA Sophia Antipolis

Copyright © 2004 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 June 2004

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SoCG04

Sponsor:

SoCG04: Annual ACM Symposium on Computational Geometry 2004

June 8 - 11, 2004

New York, Brooklyn, USA

Acceptance Rates

SCG '04 Paper Acceptance Rate 49 of 147 submissions, 33%;

Overall Acceptance Rate 625 of 1,685 submissions, 37%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

38
Total Citations
View Citations
441
Total Downloads

Downloads (Last 12 months)8
Downloads (Last 6 weeks)4

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Le HSolomon SThan C(2023)Optimal Fault-Tolerant Spanners in Euclidean and Doubling Metrics: Breaking the Ω (log n) Lightness Barrier2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00013(77-97)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00013
Bartal YFandina ONeiman O(2022)Covering metric spaces by few treesJournal of Computer and System Sciences10.1016/j.jcss.2022.06.001130(26-42)Online publication date: Dec-2022
https://doi.org/10.1016/j.jcss.2022.06.001
Le HSolomon S(2019)Truly Optimal Euclidean Spanners2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS.2019.00069(1078-1100)Online publication date: Nov-2019
https://doi.org/10.1109/FOCS.2019.00069
Huang LJiang SLi JWu X(2018)Epsilon-Coresets for Clustering (with Outliers) in Doubling Metrics2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS.2018.00082(814-825)Online publication date: Oct-2018
https://doi.org/10.1109/FOCS.2018.00082
Filtser ASolomon SGiakkoupis G(2016)The Greedy Spanner is Existentially OptimalProceedings of the 2016 ACM Symposium on Principles of Distributed Computing10.1145/2933057.2933114(9-17)Online publication date: 25-Jul-2016
https://dl.acm.org/doi/10.1145/2933057.2933114
Chan TGupta AMaggs BZhou S(2016)On Hierarchical Routing in Doubling MetricsACM Transactions on Algorithms10.1145/291518312:4(1-22)Online publication date: 16-Aug-2016
https://dl.acm.org/doi/10.1145/2915183
Gudmundsson JNarasimhan GSmid M(2016)Geometric SpannersEncyclopedia of Algorithms10.1007/978-1-4939-2864-4_167(846-852)Online publication date: 22-Apr-2016
https://doi.org/10.1007/978-1-4939-2864-4_167
Elkin MSolomon S(2015)Optimal Euclidean SpannersJournal of the ACM10.1145/281900862:5(1-45)Online publication date: 2-Nov-2015
https://dl.acm.org/doi/10.1145/2819008
Chan TLi MNing LSolomon S(2015)New Doubling SpannersSIAM Journal on Computing10.1137/13093098444:1(37-53)Online publication date: 10-Feb-2015
https://dl.acm.org/doi/10.1137/130930984
Chan TLi MNing L(2015)Sparse Fault-Tolerant Spanners for Doubling Metrics with Bounded Hop-Diameter or DegreeAlgorithmica10.1007/s00453-013-9779-y71:1(53-65)Online publication date: 1-Jan-2015
https://dl.acm.org/doi/10.1007/s00453-013-9779-y
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents