A faster algorithm for the constrained minimum covering circle problem to expedite solving p‐center problems in an irregularly shaped area with holes
针对连续p-中心问题，通过利用子问题凸性和优化搜索过程，改进了Voronoi启发式方法中约束最小覆盖圆的计算，在真实规模测试中比文献基准快400倍。
Abstract This paper introduces several means to expedite a known Voronoi heuristic method for solving a continuous p ‐center location problem, which is to cover a polygon with p circles such that no circle's center lies outside the polygon, no circle's center drops inside a polygonal hole, and the radius of the largest circle is as small as possible. A key step in the Voronoi heuristic is the repeated task of determining the constrained minimum covering circle (CMCC), but the best‐known method for this task is brute‐force and inefficient. This paper develops an improved method by exploiting the convexity of a related subproblem and employing an optimized search procedure. The algorithmic enhancements help to drastically reduce the effort required for finding the CMCC, and in turn, significantly expedite the solution of the p ‐center problem. On a realistic‐scale test case, the proposed algorithm ran 400× faster than the literature benchmark.