Computing the L₁ Geodesic Diameter and Center of a Simple Polygon in Linear Time
pith:3FJSAUKY Add to your LaTeX paper
What is a Pith Number?\usepackage{pith}
\pithnumber{3FJSAUKY}
Prints a linked pith:3FJSAUKY badge after your title and writes the identifier into PDF metadata. Compiles on arXiv with no extra files. Learn more
read the original abstract
In this paper, we show that the $L_1$ geodesic diameter and center of a simple polygon can be computed in linear time. For the purpose, we focus on revealing basic geometric properties of the $L_1$ geodesic balls, that is, the metric balls with respect to the $L_1$ geodesic distance. More specifically, in this paper we show that any family of $L_1$ geodesic balls in any simple polygon has Helly number two, and the $L_1$ geodesic center consists of midpoints of shortest paths between diametral pairs. These properties are crucial for our linear-time algorithms, and do not hold for the Euclidean case.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.