Worst-case optimal covering of rectangles by disks

DOI10.1007/S00454-023-00582-1MaRDI QIDQ6624196zbMATH OpenFDO

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

Publication date 25 October 2024

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/S00454-023-00582-1

zbMATH Keywords

approximationcovering coefficientcritical densitydisk coveringinterval arithmetictight worst-case bound

Mathematics Subject Classification ID

Combinatorial aspects of packing and covering (05B40) Packing and covering in (2) dimensions (aspects of discrete geometry) (52C15) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Worst-case optimal covering of rectangles by disks
• Covering rectangles by disks: the video (media exposition)
• Covering a rectangle with equal circles
• Optimal circle covering problems and their applications
• Unit disk cover problem in 2D

Cites work

• A constant-factor approximation for multi-covering with disks
• A Finite Packing Problem
• Conjecturally Optimal Coverings of an Equilateral Triangle with Up to 36 Equal Circles
• Covering a line segment with variable radius discs
• Covering a rectangle with equal circles
• Covering a rectangle with six and seven circles
• Covering Points by Unit Disks of Fixed Location
• Covering rectangles by disks: the video (media exposition)
• Curved hexagonal packings of equal disks in a circle
• Dense Packing of Equal Circles within a Circle
• Dense packings of congruent circles in a circle
• Densest packings of eleven congruent circles in a circle
• Efficient algorithm for placing a given number of base stations to cover a convex region
• scientific article; zbMATH DE number 3919213 (Why is no real title available?)
• scientific article; zbMATH DE number 1241839 (Why is no real title available?)
• scientific article; zbMATH DE number 2117213 (Why is no real title available?)
• Loosest Circle Coverings of an Equilateral Triangle
• Minimum-cost coverage of point sets by disks
• Multi cover of a polygon minimizing the sum of areas
• On the solution of numerical functional equations.
• Optimal circle covering problems and their applications
• Optimal cover of a disk with three smaller congruent disks
• Packing disks into disks with optimal worst-case density
• Packing Geometric Objects with Optimal Worst-Case Density (Multimedia Exposition)
• Packing of 14, 16, 17 and 20 Circles in a Circle
• Research Problems in Discrete Geometry
• Some packing and covering theorems
• Split packing: algorithms for packing circles with optimal worst-case density
• Split packing: an algorithm for packing circles with optimal worst-case density
• The densest packing of 12 congruent circles in a circle
• The densest packing of 13 congruent circles in a circle
• The densest packing of 19 congruent circles in a circle
• Thinnest covering of a circle by eight, nine, or ten congruent circles
• VARIATIONS OF BASE-STATION PLACEMENT PROBLEM ON THE BOUNDARY OF A CONVEX REGION
• Worst-case optimal covering of rectangles by disks

Cited in

(2)

• Worst-case optimal covering of rectangles by disks
• Covering rectangles by disks: the video (media exposition)

This page was built for publication: Worst-case optimal covering of rectangles by disks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6624196)