Dynamic ray shooting and shortest paths via balanced geodesic triangulations

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Dynamic ray shooting and shortest paths via balanced geodesic triangulations

Full text

Pdf (906 KB)

Source

Annual Symposium on Computational Geometry archive
Proceedings of the ninth annual symposium on Computational geometry table of contents

San Diego, California, United States

Pages: 318 - 327

Year of Publication: 1993

ISBN:0-89791-582-8

Authors

Michael T. Goodrich	Johns Hopkins Univ., Baltimore, MD
Roberto Tamassia	Brown Univ., Providence, RI

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 28, Citation Count: 8

Additional Information:

references cited by index terms review collaborative colleagues

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

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/160985.161157 What is a DOI?

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 and M. Sharir, "Applications of a new partitioning scheme," Proc. 2nd Workshop Algorithms Data Struct., Lecture Notes in Computer Science, vol. 519, Springer-Verlag, 1991, 379-391.
	2	Bernard Chazelle , Herbert Edelsbrunner , Michelangelo Grigni , Leonidas Guibas , John Hershberger , Micha Sharir , Jack Snoeyink, Ray shooting in polygons using Geodesic triangulations, Proceedings of the 18th international colloquium on Automata, languages and programming, p.661-673, June 1991, Madrid, Spain
	3	B. Chazelle , L. J. Guibas, Visibility and intersection problems in plane geometry, Discrete & Computational Geometry, v.4 n.6, p.551-581, Sep. 1989 [doi>10.1007/BF02187747]
	4	Yi-Jen Chiang , Franco P. Preparata , Roberto Tamassia, A unified approach to dynamic point location, ray shooting, and shortest paths in planar maps, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.44-53, January 25-27, 1993, Austin, Texas, United States
	5	S.W. Cheng and R. Janardan, "New Results on Dynamic Planar Point Location," Technical Report TR 90-13, Dept. of Computer Science, Univ. of Minnesota, 1990. (Prelim. version' 31st FOGS, 96--105, 1990.)
	6	Siu Wing Cheng , Ravi Janardan, Space-efficient ray-shooting and intersection searching: algorithms, dynamization, and applications, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.7-16, January 28-30, 1991, San Francisco, California, United States
	7	Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
	8	David Eppstein , Giuseppe F. Italiano , Roberto Tamassia , Robert E. Tarjan , Jeffery Westbrook , Moti Yung, Maintenance of a minimum spanning forest in a dynamic planar graph, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.1-11, January 22-24, 1990, San Francisco, California, United States
	9	O. Fries , K. Mehlhorn , St. Näher, Dynamization of geometric data structures, Proceedings of the first annual symposium on Computational geometry, p.168-176, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323256]
	10	M. Goodrich , M. Ghouse , J. Bright, Generalized sweep methods for parallel computational geometry, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.280-289, July 02-06, 1990, Island of Crete, Greece [doi>10.1145/97444.97695]
	11	Michael T. Goodrich , Roberto Tamassia, Dynamic trees and dynamic point location, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.523-533, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103472]
	12	L. J. Guibas , J. Hershberger, Optimal shortest path queries in a simple polygon, Journal of Computer and System Sciences, v.39 n.2, p.126-152, Oct. 1989 [doi>10.1016/0022-0000(89)90041-X]
	13	L Guibas , J Hershberger , D Leven , M Sharir , R Tarjan, Linear time algorithms for visibility and shortest path problems inside simple polygons, Proceedings of the second annual symposium on Computational geometry, p.1-13, June 02-04, 1986, Yorktown Heights, New York, United States [doi>10.1145/10515.10516]
	14	L.J. Guibas and R. Sedgewick, "A Dichromatic Framework for Balanced Trees," Proc. 19th IEEE Syrup. on Foundations of Computer Science, 1978, 8-21.
	15	John Hershberger, Optimal parallel algorithms for triangulated simple polygons, Proceedings of the eighth annual symposium on Computational geometry, p.33-42, June 10-12, 1992, Berlin, Germany [doi>10.1145/142675.142687]
	16	John Hershberger , Subhash Suri, A pedestrian approach to ray shooting: shoot a ray, take a walk, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.54-63, January 25-27, 1993, Austin, Texas, United States
	17	J.D. Lawrence, A Catalog of Special Plane Curves, Dover Publications, Inc. (New York: 1972).
	18	D.T. Lee and F.P. Preparata, "Euclidean shortest paths in the presence of rectilinear barriers," Networks, 14, 1984, 393-410.
	19	E.M. McCreight, "Priority Search Trees," SIAM J. on Comput., No. 14, 1985, 257- 276.
	20	K. Mehlhorn, Data Structures and Algorithms 1: Sorting and Searching, Springer- Verlag, 1984.
	21	Mark H. Overmars, Design of Dynamic Data Structures, Springer-Verlag New York, Inc., Secaucus, NJ, 1987
	22	Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
	23	Daniel D. Sleator , Robert Endre Tarjan, A data structure for dynamic trees, Journal of Computer and System Sciences, v.26 n.3, p.362-391, June 1983 [doi>10.1016/0022-0000(83)90006-5]
	24	D.D. Sleator, R.E. Tarjan, and W. P. Thurston, "Rotation distance, triangulations, and hyperbolic geometry," J. Arner. Math. Soc., 1, 1988, 647-682.
	25	Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983
	26	Dan E. Willard , George S. Lueker, Adding range restriction capability to dynamic data structures, Journal of the ACM (JACM), v.32 n.3, p.597-617, July 1985 [doi>10.1145/3828.3839]

