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

摘要

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