首页    期刊浏览 2024年11月24日 星期日
登录注册

文章基本信息

  • 标题:Covering Rectangles by Disks: The Video (Media Exposition)
  • 本地全文:下载
  • 作者:S{'a}ndor P. Fekete ; Phillip Keldenich ; Christian Scheffer
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2020
  • 卷号:164
  • 页码:75:1-75:4
  • DOI:10.4230/LIPIcs.SoCG.2020.75
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要: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 λâ,, = â^S(â^S7/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.
  • 关键词:Disk covering; critical density; covering coefficient; tight worst-case bound; interval arithmetic; approximation
国家哲学社会科学文献中心版权所有