A Novel and Efficient Formulation and Solution Approach for the Region Coverage Problem with Identical Circles

References

• Addis B, Locatelli M, Schoen F (2008) Disk packing in a square: A new global optimization approach. INFORMS J. Comput. 20(4):516–524.Link, Google Scholar
• Averbakh I, Berman O, Kalcsics J, Krass D (2015) Structural properties of Voronoi diagrams in facility location problems with continuous demand. Oper. Res. 63(2):394–411.Link, Google Scholar
• Birgin EG, Gardenghi JL, Laurain A (2024) Bounds on the optimal radius when covering a set with minimum radius identical disks. Math. Oper. Res. 49(3):1855–1889.Link, Google Scholar
• Birgin EG, Laurain A, Massambone R, Santana AG (2021) A shape optimization approach to the problem of covering a two-dimensional region with minimum-radius identical balls. SIAM J. Sci. Comput. 43(3):A2047–A2078.Crossref, Google Scholar
• Birgin EG, Laurain A, Massambone R, Santana AG (2022) A shape-newton approach to the problem of covering with identical balls. SIAM J. Sci. Comput. 44(2):A798–A824.Crossref, Google Scholar
• Cafieri S, Hansen P, Messine F (2022) Global exact optimization for covering a rectangle with 6 circles. J. Global Optim. 83(1):163–185.Crossref, Google Scholar
• Doye JP, Leary RH, Locatelli M, Schoen F (2004) Global optimization of Morse clusters by potential energy transformations. INFORMS J. Comput. 16(4):371–379.Link, Google Scholar
• Drezner Z, Suzuki A (2010) Covering continuous demand in the plane. J. Oper. Res. Soc. 61(5):878–881.Crossref, Google Scholar
• Fiacco AV, McCormick GP (1964) Computational algorithm for the sequential unconstrained minimization technique for nonlinear programming. Management Sci. 10(4):601–617.Link, Google Scholar
• Fortune S (1987) A sweepline algorithm for Voronoi diagrams. Algorithmica 2:153–174.Crossref, Google Scholar
• Galiev SI, Karpova M (2010) Optimization of multiple covering of a bounded set with circles. Comput. Math. Math. Phys. 50:721–732.Crossref, Google Scholar
• Hager WW, Zhang H (2013) The limited memory conjugate gradient method. SIAM J. Optim. 23(4):2150–2168.Crossref, Google Scholar
• Heppes A, Melissen H (1997) Covering a rectangle with equal circles. Periodica Math. Hungarica 34:65–81.Crossref, Google Scholar
• Lai X, Hao JK, Yue D, Zhou Y (2025a) A heuristic algorithm with multi-scale perturbations for point arrangement and equal circle packing in a convex container. Comput. Oper. Res. 181:107099.Crossref, Google Scholar
• Lai X, Lin Z, Hao JK, Wu Q (2025b) An efficient optimization model and tabu search–based global optimization approach for the continuous p-dispersion problem. INFORMS J. Comput. 37(4):1018–1043.Link, Google Scholar
• Leary RH (2000) Global optimization on funneling landscapes. J. Global Optim. 18(4):367–383.Crossref, Google Scholar
• Liu YC (2022) A faster algorithm for the constrained minimum covering circle problem to expedite solving p‐center problems in an irregularly shaped area with holes. Naval Res. Logist. 69(3):431–441.Crossref, Google Scholar
• Liu DC, Nocedal J (1989) On the limited memory BFGS method for large scale optimization. Math. Programming 45(1–3):503–528.Crossref, Google Scholar
• Lourenço HR, Martin OC, Stützle T (2010) Iterated local search: Framework and applications. Gendreau M, Potvin JY, eds. Handbook of Metaheuristics, Volume 146 of International Series in Operations Research and Management Science, Chapter 12, 2nd ed. (Springer-Verlag, Berlin, Heidelberg, New York), 363–397.Crossref, Google Scholar
• Melissen JBM, Schuur PC (1996) Improved coverings of a square with six and eight equal circles. Electronic J. Comb. 3(1):R32.Crossref, Google Scholar
• Melissen JBM, Schuur PC (2000) Covering a rectangle with six and seven circles. Discrete Appl. Math. (1979). 99(1–3):149–156.Crossref, Google Scholar
• Neville EH (1915) On the solution of numerical functional equations: Illustrated by an account of a popular puzzle and of its solution. Proc. London Math. Soc. 2(1):308–326.Crossref, Google Scholar
• Nurmela KJ (2000) Conjecturally optimal coverings of an equilateral triangle with up to 36 equal circles. Experiment. Math. 9(2):241–250.Crossref, Google Scholar
• Nurmela KJ, Östergård PRJ (2000) Covering a square with up to 30 equal circles. Technical report, Helsinki University of Technology.Google Scholar
• Plastria F (2002) Continuous covering location problems. Drezner Z, Hamacher H, eds. Facility Location: Applications and Theory, vol. 1 (Springer, Berlin, Germany), 37–79.Crossref, Google Scholar
• Stoyan YG, Patsuk VM (2010) Covering a compact polygonal set by identical circles. Comput. Optim. Appl. 46(1):75–92.Crossref, Google Scholar
• Suzuki A, Drezner Z (1996) The p-center location problem in an area. Location Sci. 4(1–2):69–82.Crossref, Google Scholar
• Suzuki A, Drezner Z (2009) The minimum equitable radius location problem with continuous demand. Eur. J. Oper. Res. 195(1):17–30.Crossref, Google Scholar
• Tarnai T, Gáspár Z (1995) Covering a square by equal circles. Elemente Der Mathematik. 50(4):167–170.Google Scholar
• Wang B (2011) Coverage problems in sensor networks: A survey. ACM Comput. Surveys (CSUR). 43(4):1–53.Crossref, Google Scholar
• Wei H, Murray AT, Xiao N (2006) Solving the continuous space p-centre problem: Planning application issues. IMA J. Management Math. 17(4):413–425.Crossref, Google Scholar
• Wu Q, Li M, Lai X, Hao JK, Qiu Y (2026) A novel and efficient formulation and solution approach for the region coverage problem with identical circles. https://github.com/INFORMSJoC/2025.1649.Google Scholar