The Minimax 2-point Sets Covering Problem and Improved Algorithm

doi:10.12005/orms.2020.0169

Operations Research and Management Science ›› 2020, Vol. 29 ›› Issue (7): 33-40.DOI: 10.12005/orms.2020.0169

• Theory Analysis and Methodology Study • Previous Articles Next Articles

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

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

徐弈¹, 陈莹²

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

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

Abstract

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

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

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

CLC Number:

TB114.1

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.

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

References

[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

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 2

Recommended Articles

Metrics

[1]	WU Chen-chen, WANG Li, XU Chun-ming, XU Da-chuan. Approximation Algorithm for the Robust Dynamic Facility Location Problem [J]. Operations Research and Management Science, 2020, 29(5): 61-66.
[2]	HE Yong-mei, NING Ai-bing, PENG Da-jiang, SHANG Chun-jian, ZHANG Hui-zhen. Reduction Backtracking Algorithm for Uncapacitated Facility Location Problem [J]. Operations Research and Management Science, 2018, 27(9): 17-21.