The Visibility Center of a Simple Polygon

DOI10.4230/LIPICS.ESA.2021.65MaRDI QIDQ6075959zbMATH OpenOpenAlexFDO

Authors Anna Lubiw

Publication date 20 September 2023

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

zbMATH Keywords

facility locationshortest pathssimple polygonsvisibility

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Abstract: We introduce the emph{visibility center} of a set of points inside a polygon -- a point $c_V$ such that the maximum geodesic distance from $c_V$ to see any point in the set is minimized. For a simple polygon of $n$ vertices and a set of $m$ points inside it, we give an $O((n+m)log(n+m))$ time algorithm to find the visibility center. We find the visibility center of emph{all} points in a simple polygon in $O(nlogn)$ time. Our algorithm reduces the visibility center problem to the problem of finding the geodesic center of a set of half-polygons inside a polygon, which is of independent interest. We give an $O((n+k)log(n+k))$ time algorithm for this problem, where $k$ is the number of half-polygons.

Recommendations

• scientific article; zbMATH DE number 4051002
• Computing the geodesic center of a simple polygon
• scientific article; zbMATH DE number 6789192
• The geodesic edge center of a simple polygon
• The 2-center problem in a simple polygon

Cited in

(2)

• The geodesic edge center of a simple polygon
• Realizing metric spaces with convex obstacles

This page was built for publication: The Visibility Center of a Simple Polygon

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