Bottleneck Partial-Matching Voronoi Diagrams
Matthias Henze, Rafel Jaume · 2014
Abstract. Given two point sets in the plane, we study the minimiza-tion of the (lexicographic) bottleneck distance between the smaller set and an equally sized subset of the larger set under translations. We re-late this problem to two Voronoi-type diagrams and derive polynomial bounds for their combinatorial complexity that are optimal in the size of the larger set. We devise efficient construction algorithms for these dia-grams which are used to solve the minimization problem and, moreover, can be used to solve other related problems. 1.