Document Open Access Logo

Covering Rectangles by Disks: The Video (Media Exposition)

Authors Sándor P. Fekete , Phillip Keldenich , Christian Scheffer

PDF

File

Thumbnail PDF
PDF
LIPIcs.SoCG.2020.75.pdf
  • Filesize: 0.83 MB
  • 4 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

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.

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

Author Details

Sándor P. Fekete
  • Department of Computer Science, TU Braunschweig, Germany
Phillip Keldenich
  • Department of Computer Science, TU Braunschweig, Germany
Christian Scheffer
  • Department of Computer Science, TU Braunschweig, Germany

Acknowledgements

We thank Sebastian Morr, Utkarsh Gupta and Sahil Shah for joint related work.

Supplementary Materials

References

  1. 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.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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