Document Open Access Logo

Worst-Case Optimal Covering of Rectangles by Disks

Authors Sándor P. Fekete , Utkarsh Gupta , Phillip Keldenich , Christian Scheffer , Sahil Shah

PDF

File

Thumbnail PDF
PDF
LIPIcs.SoCG.2020.42.pdf
  • Filesize: 3.47 MB
  • 23 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Packing and covering problems
  • Theory of computation → Computational geometry
Keywords
  • Disk covering
  • critical density
  • covering coefficient
  • tight worst-case bound
  • interval arithmetic
  • approximation

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

We provide the solution for a fundamental problem of geometric optimization by giving a complete characterization of worst-case optimal disk coverings of rectangles: For any λ ≥ 1, the critical covering area A^*(λ) is the minimum value for which any set of disks with total area at least A^*(λ) can cover a rectangle of dimensions λ× 1. We show that there is a threshold value λ₂ = √{√7/2 - 1/4} ≈ 1.035797…, such that for λ < λ₂ the critical covering area A^*(λ) is A^*(λ) = 3π(λ²/16 + 5/32 + 9/(256λ²)), and for λ ≥ λ₂, the critical area is A^*(λ)=π(λ²+2)/4; these values are tight. For the special case λ=1, i.e., for covering a unit square, the critical covering area is 195π/256 ≈ 2.39301…. The proof uses a careful combination of manual and automatic analysis, demonstrating the power of the employed interval arithmetic technique.

Cite As Get BibTex

Sándor P. Fekete, Utkarsh Gupta, Phillip Keldenich, Christian Scheffer, and Sahil Shah. Worst-Case Optimal Covering of Rectangles by Disks. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 42:1-42:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.SoCG.2020.42

Author Details

Sándor P. Fekete
  • Department of Computer Science, TU Braunschweig, Germany
Utkarsh Gupta
  • Department of Computer Science & Engineering, IIT Bombay, India
Phillip Keldenich
  • Department of Computer Science, TU Braunschweig, Germany
Christian Scheffer
  • Department of Computer Science, TU Braunschweig, Germany
Sahil Shah
  • Department of Computer Science & Engineering, IIT Bombay, India

Acknowledgements

We thank Sebastian Morr and Arne Schmidt for helpful discussions. Major parts of the research by Utkarsh Gupta and Sahil Shah were carried out during a stay at TU Braunschweig.

Supplementary Materials

