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

article

Linear-Time Algorithms for Geometric Graphs with Sublinearly Many Edge Crossings

Authors:

David Eppstein,

Michael T. Goodrich,

Darren StrashAuthors Info & Claims

SIAM Journal on Computing, Volume 39, Issue 8

Pages 3814 - 3829

https://doi.org/10.1137/090759112

Published: 01 December 2010 Publication History

Abstract

We provide linear-time algorithms for geometric graphs with sublinearly many edge crossings. That is, we provide algorithms running in $O(n)$ time on connected geometric graphs having $n$ vertices and $k$ pairwise crossings, where $k$ is smaller than $n$ by an iterated logarithmic factor. Specific problems that we study include Voronoi diagrams and single-source shortest paths. Our algorithms all run in linear time in the standard comparison-based computational model; hence, we make no assumptions about the distribution or bit complexities of edge weights, nor do we utilize unusual bit-level operations on memory words. Instead, our algorithms are based on a planarization method that “zeros in” on edge crossings, together with methods for applying planar separator decompositions to geometric graphs with sublinearly many crossings. Incidentally, our planarization algorithm also solves an open computational geometry problem of Chazelle for triangulating a self-intersecting polygonal chain having $n$ segments and $k$ crossings in linear time, for the case when $k$ is sublinear in $n$ by an iterated logarithmic factor.

References

[1]

P. K. Agarwal, Geometric partitioning and its applications, in Computational Geometry: Papers from the DIMACS Special Year, J. E. Goodman, R. Pollack, and W. Steiger, eds., AMS, Providence, RI, 1991, pp. 1-38.

[2]

R. J. Anderson and G. L. Miller, An optimal algorithm for intersecting line segments in the plane, Algorithmica, 6 (1991), pp. 859-868.

[3]

D. Armon and J. Reif, A dynamic separator algorithm, in Proceedings of the 3rd Workshop on Algorithms and Data Structures, Lecture Notes Comput. Sci. 709, Springer-Verlag, New York, Berlin, 1993, pp. 107-118.

[4]

F. Aurenhammer, Voronoi diagrams: A survey of a fundamental geometric data structure, ACM Comput. Surv., 23 (1991), pp. 345-405.

[5]

F. Aurenhammer and R. Klein, Voronoi diagrams, in Handbook of Computational Geometry, J.-R. Sack and J. Urrutia, eds., Elsevier Science Publishers/North-Holland, Amsterdam, 2000, pp. 201-290.

[6]

J. L. Bentley and T. A. Ottmann, Algorithms for reporting and counting geometric intersections, IEEE Trans. Comput., C-28 (1979), pp. 643-647.

[7]

J.-D. Boissonnat, O. Devillers, R. Schott, M. Teillaud, and M. Yvinec, Applications of random sampling to on-line algorithms in computational geometry, Discrete Comput. Geom., 8 (1992), pp. 51-71.

[8]

B. Chazelle, Triangulating a simple polygon in linear time, Discrete Comput. Geom., 6 (1991), pp. 485-524.

[9]

B. Chazelle, A minimum spanning tree algorithm with inverse-Ackermann type complexity, J. ACM, 47 (2000), pp. 1028-1047.

[10]

B. Chazelle and H. Edelsbrunner, An optimal algorithm for intersecting line segments in the plane, J. ACM, 39 (1992), pp. 1-54.

[11]

B. Chazelle and L. J. Guibas, Fractional cascading: I. A data structuring technique, Algorithmica, 1 (1986), pp. 133-162.

[12]

D. Cheriton and R. E. Tarjan, Finding minimum spanning trees, SIAM J. Comput., 5 (1976), pp. 724-742.

[13]

K. L. Clarkson, R. Cole, and R. E. Tarjan, Erratum: Randomized parallel algorithms for trapezoidal diagrams, Internat. J. Comput. Geom. Appl., 2 (1992), pp. 341-343.

[14]

K. L. Clarkson, R. Cole, and R. E. Tarjan, Randomized parallel algorithms for trapezoidal diagrams, Internat. J. Comput. Geom. Appl., 2 (1992), pp. 117-133.

[15]

K. L. Clarkson and P. W. Shor, Applications of random sampling in computational geometry, II, Discrete Comput. Geom., 4 (1989), pp. 387-421.

[16]

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 2nd ed., MIT Press, Cambridge, MA, 2001.

[17]

M. de Berg and O. Schwarzkopf, Cuttings and applications, Internat. J. Comput. Geom. Appl., 5 (1995), pp. 343-355.

[18]

F. Dehne, X. Deng, P. Dymond, A. Fabri, and A. A. Khokhar, A randomized parallel 3d convex hull algorithm for coarse grained multicomputers, in Proceedings of the Seventh Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA '95), New York, 1995, ACM, New York, pp. 27-33.

[19]

