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

doi:10.12005/orms.2020.0169

运筹与管理 ›› 2020, Vol. 29 ›› Issue (7): 33-40.DOI: 10.12005/orms.2020.0169

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

徐弈¹, 陈莹²

1.西安理工大学经济与管理学院,陕西西安 710054;
2.西安交通大学管理学院,陕西西安 710049

收稿日期:2018-12-10 出版日期:2020-07-25
作者简介:徐弈(1989-),男,陕西省西安市人,讲师,博士,研究方向为:运筹与优化;陈莹(1989-),女,满族,辽宁省锦州市人,博士研究生,研究方向为:运筹与优化。
基金资助:
陕西省自然科学基础研究计划(青年人才项目)(2020JQ-654) ;西安理工大学校博士启动金(105-451119001)

The Minimax 2-point Sets Covering Problem and Improved Algorithm

XU Yi¹, CHEN Ying²

1. School of Economics and Management, Xi'an University of Technology, Xi'an710054, China;
2. School of Management, Xi'an Jiaotong University, Xi'an 710049, China

Received:2018-12-10 Online:2020-07-25

摘要/Abstract

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

关键词: 二中心问题, 最远点Voronoi图, 中心包, 选址问题

Abstract: 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.

Key words: 2-center problem, farthest point Voronoi diagram, center hull, facility location problem

中图分类号:

TB114.1

徐弈, 陈莹. 最小最大二点集覆盖问题分析及改进算法设计[J]. 运筹与管理, 2020, 29(7): 33-40.

XU Yi, CHEN Ying. The Minimax 2-point Sets Covering Problem and Improved Algorithm[J]. Operations Research and Management Science, 2020, 29(7): 33-40.

参考文献

[1] Drezner Z. The planar two-center and two-median problems[J]. Transportation Science, 1984, 18(4): 351-361.
[2] Katz M J, Sharir M. An expander-based approach to geometric optimization[J]. SIAM Journal on Computing, 1997, 26(5): 1384-1408.
[3] Hershberger J, Suri S. Finding tailored partitions[J]. Journal of Algorithms, 1991, 12(3): 431-463.
[4] Jaromczyk JW, Kowaluk M. An efficient algorithm for the euclidean two-center problem[C]. Proceedings of the 10th ACM Symposium on Computational Geometry, 1994: 303-311.
[5] Sharir M. A near-linear algorithm for the planar 2-center problem[J]. Discrete and Computational Geometry, 1997, 18(2): 125-134.
[6] Eppstein D. Faster construction of planar two-centers[C]. Proceedings of the 8th ACM Symposium on Discrete Algorithms, 1997: 131-138.
[7] Chan T M. More planar two-center algorithms[J]. Computational Geometry, 1999, 13(3): 189-198.
[8] Agarwal P K, Sharir M, Welzl E. The discrete 2-center problem[J]. Discrete and Computational Geometry, 1998, 20(3): 287-305.
[9] Poon C K, Zhu B. Streaming with minimum space: an algorithm for covering by two congruent balls[J]. Theoretical Computer Science, 2013: 72-82.
[10] Kim S S, Ahn H K. An improved data stream algorithm for clustering[J]. Computational Geometry, 2015, 48(9): 635-645.
[11] Huang P, Tsai Y T, Tang C Y. A fast algorithm for the alpha-connected two-center decision problem[J]. Information Processing Letters, 2003, 85(4): 205-210.
[12] Huang P, Tsai Y T, Tang C Y. A near-quadratic algorithm for the alpha-connected two-center problem[J]. Journal of Information Science and Engineering, 2006, 22: 1317-1324.
[13] Xu Y, Peng JG, Xu Y F, Zhu B H. The discrete and mixed minimax 2-center problem[J]. Theoretical Computer Science, 2019, 774: 95-102.
[14] Kavand P, Mohades A, Eskandari M. (n,1,1,$＼alpha$)-center problem[J]. Amirkabir International Journal of Science and Research, 2014, 46: 57-64.
[15] Shamos M I, Hoey D. Closest-point problems[C]. Proceedings of the 16th Annual Symposium on IEEE Foundations of Computer Science, 1975: 151-162.
[16] Berg D M, Kreveld V M, Overmars M. Computational geometry[M]. Springer, 2000: 1-17.
[17] Aurenhammer F, Klein R, Lee D T. Voronoi diagrams and delaunay triangulations[M]. World Scientific, 2013.
[18] Megiddo N. Linear-time algorithm for linear programming in $R^3$ and related problems[J]. SIAM Journal on Computing, 1983, 12(4): 759-776.
[19] Wang C A. Optimal algorithms for the intersection and the minimum distance problems between planar polygons[J]. IEEE Transactions on Computers, 1983, 32(12): 1203-1207.
[20] Segal M. Lower bounds for covering problems[J]. Journal of Mathematical Modelling and Algorithms, 2002, 1(1): 17-29.

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

The Minimax 2-point Sets Covering Problem and Improved Algorithm

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 3

编辑推荐

Metrics

[1]	吴晨晨, 王丽, 徐春明, 徐大川. 鲁棒动态设施选址问题的近似算法[J]. 运筹与管理, 2020, 29(5): 61-66.
[2]	何永梅, 宁爱兵, 彭大江, 尚春剑, 张惠珍. 无容量限制设施选址问题的降阶回溯算法[J]. 运筹与管理, 2018, 27(9): 17-21.
[3]	陆坚毅, 杨超, 揭婉晨. 考虑绕行特征的电动汽车快速充电站选址问题及自适应遗传算法[J]. 运筹与管理, 2017, 26(1): 8-17.