References

  1. A Karim Abu-Affash, Paz Carmi, Matthew J Katz, and Gila Morgenstern. Multi cover of a polygon minimizing the sum of areas. International Journal of Computational Geometry & Applications, 21(06):685-698, 2011. Google Scholar
  2. Alessandro Agnetis, Enrico Grande, Pitu B Mirchandani, and Andrea Pacifici. Covering a line segment with variable radius discs. Computers & Operations Research, 36(5):1423-1436, 2009. Google Scholar
  3. Helmut Alt, Esther M. Arkin, Hervé Brönnimann, Jeff Erickson, Sándor P. Fekete, Christian Knauer, Jonathan Lenchner, Joseph S. B. Mitchell, and Kim Whittlesey. Minimum-cost coverage of point sets by disks. In Proc. 22nd Annu. ACM Sympos. Comput. Geom., pages 449-458, 2006. URL: https://doi.org/10.1145/1137856.1137922.
  4. Balázs Bánhelyi, Endre Palatinus, and Balázs L Lévai. Optimal circle covering problems and their applications. Central European Journal of Operations Research, 23(4):815-832, 2015. Google Scholar
  5. Aaron T. Becker, Sándor P. Fekete, Phillip Keldenich, Sebastian Morr, and Christian Scheffer. Packing Geometric Objects with Optimal Worst-Case Density (Multimedia Exposition). In Proceedings 35th International Symposium on Computational Geometry (SoCG), pages 63:1-63:6, 2019. Video available at https://www.ibr.cs.tu-bs.de/users/fekete/Videos/PackingCirclesInSquares.mp4. URL: https://doi.org/10.4230/LIPIcs.SoCG.2019.63.
  6. K. Bezdek. Körök optimális fedései (Optimal covering of circles). PhD thesis, Eötvös Lorand University, 1979. Google Scholar
  7. KÄROLY Bezdek. Über einige optimale Konfigurationen von Kreisen. Ann. Univ. Sci. Budapest Rolando Eötvös Sect. Math, 27:143-151, 1984. Google Scholar
  8. Santanu Bhowmick, Kasturi R. Varadarajan, and Shi-Ke Xue. A constant-factor approximation for multi-covering with disks. JoCG, 6(1):220-234, 2015. URL: https://doi.org/10.20382/jocg.v6i1a9.
  9. Károly Böröczky Jr. Finite packing and covering, volume 154. Cambridge University Press, 2004. Google Scholar
  10. Peter Brass, William OJ Moser, and János Pach. Density problems for packings and coverings. Research Problems in Discrete Geometry, pages 5-74, 2005. Google Scholar
  11. Paz Carmi, Matthew J Katz, and Nissan Lev-Tov. Covering points by unit disks of fixed location. In Proc. International Symposium on Algorithms and Computation (ISAAC), pages 644-655. Springer, 2007. Google Scholar
  12. Cgal, Computational Geometry Algorithms Library. URL: http://www.cgal.org.
  13. Gautam K Das, Sandip Das, Subhas C Nandy, and Bhabani P Sinha. Efficient algorithm for placing a given number of base stations to cover a convex region. Journal of Parallel and Distributed Computing, 66(11):1353-1358, 2006. Google Scholar
  14. Gautam K Das, Sasanka Roy, Sandip Das, and Subhas C Nandy. Variations of base-station placement problem on the boundary of a convex region. International Journal of Foundations of Computer Science, 19(02):405-427, 2008. Google Scholar
  15. Erik D. Demaine, Sándor P. Fekete, and Robert J. Lang. Circle packing for origami design is hard. In Origami⁵: 5th International Conference on Origami in Science, Mathematics and Education, AK Peters/CRC Press, pages 609-626, 2011. URL: http://arxiv.org/abs/1105.0791.
  16. dpa. Rasensprenger zeichnet Kreise auf Fußballfeld, 2018. Google Scholar
  17. Gábor Fejes Tóth. Recent progress on packing and covering. Contemporary Mathematics, 223:145-162, 1999. Google Scholar
  18. Sándor P. Fekete, Utkarsh Gupta, Phillip Keldenich, Christian Scheffer, and Sahil Shah. Worst-case optimal covering of rectangles by disks. arXiv:2003.08236 [cs.CG], 2020. URL: http://arxiv.org/abs/2003.08236.
  19. Sándor P. Fekete, Phillip Keldenich, and Christian Scheffer. Packing Disks into Disks with Optimal Worst-Case Density. In Proceedings 35th International Symposium on Computational Geometry (SoCG 2019), pages 35:1-35:19, 2019. URL: https://doi.org/10.4230/LIPIcs.SoCG.2019.35.
  20. Sándor P. Fekete, Phillip Keldenich, and Christian Scheffer. Covering rectangles by disks: The video. In Proceedings of the 36th International Symposium on Computational Geometry (SoCG), 2020. To appear. Google Scholar
  21. Sándor P. Fekete, Sebastian Morr, and Christian Scheffer. Split packing: Algorithms for packing circles with optimal worst-case density. Discrete & Computational Geometry, 2018. URL: https://doi.org/10.1007/s00454-018-0020-2.
  22. F. Fodor. The densest packing of 19 congruent circles in a circle. Geometriae Dedicata, 74:139–145, 1999. Google Scholar
  23. F. Fodor. The densest packing of 12 congruent circles in a circle. Beiträge zur Algebra und Geometrie (Contributions to Algebra and Geometry), 41:401–409, 2000. Google Scholar
  24. F. Fodor. The densest packing of 13 congruent circles in a circle. Beiträge zur Algebra und Geometrie (Contributions to Algebra and Geometry), 44:431–440, 2003. Google Scholar
  25. E. Friedman. Circles covering squares web page, 2014. URL: http://www2.stetson.edu/~efriedma/circovsqu/.
  26. M. Goldberg. Packing of 14, 16, 17 and 20 circles in a circle. Mathematics Magazine, 44:134–139, 1971. Google Scholar
  27. R.L. Graham, B.D. Lubachevsky, K.J. Nurmela, and P.R.J. Östergøard. Dense packings of congruent circles in a circle. Discrete Mathematics, 181:139–154, 1998. Google Scholar
  28. Aladár Heppes and Hans Melissen. Covering a rectangle with equal circles. Periodica Mathematica Hungarica, 34(1-2):65-81, 1997. Google Scholar
  29. Chi-Fu Huang and Yu-Chee Tseng. A survey of solutions for the coverage problems in wireless sensor networks. Journal of Internet Technology, 6(1):1-8, 2005. Google Scholar
  30. Matthew P Johnson, Deniz Sariöz, Amotz Bar-Noy, Theodore Brown, Dinesh Verma, and Chai W Wu. More is more: the benefits of denser sensor deployment. ACM Transactions on Sensor Networks (TOSN), 8(3):22, 2012. Google Scholar
  31. B.D. Lubachevsky and R.L. Graham. Curved hexagonal packings of equal disks in a circle. Discrete & Computational Geometry, 18:179–194, 1997. Google Scholar
  32. H. Melissen. Densest packing of eleven congruent circles in a circle. Geometriae Dedicata, 50:15–25, 1994. Google Scholar
  33. Hans Melissen. Loosest circle coverings of an equilateral triangle. Mathematics Magazine, 70(2):118-124, 1997. Google Scholar
  34. Johannes Bernardus Marinus Melissen and Peter Cornelis Schuur. Covering a rectangle with six and seven circles. Discrete Applied Mathematics, 99(1-3):149-156, 2000. Google Scholar
  35. John W. Moon and Leo Moser. Some packing and covering theorems. In Colloquium Mathematicae, volume 17, pages 103-110. Institute of Mathematics, Polish Academy of Sciences, 1967. Google Scholar
  36. Sebastian Morr. Split packing: An algorithm for packing circles with optimal worst-case density. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 99-109, 2017. Google Scholar
  37. Eric H Neville. On the solution of numerical functional equations. Proceedings of the London Mathematical Society, 2(1):308-326, 1915. Google Scholar
  38. Kari J Nurmela. Conjecturally optimal coverings of an equilateral triangle with up to 36 equal circles. Experimental Mathematics, 9(2):241-250, 2000. Google Scholar
  39. Norman Oler. A finite packing problem. Canadian Mathematical Bulletin, 4:153–155, 1961. Google Scholar
  40. Endre Palatinus and Balázs Bánhelyi. Circle covering and its applications for telecommunication networks. In 8 th International Conference on Applied Informatics, page 255, 2010. Google Scholar
  41. G.E. Reis. Dense packing of equal circles within a circle. Mathematics Magazine, issue 48:33–37, 1975. Google Scholar
  42. Williamjeet Singh and Jyotsna Sengupta. An efficient algorithm for optimizing base station site selection to cover a convex square region in cell planning. Wireless personal communications, 72(2):823-841, 2013. Google Scholar
  43. Eckard Specht. Packomania, 2015. URL: http://www.packomania.com/.
  44. Balázs Szalkai. Optimal cover of a disk with three smaller congruent disks. Advances in Geometry, 16(4):465-476, 2016. Google Scholar
  45. Gábor Fejes Tóth. Thinnest covering of a circle by eight, nine, or ten congruent circles. Combinatorial and computational geometry, 52(361):59, 2005. Google Scholar
  46. Gábor Fejes Tóth. Packing and covering. In Handbook of Discrete and Computational Geometry, Third Edition, pages 27-66. Chapman and Hall/CRC, 2017. Google Scholar
  47. Xiaochun Xu, Sartaj Sahni, and Nageswara SV Rao. Minimum-cost sensor coverage of planar regions. In FUSION, pages 1-8, 2008. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact