Rectilinear Link Diameter and Radius in a Rectilinear Polygonal Domain


We study the computation of the diameter and radius under the rectilinear link distance within a rectilinear polygonal domain of $n$ vertices and $h$ holes. We introduce a graph of oriented distances to encode the distance between pairs of points of the domain. This helps us transform the problem so that we can search through the candidates more efficiently. Our algorithm computes both the diameter and the radius in $O (\min(n^\omega, n^2 + nh \log h + \chi^2))$ time, where $\omega<2.373$ denotes the matrix multiplication exponent and $\chi\in \Omega(n)\cap O(n^2)$ is the number of edges of the graph of oriented distances. We also provide an alternative algorithm for computing the diameter that runs in $O(n^2 \log n)$ time.

In 34th European Workshop on Computational Geometry (EuroCG 2018) and 29th International Symposium on Algorithms and Computation (ISAAC 2018)