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

DOI10.1006/jagm.1995.0797zbMath0866.68117OpenAlexW2084097355MaRDI QIDQ3128986

Michael T. Goodrich

Publication date: 27 April 1997

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

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)

Related Items (15)

Tight degree bounds for pseudo-triangulations of points ⋮ An algorithmic study of manufacturing paperclips and other folded structures. ⋮ Minimum weight pseudo-triangulations ⋮ FINDING AN OPTIMAL BRIDGE BETWEEN TWO POLYGONS ⋮ Rectangular partitions of a rectilinear polygon ⋮ Augmenting the edge connectivity of planar straight line graphs to three ⋮ A faster algorithm for computing motorcycle graphs ⋮ Relative convex hulls in semi-dynamic arrangements ⋮ Decomposing a simple polygon into pseudo-triangles and convex polygons ⋮ Dynamic Algorithms for Visibility Polygons in Simple Polygons ⋮ Decompositions, partitions, and coverings with convex polygons and pseudo-triangles ⋮ On the number of pseudo-triangulations of certain point sets ⋮ Pointed binary encompassing trees: simple and optimal ⋮ Highway hull revisited ⋮ Visibility polygons and visibility graphs among dynamic polygonal obstacles in the plane

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