文章基本信息

标题：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