scientific article; zbMATH DE number 4051002

From MaRDI portal
Publication:3787491





[For the entire collection see Zbl 0636.00011.] The authors present a polynomial-time algorithm for finding the geodesic center of a simple polygon, which is defined to be a point in the polygon whose greatest internal distance to any other point in the polygon is a minimum. The distance between two points in a simple polygon is measured as the length of the shortest internal path between them. The key idea is the construction of a geodesic farthest-point Voronoi diagram for a simple polygon which consists of straight lines and hyperbolic curve segments. The geodesic center of a simple polygon is either the center of its geodesic diameter or a vertex of the Voronoi diagram. The algorithm runs in O(n 3 log log n) time, n being the number of vertices of the given polygon.




Cited in
(32)








This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3787491)