Bottleneck partial-matching Voronoi diagrams and applications (Q902422)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Bottleneck partial-matching Voronoi diagrams and applications |
scientific article |
Statements
Bottleneck partial-matching Voronoi diagrams and applications (English)
0 references
18 January 2016
0 references
The bottleneck distance between two sets \(A\) and \(B\) with \(|B| \leq |A|\) is defined as \[ \Delta(A,B) = \min_{\sigma: B \hookrightarrow A} \max_{b \in B} \| b - \sigma(b) \|, \] in which \(\| \cdot \|\) denotes the Euclidean norm and the minimum is taken over all injections from \(B\) into \(A\). The paper under review studies a dynamic version of the bottleneck distance; i.e., the authors consider all translations of \(B\), while fixing \(A\), and seek a translated copy \(B+t\) of \(B\) with minimum bottleneck distance to \(A\). Formally, they want to compute \[ \min_{t \in \mathbb{R}^d} \Delta(A,B+t), \] and call this problem bottleneck partial-matching under translations. The authors focus on algorithms whose complexity is sensitive to the size of the smaller set and introduce Voronoi-type diagrams, which they call bottleneck diagrams, as their main technical tool. The main results of the paper include efficient algorithms for the construction of such diagrams, as well as an application of these diagrams to find optimal bottleneck matchings under translations in arbitrary dimension \(d\).
0 references
bottleneck matching
0 references
Voronoi-type diagram
0 references
partial point matching under translations
0 references
bipartite graph
0 references
algorithm
0 references
0 references
0 references
0 references