Link distance and shortest path problems in the plane (Q634253): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 09:19, 30 January 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Link distance and shortest path problems in the plane |
scientific article |
Statements
Link distance and shortest path problems in the plane (English)
0 references
2 August 2011
0 references
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.
0 references
shortest paths
0 references
link distance
0 references
simple polygon
0 references
polygonal domain
0 references
Voronoi diagrams
0 references
computational geometry
0 references
Hausdorff distance
0 references
Fréchet distance
0 references