Linear-time algorithms for geometric graphs with sublinearly many crossings

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Linear-time algorithms for geometric graphs with sublinearly many crossings

Full text

Pdf (1.78 MB)

Source

Symposium on Discrete Algorithms archive
Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms table of contents

New York, New York

Pages 150-159

Year of Publication: 2009

Authors

David Eppstein	University of California, Irvine
Michael T. Goodrich	University of California, Irvine
Darren Strash	University of California, Irvine

Publisher

Society for Industrial and Applied Mathematics Philadelphia, PA, USA

Bibliometrics

Downloads (6 Weeks): 12, Downloads (12 Months): 94, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

ABSTRACT

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 logarithmic factor. Specific problems 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 "zeroes in" on edge crossings, together with methods for extending 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

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	P. K. Agarwal. Geometric partitioning and its applications. In J. E. Goodman, R. Pollack, and W. Steiger, editors, Computational Geometry: Papers from the DI-MACS Special Year. American Mathematical Society, 1991.
	2	R. J. Anderson and G. L. Miller. An optimal algorithm for intersecting line segments in the plane. Algorithmica, 6:859--868, 1991.
	3	Deganit Armon , John H. Reif, A Dynamic Separator Algorithm, Proceedings of the Third Workshop on Algorithms and Data Structures, p.107-118, August 11-13, 1993
	4	Franz Aurenhammer, Voronoi diagrams—a survey of a fundamental geometric data structure, ACM Computing Surveys (CSUR), v.23 n.3, p.345-405, Sept. 1991 [doi>10.1145/116873.116880]
	5	F. Aurenhammer and R. Klein. Voronoi diagrams. In J.-R. Sack and J. Urrutia, editors, Handbook of Computational Geometry, pages 201--290. Elsevier Science Publishers B.V. North-Holland, Amsterdam, 2000.
	6	J. L. Bentley , T. A. Ottmann, Algorithms for Reporting and Counting Geometric Intersections, IEEE Transactions on Computers, v.28 n.9, p.643-647, September 1979 [doi>10.1109/TC.1979.1675432]
	7	Jean-Daniel Boissonnat , Olivier Devillers , René Schott , Monique Teillaud , Mariette Yvinec, Applications of random sampling to on-line algorithms in computational geometry, Discrete & Computational Geometry, v.8 n.1, p.51-71, 1992 [doi>10.1007/BF02293035]
	8	Bernard Chazelle, Triangulating a simple polygon in linear time, Discrete & Computational Geometry, v.6 n.5, p.485-524, 1991 [doi>10.1007/BF02574703]
	9	Bernard Chazelle, A minimum spanning tree algorithm with inverse-Ackermann type complexity, Journal of the ACM (JACM), v.47 n.6, p.1028-1047, Nov. 2000 [doi>10.1145/355541.355562]
	10	Bernard Chazelle , Herbert Edelsbrunner, An optimal algorithm for intersecting line segments in the plane, Journal of the ACM (JACM), v.39 n.1, p.1-54, Jan. 1992 [doi>10.1145/147508.147511]
	11	B. Chazelle and L. J. Guibas. Fractional cascading. In Proc. Internat. Colloq. Automata Lang. Program., 1985. To appear.
	12	D. Cheriton and R. E. Tarjan. Finding minimum spanning trees. SIAM J. Comput., 5:724--742, 1976.
	13	K. L. Clarkson, R. Cole, and R. E. Tarjan. Erratum: Randomized parallel algorithms for trapezoidal diagrams. Internat. J. Comput. Geom. Appl., 2(3):341--343, 1992.
	14	K. L. Clarkson, R. Cole, and R. E. Tarjan. Randomized parallel algorithms for trapezoidal diagrams. Internat. J. Comput. Geom. Appl., 2(2):117--133, 1992.
	15	K. L. Clarkson , P. W. Shor, Applications of random sampling in computational geometry, II, Discrete & Computational Geometry, v.4 n.5, p.387-421, 1989 [doi>10.1007/BF02187740]
	16	Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
	17	M. de Berg and O. Schwarzkopf. Cuttings and applications. Internat. J. Comput. Geom. Appl., 5:343--355, 1995.
	18	G. Di Battista, P. Eades, R. Tamassia, and I. G. Tollis. Graph Drawing. Prentice Hall, Upper Saddle River, NJ, 1999.
	19	H. Edelsbrunner, J. W. Jaromczyk, J. W. Penny, and G. Swiatek. Primal canoes: optimal arrangements of segments. In Proc. 3rd Canad. Conf. Comput. Geom., pages 224--227, Aug. 1991.
	20	D. Eppstein. Spanning trees and spanners. In J.-R. Sack and J. Urrutia, editors, Handbook of Computational Geometry, chapter 9, pages 425--461. Elsevier, 2000.
	21	David Eppstein, Setting Parameters by Example, SIAM Journal on Computing, v.32 n.3, p.643-653, 2003 [doi>10.1137/S0097539700370084]
	22	David Eppstein , Zvi Galil , Giuseppe F. Italiano , Thomas H. Spencer, Separator based sparsification I.: planarity testing and minimum spanning trees, Journal of Computer and System Sciences, v.52 n.1, p.3-27, Feb. 1996 [doi>10.1006/jcss.1996.0002]
	23	D. Eppstein and M. T. Goodrich. Studying (nonplanar) road networks through an algorithmic lens. Submitted, 2008.
	24	David Eppstein , Gary L. Miller , Shang-Hua Teng, A deterministic linear time algorithm for geometric separators and its applications, Proceedings of the ninth annual symposium on Computational geometry, p.99-108, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.161005]
	25	M. Erwig. The graph Voronoi diagram with applications. Networks, 36(3):156--163, 2000.
	26	J. W. Essam and M. E. Fisher. Some basic definitions in graph theory. Review of Modern Physics, 42(2):271--288, 1970.
	27	Michael L. Fredman , Robert Endre Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the ACM (JACM), v.34 n.3, p.596-615, July 1987 [doi>10.1145/28869.28874]
	28	Andrew V. Goldberg, Scaling algorithms for the shortest paths problem, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.222-231, January 25-27, 1993, Austin, Texas, United States
	29	Andrew V. Goldberg , Chris Harrelson, Computing the shortest path: A search meets graph theory, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	30	Michael T. Goodrich, Planar separators and parallel polygon triangulation, Journal of Computer and System Sciences, v.51 n.3, p.374-389, Dec. 1995 [doi>10.1006/jcss.1995.1076]
	31	M. T. Goodrich and R. Tamassia. Algorithm Design: Foundations, Analysis, and Internet Examples. John Wiley & Sons, New York, NY, 2002.
	32	R. L. Graham and F. F. Yao. Finding the convex hull of a simple polygon. J. Algorithms, 4:324--331, 1983.
	33	Sariel Har-Peled, Constructing Planar Cuttings in Theory and Practice, SIAM Journal on Computing, v.29 n.6, p.2016-2039, April 2000 [doi>10.1137/S0097539799350232]
	34	Monika R. Henzinger , Philip Klein , Satish Rao , Sairam Subramanian, Faster shortest-path algorithms for planar graphs, Journal of Computer and System Sciences, v.55 n.1, p.3-23, Aug. 1997 [doi>10.1006/jcss.1997.1493]
	35	Martin Holzer , Frank Schulz , Dorothea Wagner , Thomas Willhalm, Combining speed-up techniques for shortest-path computations, Journal of Experimental Algorithmics (JEA), 10, 2005 [doi>10.1145/1064546.1180616]
	36	David R. Karger , Philip N. Klein , Robert E. Tarjan, A randomized linear-time algorithm to find minimum spanning trees, Journal of the ACM (JACM), v.42 n.2, p.321-328, March 1995 [doi>10.1145/201019.201022]
	37	G. A. Klunder , H. N. Post, The shortest path problem on large-scale real-road networks, Networks, v.48 n.4, p.182-194, December 2006 [doi>10.1002/net.v48:4]
	38	D. T. Lee. On finding the convex hull of a simple polygon. Internat. J. Comput. Inform. Sci., 12:87--98, 1983.
	39	R. J. Lipton and R. E. Tarjan. A separator theorem for planar graphs. SIAM J. Appl. Math., 36:177--189, 1979.
	40	M. Mareš. Two linear time algorithms for MST on minor closed graph classes. Archivum Mathematicum (BRNO), 40(3):315--320, 2004.
	41	Kurt Mehlhorn, A faster approximation algorithm for the Steiner problem in graphs, Information Processing Letters, v.27 n.3, p.125-128, March 25, 1988 [doi>10.1016/0020-0190(88)90066-X]
	42	Ulrich Meyer, Single-source shortest-paths on arbitrary directed graphs in linear average-case time, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.797-806, January 07-09, 2001, Washington, D.C., United States
	43	Gary L Miller, Finding small simple cycle separators for 2-connected planar graphs, Journal of Computer and System Sciences, v.32 n.3, p.265-279, June 1986 [doi>10.1016/0022-0000(86)90030-9]
	44	Gary L. Miller , Shang-Hua Teng , William Thurston , Stephen A. Vavasis, Geometric Separators for Finite-Element Meshes, SIAM Journal on Scientific Computing, v.19 n.2, p.364-386, March 1998 [doi>10.1137/S1064827594262613]
	45	Gary L. Miller , Shang-Hua Teng , William Thurston , Stephen A. Vavasis, Separators for sphere-packings and nearest neighbor graphs, Journal of the ACM (JACM), v.44 n.1, p.1-29, Jan. 1997 [doi>10.1145/256292.256294]
	46	B. Mohar and C. Thomassen. Graphs on Surfaces. Johns Hopkins University Press, 2001.
	47	J. Pach. Towards a Theory of Geometric Graphs, volume 342 of Contemporary Mathematics. American Mathematical Society, 2004.
	48	Rajeev Raman, Recent results on the single-source shortest paths problem, ACM SIGACT News, v.28 n.2, p.81-87, June 1997 [doi>10.1145/261342.261352]
	49	P. Sanders and D. Schultes. Highway hierarchies hasten exact shortest path queries. In Proceedings 17th European Symposium on Algorithms (ESA), volume 3669 of Springer LNCS, pages 568--579. Springer, 2005.
	50	Robert Sedgewick , Jeffrey Scott Vitter, Shortest paths in Euclidean graphs, Algorithmica, v.1 n.1, p.31-48, Jan. 1986 [doi>10.1007/BF01840435]
	51	Daniel A. Spielman , Shang-Hua Teng, Disk packings and planar separators, Proceedings of the twelfth annual symposium on Computational geometry, p.349-358, May 24-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237218.237404]
	52	Mikkel Thorup, Undirected single-source shortest paths with positive integer weights in linear time, Journal of the ACM (JACM), v.46 n.3, p.362-394, May 1999 [doi>10.1145/316542.316548]
	53	W. T. Trotter. Planar Graphs, volume 9 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science. American Mathematical Society, 1993.
	54	F. Benjamin Zhan , Charles E. Noon, Shortest Path Algorithms: An Evaluation Using Real Road Networks, Transportation Science, v.32 n.1, p.65-73, January 1998 [doi>10.1287/trsc.32.1.65]