Article

Free access

Dynamic ray shooting and shortest paths via balanced geodesic triangulations

Authors:

Michael T. Goodrich,

Roberto TamassiaAuthors Info & Claims

SCG '93: Proceedings of the ninth annual symposium on Computational geometry

Pages 318 - 327

https://doi.org/10.1145/160985.161157

Published: 01 July 1993 Publication History

PDF eReader

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.

Google Scholar

[2]

B. Chazelle, H. Edelsbrunner, M. Grigni, L. Guibas, J. Hershberger, M. Sharir, and J. Snoeyink, "Ray shooting in polygons using geodesic triangulations," Proc. Int. Coll. on Automata, Languages, and Programming (iCALP): LNC$ 510, 1991, 661-673.

Digital Library

Google Scholar

[3]

B. Chazelle and L.J. Guibas, "Visibility and Intersection Problems in Plane Geometry,'' Discrete Comput. Geom., 4, 1989, 551-581.

Digital Library

Google Scholar

[4]

Y.-J. Chiang, Y.-J., F.P. Preparata, and R. Tamassia, "A Unified Approach to Dynamic Point Location, Ray Shooting, and Shortest Paths in Planar Maps," Proc. jth A CM-$IAM Syrup. on Discrete .Algorithms, 1993, 44-53.

Digital Library

Google Scholar

[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.)

Digital Library

Google Scholar

[6]

S.W. Cheng and R. Janardan, "Spaceemcient ray shooting and intersection searching: Mgorithms, dynamization and applications," Proc. 2rid A CM-SIAM Sympos. Discrete AIgorithms, 1991, 7-16.

Digital Library

Google Scholar

[7]

