The geodesic diameter of polygonal domains

DOI10.1007/s00454-013-9527-8zbMath1298.52013arXiv1001.0695OpenAlexW2569574600MaRDI QIDQ368771

Matias Korman, Yoshio Okamoto, Sang Won Bae

Publication date: 23 September 2013

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1001.0695

zbMATH Keywords

shortest pathconvex functionpolygonal domainexact algorithmgeodesic diameterlower envelope

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Geodesics in global differential geometry (53C22) Variational problems in applications to the theory of geodesics (problems in one independent variable) (58E10)

Related Items (10)

Rectilinear link diameter and radius in a rectilinear polygonal domain ⋮ Computing the geodesic centers of a polygonal domain ⋮ An optimal deterministic algorithm for geodesic farthest-point Voronoi diagrams in simple polygons ⋮ Maximal distortion of geodesic diameters in polygonal domains ⋮ Computing the \(L_1\) geodesic diameter and center of a polygonal domain ⋮ A linear-time algorithm for the geodesic center of a simple polygon ⋮ Computing a minimum-width cubic and hypercubic shell ⋮ Rectilinear link diameter and radius in a rectilinear polygonal domain ⋮ Unnamed Item ⋮ Computing the \(L_1\) geodesic diameter and center of a simple polygon in linear time

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Querying two boundary points for shortest paths in a polygonal domain
• Computing the geodesic center of a simple polygon
• The furthest-site geodesic Voronoi diagram
• Optimal shortest path queries in a simple polygon
• An isoperimetric problem for tetrahedra
• Shortest Path Problems on a Polyhedral Surface
• Shortest Path Queries in Polygonal Domains
• The Geodesic Diameter of Polygonal Domains
• An Optimal Algorithm for Euclidean Shortest Paths in the Plane
• Star Unfolding of a Polytope with Applications
• Matrix Searching with the Shortest-Path Metric
• The geodesic farthest-site Voronoi diagram in a polygonal domain with holes
• SHORTEST PATHS AMONG OBSTACLES IN THE PLANE

This page was built for publication: The geodesic diameter of polygonal domains