最小最大二点集覆盖问题分析及改进算法设计

The Minimax 2-point Sets Covering Problem and Improved Algorithm

本文考虑二中心问题的扩展问题-最小最大二点集覆盖问题。给定两个平面点集P1和P2,分别包含m和n个点,求两个圆分别覆盖P1和P2,并且要求两圆半径与两圆圆心距三者中的最大值最小。本文主要贡献在于分析半径变化过程中两个点集中心包之间最近距离的变化关系,其中中心包是点集所具有的一个特殊几何结构,所得到的结果改进了Huang等人之前给出的结果,并且通过该结果设计相应算法,所得到的算法复杂性是目前最好的。

For a variation of two center problem,we consider the minimax 2-point sets covering problem.This problem considers finding two disks covering two point sets respectively such that the maximum among the two radii and the distance between two centers is minimized.According to the relationship between a center hull and the farthest point Voronoi diagram,when the radius is increasing from 0,we propose the minimum distance between two center hulls.We improve the previous result and give an improved algorithm which is the best known algorithm so far.