CITED BY 8

	Danny Z. Chen , Kevin S. Klenk , Hung-Yi T. Tu, Shortest path queries among weighted obstacles in the rectilinear plane, Proceedings of the eleventh annual symposium on Computational geometry, p.370-379, June 05-07, 1995, Vancouver, British Columbia, Canada
	Gill Barequet , Michael T. Goodrich , D. Z. Chen , O. Daescu , J. Snoeyink, Efficiently approximating polygonal paths in three and higher dimensions, Proceedings of the fourteenth annual symposium on Computational geometry, p.317-326, June 07-10, 1998, Minneapolis, Minnesota, United States
	Danny Z. Chen, On the all-pairs Euclidean short path problem, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.292-301, January 22-24, 1995, San Francisco, California, United States
	G. D. Ramkumar, An algorithm to compute the Minkowski sum outer-face of two simple polygons, Proceedings of the twelfth annual symposium on Computational geometry, p.234-241, May 24-26, 1996, Philadelphia, Pennsylvania, United States
	Bernard Chazelle, Computational geometry: a retrospective, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.75-94, May 23-25, 1994, Montreal, Quebec, Canada
	Mikhail J. Atallah , Michael T. Goodrich , Kumar Ramaiyer, Biased finger trees and three-dimensional layers of maxima: (preliminary version), Proceedings of the tenth annual symposium on Computational geometry, p.150-159, June 06-08, 1994, Stony Brook, New York, United States
	Michael T. Goodrich, Efficient piecewise-linear function approximation using the uniform metric: (preliminary version), Proceedings of the tenth annual symposium on Computational geometry, p.322-331, June 06-08, 1994, Stony Brook, New York, United States
	C. T. Silva , J. S. B. Mitchell , A. E. Kaufman, Automatic generation of triangular irregular networks using greedy cuts, Proceedings of the 6th conference on Visualization '95, p.201, October 29-November 03, 1995

INDEX TERMS

Primary Classification:
F. Theory of Computation
F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
F.2.2 Nonnumerical Algorithms and Problems
Subjects: Geometrical problems and computations

Additional Classification:
E. Data
E.1 DATA STRUCTURES
Subjects: Trees

G. Mathematics of Computing
G.2 DISCRETE MATHEMATICS
G.2.2 Graph Theory
Subjects: Path and circuit problems

General Terms:
Algorithms, Verification

REVIEW

"Jerzy W. Jaromczyk : Reviewer"

Connected, planar subdivisions generated by a straight-line embedding into the plane of a planar graph play an important role in computational geometry due to their numerous applications. Each bounded face of a planar subdivision more...

Collaborative Colleagues:

Michael T. Goodrich: colleagues

Roberto Tamassia: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player