Computing the \(L_1\) geodesic diameter and center of a simple polygon in linear time (Q2349742): Difference between revisions

\textit{S. Schuierer} [``Computing the \(L_1\) -diameter and center of a simple rectilinear polygon'', in: Proc. Int. Conf. on Computing and Information, ICCI'94, 214--229 (1994)] has shown how to compute the \(L_1\) geodesic diameter and radius of a simple rectilinear polygon in linear time. This paper is aimed to provide a clear and complete exposition on the diameter and radius of general simple polygons with respect to the \(L_1\) geodesic distance. It is first shown that any family of \(L_1\) geodesic balls has Helly number two, a property that does not hold for the Euclidean geodesic distance. The authors then show that the method of \textit{J. Hershberger} and \textit{S. Suri} [SIAM J. Comput. 26, No. 6, 1612--1634 (1997; Zbl 0885.68086)] for computing the Euclidean diameter extends to \(L_1\) metrics, and that the running time is preserved. It is further shown that the set of points realizing \(L_1\) geodesic centers coincides with the intersection of a finite number of geodesic balls.