Bottleneck partial-matching Voronoi diagrams and applications (Q902422)

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\).