X. Deng and B. Zhu, A randomized algorithm for Voronoi diagram of line segments on coarse grained multiprocessors, in Parallel Processing Symposium, 1996, Proceedings of the 10th International Parallel Processing Symposium, Honolulu, HI, 1996, IEEE Computer Society Press, Piscataway, NJ, pp. 192-198.

[20]

G. Di Battista, P. Eades, R. Tamassia, and I. G. Tollis, Graph Drawing, Prentice-Hall, Upper Saddle River, NJ, 1999.

[21]

H. Edelsbrunner, J. W. Jaromczyk, J. W. Penny, and G. Świątek, Primal canoes: Optimal arrangements of segments, in Proceedings of the 3rd Canadian Conference on Computational Geometry, Burnaby, BC, 1991, pp. 224-227.

[22]

D. Eppstein, Spanning trees and spanners, in Handbook of Computational Geometry, J.-R. Sack and J. Urrutia, eds., Elsevier, New York, 2000, pp. 425-461.

[23]

D. Eppstein, Setting parameters by example, SIAM J. Comput., 32 (2003), pp. 643-653.

[24]

D. Eppstein, Z. Galil, G. F. Italiano, and T. H. Spencer, Separator based sparsification. I. Planarity testing and minimum spanning trees, J. Comput. Systems Sci., 52 (1996), pp. 3-27.

[25]

