Link distance and shortest path problems in the plane (Q634253)

Voronoi diagrams are a central topic in computational geometry, with numerous applications in natural sciences, economics, computer science, and mathematics. Let \(M\) be a set, and let \(s_i\), \(1\leq i\leq N\), be subsets of \(M\) called sites. For each \(i\), let \(d_i\) be a real-valued function denoting the ``distance'' of a point \(z\in M\) from site \(s_i\). A Voronoi diagram consists of subsets of \(M\) that have the same nearest site(s) among the \(s_i\). This paper contains a collection of new results on variants of Voronoi diagrams, and on the computation of nontrivial distances their definitions might be based on. These results share the geometric setting. Namely, the set \(M\subset\mathbb{R}^2\) is either a closed interior domain \(P\) of a simple polygon of \(k\) edges (a floor plan of an art gallery), or a set \(D\) that results by removing from \(\mathbb{R}^2\) finitely many open polygonal domains of \(k\) edges in total (the plane cluttered with obstacles). First, the link distance is studied. It assigns to two points the minimum number of edges of a connecting polygonal path in \(M\). For a line segment \(s_i\), \(d_i(z)\) denotes the minimum link distance between point \(z\) and any point on \(s_i\). Inside a simple polygon \(P\), Voronoi diagrams can efficiently be constructed. In order to compute the link distance, shortest path maps can be applied. They also help in computing the (link-based) Hausdorff distance between sets of line segments, and the Fréchet distance between polygonal chains. In the second part of the paper, distance problems based on the Euclidean metric (instead of the link distance) are studied. The interested reader is referred to Tables 1 and 2 that list the results presented in this paper.