2022/04/19 by Binay Bhattacharya, Bhattacharya, Binay, Amirhossein Mozafari +3
Business, Management and Accounting · Computer Science · Social Sciences · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Cross-Border Cooperation and Integration #FOS: Computer and information sciences #Facility Location and Emergency Management
paper · pdf · doi:10.48550/arxiv.2204.08754
openalex publication_date 2022/04/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a set P of n points in the plane, the k-center problem is to find k congruent disks of minimum possible radius such that their union covers all the points in P. The 2-center problem is a special case of the k-center problem that has been extensively studied in the recent past \citeCAHN,HT,SH. In this paper, we consider a generalized version of the 2-center problem called proximity connected 2-center (PCTC) problem. In this problem, we are also given a parameter δ≥ 0 and we have the additional constraint that the distance between the centers of the disks should be at most δ. Note that when δ=0, the PCTC problem is reduced to the 1-center(minimum enclosing disk) problem and when δ tends to infinity, it is reduced to the 2-center problem. The PCTC problem first appeared in the context of wireless networks in 1992 \citeACN0, but obtaining a nontrivial deterministic algorithm for the problem remained open. In this paper, we resolve this open problem by providing a deterministic O(n2log n) time algorithm for the problem.