T.H. Cormen, C.E. Leiserson, and R.L. Rivest, h~tvoduction to Algorithms, MIT Press (Cambridge, Mass.' 1990).

Digital Library

Google Scholar

[8]

Eppstein, D., G.F. Italiano, R. Tamassia, R.E. Tarjan, J. Westbrook, and M. Yung, "Maintenance of a Minixnmn Spanning Forest ill a Dynamic Planar Graph," Proc. First A CM-SIAM Symp. on Discrete Algorithms, 1-11, 1990.

Digital Library

Google Scholar

[9]

O. Fries, K. Mehlhorn, and S. Naeher, "Dynamization of Geometric Data Structures," Proc. (1st) A CM Syrup. on Computational Geometry, 168-176, 1985.

Digital Library

Google Scholar

[10]

M.T. Goodrich, M. Ghouse, and J. Bright, "Generalized Sweep Methods for Parallel Computational Geometry," Proc. 2nd A CM Syrup. on Parallel Algorithms and Architectures, 1990, 280-289.

Digital Library

Google Scholar

[11]

M.T. Goodrich and R. Tamassia, "Dynamic Trees and Dynamic Point Location," Proc. 23rd A CM Syrup. on Theory of Computing, 1991, 523-533.

Digital Library

Google Scholar

[12]

L.J. Guibas and J. Hershberger, "Optimal shortest path queries in a simple polygon," J. Comput. Syst. Sci., 39, 1989, 126-152.

Digital Library

Google Scholar

[13]

L.J. Guibas, J. Hershberger, D. Leven, M. Sharir, and R.E. Tarjan, "Linear Time Algorithms for Visibility and Shortest Path Problems Inside Simple Polygons," 2rid ACM Comp. Gcom., 1986, 1-13.

Digital Library

Google Scholar

[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.

Google Scholar

[15]

J. Hershberger, "Optimal Parallel Algorithms for Triangulated Simple Polygons," Proc. 8th A CM Syrup. on Computational Geometry, 1992, 33-42.

Digital Library

Google Scholar

[16]

J. Hershberger and S. Suri, "A Pedestrian Approach to Ray Shooting: Shoot a Ray, Take a Walk," Proc. Jth ACM-$IAM Syrup. on Discrete Algorithms, 1993.

Digital Library

Google Scholar

[17]

J.D. Lawrence, A Catalog of Special Plane Curves, Dover Publications, Inc. (New York: 1972).

Google Scholar

[18]

D.T. Lee and F.P. Preparata, "Euclidean shortest paths in the presence of rectilinear barriers," Networks, 14, 1984, 393-410.

Crossref

Google Scholar

[19]

E.M. McCreight, "Priority Search Trees," SIAM J. on Comput., No. 14, 1985, 257- 276.

Google Scholar

[20]

K. Mehlhorn, Data Structures and Algorithms 1: Sorting and Searching, Springer- Verlag, 1984.

Google Scholar

[21]

M. Overmars, The Design of Dynamic Data Structures, Lecture Notes in Computer Science, Springer-Verlag, 1983.

Digital Library

Google Scholar

[22]

F.P. Preparata and M.I. Shamos, Computational Geometry: An Introduction, Springer-Verlag, NY, 1985.

Digital Library

Google Scholar

[23]

D.D. Sleator and R.E. Tarjan, "A Data Structure for Dynamic Trees," J. Comput. and Sys. $ci., Vol. 26,362-391, 1983.

Digital Library

Google Scholar

[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.

Crossref

Google Scholar

[25]

R.E. Tarjan, Data Structures and Network Algorithms, SIAM, Philadelphia, PA, 1983.

Digital Library

Google Scholar

[26]

D. Willard and G. Lueker, "Adding Range Restriction Capability to Dynamic Data Structures," J. ACM, Vol. 32, 597-617, 1985.

Digital Library

Google Scholar

Cited By

View all

Eppstein DGoodrich MTrott LWolfson OAgrawal DLu C(2009)Going off-roadProceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems10.1145/1653771.1653778(23-32)Online publication date: 4-Nov-2009
https://dl.acm.org/doi/10.1145/1653771.1653778
Chiang YTamassia R(2006)Optimal shortest path and minimum-link path queries in the presence of obstaclesAlgorithms — ESA '9410.1007/BFb0049414(266-277)Online publication date: 23-Feb-2006
https://doi.org/10.1007/BFb0049414
Papadopoulou E(2005)k-pairs non-crossing shortest paths in a simple polygonAlgorithms and Computation10.1007/BFb0009507(305-314)Online publication date: 11-Oct-2005
https://doi.org/10.1007/BFb0009507
Show More Cited By

Index Terms

Dynamic ray shooting and shortest paths via balanced geodesic triangulations

Recommendations

Dynamic Ray Shooting and Shortest Paths in Planar Subdivisions via Balanced Geodesic Triangulations

We give new methods for maintaining a data structure that supports ray-shooting and shortest-path queries in a dynamically changing connected planar subdivision S. Our approach is based on a new dynamic method for maintaining a balanced decomposition of ...
Fast methods for computing all-to-all geodesic paths for the eikonal equation
A Unified Approach to Dynamic Point Location, Ray Shooting, and Shortest Paths in Planar Maps

We describe a new technique for dynamically maintaining the trapezoidal decomposition of a connected planar map $\cal M$ with $n$ vertices and apply it to the development of a unified dynamic data structure that supports point-location, ray-shooting, ...

Reviews

Reviewer: Jerzy W. Jaromczyk

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 S is a simple polygon. The paper presents a data structure that supports ray shooting and shortest paths queries with respect to S . This data structure allows for dynamic changes of S , that is, edges and vertices can be deleted or inserted into S . The basic ingredient of the solution, using O n space and O log n time for updates and queries (where n is the size of S ), is a tree T that is the dual of the geodesic triangulation of the faces of S . This triangulation uses geodesic paths (shortest paths between vertices) and is topologically and combinatorially like a standard triangulation of a polygon. The tree T can be maintained as a binary search tree (red-black tree) with simple tree operations (rotation, split, and splice) corresponding to dynamic changes in the underlying planar subdivision. This data structure outperforms the previous solutions by a factor of log n in space, and in update/query time requirements. The proceedings contains a preliminary version of the paper, and some proofs are omitted. A clear presentation guides the reader through the paper, however, despite the shortcuts implied by the space limitations. Also, a sequence of eight carefully prepared figures provides an excellent illustration of the essential elements of the construction and the algorithms.

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

SCG '93: Proceedings of the ninth annual symposium on Computational geometry

July 1993

406 pages

ISBN:0897915828

DOI:10.1145/160985

Chairman:
Chee Yap

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 1993

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

9SCG93

Sponsor:

9SCG93: Ninth Symposium on Computational Geometry

May 18 - 21, 1993

California, San Diego, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
406
Total Downloads

Downloads (Last 12 months)23
Downloads (Last 6 weeks)7

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Eppstein DGoodrich MTrott LWolfson OAgrawal DLu C(2009)Going off-roadProceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems10.1145/1653771.1653778(23-32)Online publication date: 4-Nov-2009
https://dl.acm.org/doi/10.1145/1653771.1653778
Chiang YTamassia R(2006)Optimal shortest path and minimum-link path queries in the presence of obstaclesAlgorithms — ESA '9410.1007/BFb0049414(266-277)Online publication date: 23-Feb-2006
https://doi.org/10.1007/BFb0049414
Papadopoulou E(2005)k-pairs non-crossing shortest paths in a simple polygonAlgorithms and Computation10.1007/BFb0009507(305-314)Online publication date: 11-Oct-2005
https://doi.org/10.1007/BFb0009507
Arikati SChen DChew LDas GSmid MZaroliagis C(2005)Planar spanners and approximate shortest path queries among obstacles in the planeAlgorithms — ESA '9610.1007/3-540-61680-2_79(514-528)Online publication date: 6-Jun-2005
https://doi.org/10.1007/3-540-61680-2_79
Barequet GGoodrich MChen DDaescu OSnoeyink JJanardan R(1998)Efficiently approximating polygonal paths in three and higher dimensionsProceedings of the fourteenth annual symposium on Computational geometry10.1145/276884.276920(317-326)Online publication date: 7-Jun-1998
https://dl.acm.org/doi/10.1145/276884.276920
Ramkumar GWhitesides S(1996)An algorithm to compute the Minkowski sum outer-face of two simple polygonsProceedings of the twelfth annual symposium on Computational geometry10.1145/237218.237374(234-241)Online publication date: 1-May-1996
https://dl.acm.org/doi/10.1145/237218.237374
Silva CMitchell JKaufman A(1995)Automatic generation of triangular irregular networks using greedy cutsProceedings of the 6th conference on Visualization '9510.5555/832271.833873Online publication date: 29-Oct-1995
https://dl.acm.org/doi/10.5555/832271.833873
Chen DClarkson K(1995)On the all-pairs Euclidean short path problemProceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms10.5555/313651.313710(292-301)Online publication date: 22-Jan-1995
https://dl.acm.org/doi/10.5555/313651.313710
Chen DKlenk KTu HSnoeyink J(1995)Shortest path queries among weighted obstacles in the rectilinear planeProceedings of the eleventh annual symposium on Computational geometry10.1145/220279.220319(370-379)Online publication date: 1-Sep-1995
https://dl.acm.org/doi/10.1145/220279.220319
Silva CMitchell JKaufman A(1995)Automatic generation of triangular irregular networks using greedy cutsProceedings Visualization '9510.1109/VISUAL.1995.480813(201-208,)Online publication date: 1995
https://doi.org/10.1109/VISUAL.1995.480813
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

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

Cited By

Index Terms

Recommendations

Dynamic Ray Shooting and Shortest Paths in Planar Subdivisions via Balanced Geodesic Triangulations

Fast methods for computing all-to-all geodesic paths for the eikonal equation

A Unified Approach to Dynamic Point Location, Ray Shooting, and Shortest Paths in Planar Maps

Reviews

Access critical reviews of Computing literature here