Querying two boundary points for shortest paths in a polygonal domain

DOI10.1016/j.comgeo.2012.01.012zbMath1266.65033OpenAlexW2138769733MaRDI 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 domainDavenport-Schinzel sequenceshortest path query

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Related Items (2)

The geodesic diameter of polygonal domains ⋮ Unnamed Item

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

This page was built for publication: Querying two boundary points for shortest paths in a polygonal domain