Bottleneck partial-matching Voronoi diagrams and applications

详细信息    查看全文

• 作者：Matthias Henze¹ ; ^{matthias.henze@fu-berlin.de" class="auth_mail" title="E-mail the corresponding author} ; Rafel Jaume ; ² ; ^{jaume@inf.fu-berlin.de" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Bottleneck matching ; Voronoi-type diagram ; Partial point matching under translations ; Bipartite graph
• 刊名：Computational Geometry
• 出版年：2016
• 出版时间：January 2016
• 年：2016
• 卷：51
• 期：Complete
• 页码：40-54
• 全文大小：537 K

文摘

We study the minimization of the bottleneck distance between a point set B and an equally-sized subset of a point set A under translations. We relate this problem to a Voronoi-type diagram and derive polynomial bounds for its complexity that are optimal in the size of A. We devise efficient algorithms for the construction of such a diagram and its lexicographic variant, which generalize to higher dimensions. We use the diagram to find an optimal bottleneck matching under translations, to compute a connecting path of minimum bottleneck cost between two positions of B, and to determine the maximum bottleneck cost in a convex polygon.