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

DOI10.1006/JAGM.1995.0797MaRDI QIDQ3128986zbMATH OpenOpenAlexFDO

Authors Michael T. Goodrich

Publication date 27 April 1997

Published in Journal of Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://semanticscholar.org/paper/52d1690ef4d137357455efb472a2c4aae6d00564

zbMATH Keywords

ray- shootingshortest-path queries

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• A Unified Approach to Dynamic Point Location, Ray shooting, and Shortest Paths in Planar Maps
• scientific article; zbMATH DE number 437528
• Towards an optimal method for dynamic planar point location
• scientific article; zbMATH DE number 176772

Cited in

(20)

• Highway hull revisited
• Tight degree bounds for pseudo-triangulations of points
• An algorithmic study of manufacturing paperclips and other folded structures.
• Visibility polygons and visibility graphs among dynamic polygonal obstacles in the plane
• Minimum weight pseudo-triangulations
• Decompositions, partitions, and coverings with convex polygons and pseudo-triangles
• On the number of pseudo-triangulations of certain point sets
• Rectangular partitions of a rectilinear polygon
• Optimal dynamic vertical ray shooting in rectilinear planar subdivisions
• scientific article; zbMATH DE number 437528 (Why is no real title available?)
• Relative convex hulls in semi-dynamic arrangements
• FINDING AN OPTIMAL BRIDGE BETWEEN TWO POLYGONS
• A Unified Approach to Dynamic Point Location, Ray shooting, and Shortest Paths in Planar Maps
• Improved dynamic geodesic nearest neighbor searching in a simple polygon
• Dynamic algorithms for visibility polygons in simple polygons
• Augmenting the edge connectivity of planar straight line graphs to three
• Dynamic maintenance of shortest path trees in simple polygons
• Nearest neighbor searching in a dynamic simple polygon
• Pointed binary encompassing trees: simple and optimal
• Decomposing a simple polygon into pseudo-triangles and convex polygons

This page was built for publication: Dynamic Ray Shooting and Shortest Paths in Planar Subdivisions via Balanced Geodesic Triangulations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3128986)