DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2020.42

Worst-Case Optimal Covering of Rectangles by Disks

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

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

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

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)

Copy BibTex To Clipboard

@InProceedings{fekete_et_al:LIPIcs.SoCG.2020.42,
  author =	{Fekete, S\'{a}ndor P. and Gupta, Utkarsh and Keldenich, Phillip and Scheffer, Christian and Shah, Sahil},
  title =	{{Worst-Case Optimal Covering of Rectangles by Disks}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{42:1--42:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.42},
  URN =		{urn:nbn:de:0030-drops-122003},
  doi =		{10.4230/LIPIcs.SoCG.2020.42},
  annote =	{Keywords: Disk covering, critical density, covering coefficient, tight worst-case bound, interval arithmetic, approximation}
}

Search Results

Documents authored by Shah, Sahil

Worst-Case Optimal Covering of Rectangles by Disks

Abstract

Cite as

Thanks for your feedback!

Could not send message