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

作     者：徐弈 陈莹 XU Yi;CHEN Ying

作者机构：西安理工大学经济与管理学院陕西西安710054 西安交通大学管理学院陕西西安710049 

基　　金：陕西省自然科学基础研究计划(青年人才项目)(2020JQ-654) 西安理工大学校博士启动金(105-451119001) 

出 版 物：《运筹与管理》 (Operations Research and Management Science)

年 卷 期：2020年第29卷第7期

页      码：33-40页

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

主 题 词：二中心问题 最远点Voronoi图 中心包 选址问题 

学科分类：07[理学] 070104[070104] 0701[理学-数学类] 

核心收录：

D　O　I：10.12005/orms.2020.0169

馆 藏 号：203961019...