D. Eppstein and M. T. Goodrich, Studying (non-planar) road networks through an algorithmic lens, in Proceedings of the 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (GIS '08), New York, 2008, ACM, New York, pp. 1-10.

[26]

D. Eppstein, M. T. Goodrich, and D. Strash, Linear-time algorithms for geometric graphs with sublinearly many crossings, in Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '09), New York, 2009, SIAM, Philadelphia, pp. 150-159.

[27]

D. Eppstein, G. L. Miller, and S.-H. Teng, A deterministic linear time algorithm for geometric separators and its applications, in Proceedings of the 9th Annual ACM Symposium on Computational Geometry, San Diego, CA, 1993, ACM, New York, pp. 99-108.

[28]

M. Erwig, The graph Voronoi diagram with applications, Networks, 36 (2000), pp. 156-163.

[29]

J. W. Essam and M. E. Fisher, Some basic definitions in graph theory, Rev. Modern Phys., 42 (1970), pp. 271-288.

[30]

M. L. Fredman and R. E. Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, J. ACM, 34 (1987), pp. 596-615.

[31]

A. V. Goldberg, Scaling algorithms for the shortest paths problem, in Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '93), Austin, TX, 1993, SIAM, Philadelphia, pp. 222-231.

[32]

A. V. Goldberg and C. Harrelson, Computing the shortest path: $A^*$ search meets graph theory, in Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '05), Vancouver, BC, 2005, SIAM, Philadelphia, pp. 156-165.

[33]

M. T. Goodrich, Planar separators and parallel polygon triangulation, J. Comput. System Sci., 51 (1995), pp. 374-389.

[34]

M. T. Goodrich and R. Tamassia, Algorithm Design: Foundations, Analysis, and Internet Examples, John Wiley & Sons, New York, 2002.

[35]

R. L. Graham and F. F. Yao, Finding the convex hull of a simple polygon, J. Algorithms, 4 (1983), pp. 324-331.

[36]

S. Har-Peled, Constructing planar cuttings in theory and practice, SIAM J. Comput., 29 (2000), pp. 2016-2039.

[37]

M. R. Henzinger, P. Klein, S. Rao, and S. Subramanian, Faster shortest-path algorithms for planar graphs, J. Comput. System Sci., 55 (1997), pp. 3-23.

[38]

M. Holzer, F. Schulz, D. Wagner, and T. Willhalm, Combining speed-up techniques for shortest-path computations, J. Exp. Algorithmics, 10 (2005), article 2.5.

[39]

D. R. Karger, P. N. Klein, and R. E. Tarjan, A randomized linear-time algorithm to find minimum spanning trees, J. ACM, 42 (1995), pp. 321-328.

[40]

G. A. Klunder and H. N. Post, The shortest path problem on large-scale real-road networks, Networks, 48 (2006), pp. 182-194.

[41]

D. T. Lee, On finding the convex hull of a simple polygon, Internat. J. Comput. Inform. Sci., 12 (1983), pp. 87-98.

[42]

R. J. Lipton and R. E. Tarjan, A separator theorem for planar graphs, SIAM J. Appl. Math., 36 (1979), pp. 177-189.

[43]

M. Mareš, Two linear time algorithms for MST on minor closed graph classes, Arch. Math. (Brno), 40 (2004), pp. 315-320.

[44]

K. Mehlhorn, A faster approximation algorithm for the Steiner problem in graphs, Inform. Process. Lett., 27 (1988), pp. 125-128.

[45]

U. Meyer, Average-case complexity of single-source shortest-paths algorithms: Lower and upper bounds, J. Algorithms, 48 (2003), pp. 91-134.

[46]

G. L. Miller, Finding small simple cycle separators for 2-connected planar graphs, J. Comput. System Sci., 32 (1986), pp. 265-279.

[47]

G. L. Miller, S.-H. Teng, W. Thurston, and S. A. Vavasis, Separators for sphere-packings and nearest neighbor graphs, J. ACM, 44 (1997), pp. 1-29.

[48]

G. L. Miller, S.-H. Teng, W. Thurston, and S. A. Vavasis, Geometric separators for finite-element meshes, SIAM J. Sci. Comput., 19 (1998), pp. 364-386.

[49]

B. Mohar and C. Thomassen, Graphs on Surfaces, Johns Hopkins University Press, Baltimore, 2001.

[50]

J. Pach, Towards a Theory of Geometric Graphs, Contemp. Math. 342, AMS, Providence, RI, 2004.

[51]

R. Raman, Recent results on the single-source shortest paths problem, SIGACT News, 28:2 (1997), pp. 81-87.

[52]

E. A. Ramos, An optimal deterministic algorithm for computing the diameter of a three-dimensional point set, Discrete Comput. Geom., 26 (2001), pp. 233-244.

[53]

P. Sanders and D. Schultes, Highway hierarchies hasten exact shortest path queries, in Proceedings of the 17th European Symposium on Algorithms (ESA), Lecture Notes in Comput. Sci. 3669, Springer, New York, 2005, pp. 568-579.

[54]

R. Sedgewick and J. S. Vitter, Shortest paths in Euclidean graphs, Algorithmica, 1 (1986), pp. 31-48.

[55]

D. A. Spielman and S.-H. Teng, Disk packings and planar separators, in Proceedings of the 12th Annual ACM Symposium on Computational Geometry, ACM, New York, 1996, pp. 349-358.

[56]

M. Thorup, Undirected single-source shortest paths with positive integer weights in linear time, J. ACM, 46 (1999), pp. 362-394.

[57]

W. T. Trotter, Planar Graphs, DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 9, AMS, Providence, RI, 1993.

[58]

F. B. Zhan and C. E. Noon, Shortest path algorithms: An evaluation using real road networks, Transportation Sci., 32 (1998), pp. 65-73.

Cited By

Schwarz NStorandt S(2024)Efficient Computation of Crossing Components and Shortcut HullsCombinatorial Algorithms10.1007/978-3-031-63021-7_39(509-522)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1007/978-3-031-63021-7_39
Tapolcai JVass BHeszberger ZBíró JHay DKuipers FRónyai L(2018)A Tractable Stochastic Model of Correlated Link Failures Caused by DisastersIEEE INFOCOM 2018 - IEEE Conference on Computer Communications10.1109/INFOCOM.2018.8486218(2105-2113)Online publication date: 16-Apr-2018
https://dl.acm.org/doi/10.1109/INFOCOM.2018.8486218

Linear-Time Algorithms for Geometric Graphs with Sublinearly Many Edge Crossings
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
2. Theory of computation

Recommendations

Linear-time algorithms for geometric graphs with sublinearly many crossings
SODA '09: Proceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms

We provide linear-time algorithms for geometric graphs with sublinearly many crossings. That is, we provide algorithms running in O(n) time on connected geometric graphs having n vertices and k crossings, where k is smaller than n by an iterated ...
Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic $\tilde{O}(n^{5/3})$ Time

We present an explicit and efficient construction of additively weighted Voronoi diagrams on planar graphs. Let $G$ be a planar graph with $n$ vertices and $b$ sites that lie on a constant number of faces. We show how to preprocess $G$ in $\tilde O(nb^2)$ ...
All-pairs shortest paths for unweighted undirected graphs in o(mn) time

We revisit the all-pairs-shortest-paths problem for an unweighted undirected graph with n vertices and m edges. We present new algorithms with the following running times:

{ O(mn/log n) if m > n log n log log log n O(mn log log n/log n) if m > n log log ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image SIAM Journal on Computing

SIAM Journal on Computing Volume 39, Issue 8

August 2010

464 pages

ISSN:0097-5397

Issue’s Table of Contents

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 December 2010

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Schwarz NStorandt S(2024)Efficient Computation of Crossing Components and Shortcut HullsCombinatorial Algorithms10.1007/978-3-031-63021-7_39(509-522)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1007/978-3-031-63021-7_39
Tapolcai JVass BHeszberger ZBíró JHay DKuipers FRónyai L(2018)A Tractable Stochastic Model of Correlated Link Failures Caused by DisastersIEEE INFOCOM 2018 - IEEE Conference on Computer Communications10.1109/INFOCOM.2018.8486218(2105-2113)Online publication date: 16-Apr-2018
https://dl.acm.org/doi/10.1109/INFOCOM.2018.8486218

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents