LIPIcs.SoCG.2020.75.pdf
- Filesize: 0.83 MB
- 4 pages
Document
Covering Rectangles by Disks: The Video (Media Exposition)
Authors
Sándor P. Fekete 
,
Phillip Keldenich ,
Christian Scheffer
-
Part of:
Volume:
36th International Symposium on Computational Geometry (SoCG 2020)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Computational Geometry (SoCG) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2020-06-08
File
Document Identifiers
Author Details
Acknowledgements
We thank Sebastian Morr, Utkarsh Gupta and Sahil Shah for joint related work.
Cite As Get BibTex
Sándor P. Fekete, Phillip Keldenich, and Christian Scheffer. Covering Rectangles by Disks: The Video (Media Exposition). In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 75:1-75:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.SoCG.2020.75
Abstract
In this video, we motivate and visualize a fundamental result for covering a rectangle by a set of non-uniform circles: 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…. We describe the structure of the proof, and show animations of some of the main components.
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)
0PDF Downloads
References
- Sándor P. Fekete, Utkarsh Gupta, Phillip Keldenich, Christian Scheffer, and Sahil Shah. Worst-Case Optimal Covering of Rectangles by Disks. In Proceedings 36th International Symposium on Computational Geometry (SoCG 2020), pages 42:1-42:19, 2020. URL: https://doi.org/10.4230/LIPIcs.SoCG.2019.35.