Querying two boundary points for shortest paths in a polygonal domain

DOI10.1016/j.comgeo.2012.01.012zbMath1266.65033MaRDI QIDQ419498

Yoshio Okamoto, Sang Won Bae

Publication date: 18 May 2012

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.comgeo.2012.01.012

zbMATH Keywords

polygonal domain; Davenport-Schinzel sequence; shortest path query

Mathematics Subject Classification ID

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

65D18: Numerical aspects of computer graphics, image analysis, and computational geometry

Related Items

Unnamed Item, The geodesic diameter of polygonal domains

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding the upper envelope of n line segments in O(n log n) time
• Almost tight upper bounds for lower envelopes in higher dimensions
• Optimal shortest path queries in a simple polygon
• Shortest Path Problems on a Polyhedral Surface
• Shortest Path Queries in Polygonal Domains
• Improved bounds and new techniques for Davenport--Schinzel sequences and their generalizations
• An Optimal Algorithm for Euclidean Shortest Paths in the Plane
• Star Unfolding of a Polytope with Applications
• Computing Envelopes in Four Dimensions with Applications
• Planar spanners and approximate shortest path queries among obstacles in the plane
• SHORTEST PATHS AMONG OBSTACLES IN THE PLANE