On the geodesic centers of polygonal domains

DOI10.4230/LIPICS.ESA.2016.77MaRDI QIDQ4606352zbMATHOpenAlexFDO

Authors Haitao Wang

Publication date 2 March 2018

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

zbMATH Keywords

shortest pathspolygonal domainsgeodesic centers

Mathematics Subject Classification ID

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

Abstract: In this paper, we study the problem of computing Euclidean geodesic centers of a polygonal domain $mathcalP$ with a total of $n$ vertices. We discover many interesting observations. We give a necessary condition for a point being a geodesic center. We show that there is at most one geodesic center among all points of $mathcalP$ that have topologically-equivalent shortest path maps. This implies that the total number of geodesic centers is bounded by the combinatorial size of the shortest path map equivalence decomposition of $mathcalP$, which is known to be $O(n^{10})$. One key observation is a $pi$-range property on shortest path lengths when points are moving. With these observations, we propose an algorithm that computes all geodesic centers in $O(n^{11}logn)$ time. Previously, an algorithm of $O(n^{12+epsilon})$ time was known for this problem, for any $epsilon>0$.

Recommendations

• scientific article; zbMATH DE number 7030514
• The geodesic diameter of polygonal domains
• Computing the geodesic centers of a polygonal domain
• scientific article; zbMATH DE number 6789192
• scientific article; zbMATH DE number 4051002

Cited in

(8)

• Convex hulls in polygonal domains
• The polygon burning problem
• scientific article; zbMATH DE number 5552462 (Why is no real title available?)
• scientific article; zbMATH DE number 7030514 (Why is no real title available?)
• The geodesic 2-center problem in a simple polygon
• Computing the geodesic centers of a polygonal domain
• Computing the \(L_1\) geodesic diameter and center of a polygonal domain
• Centroaffine duality for spatial polygons

This page was built for publication: On the geodesic centers of polygonal domains

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