Computing external farthest neighbors for a simple polygon

DOI10.1016/0166-218X(91)90063-3zbMath0772.68094OpenAlexW1977902399MaRDI QIDQ1175781

S. Rao Kosaraju, Pankaj K. Agarwal, Baruch Schieber, Boris Aronov, Subhash Suri, Alok Aggarwal

Publication date: 25 June 1992

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(91)90063-3

zbMATH Keywords

polygonfarthest neighborsexternal diameter

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items

Efficient piecewise-linear function approximation using the uniform metric, Parallel methods for visibility and shortest-path problems in simple polygons, Guarding Exterior Region of a Simple Polygon

Cites Work

• Computing the geodesic center of a simple polygon
• Computing the external geodesic diameter of a simple polygon
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• Worst-case data structures for the priority queue with attrition
• Computing geodesic furthest neighbors in simple polygons
• Optimal shortest path queries in a simple polygon
• Euclidean shortest paths in the presence of rectilinear barriers
• Finding the convex hull of a simple polygon