BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
We give an overview of the 2022 Computational Geometry Challenge targeting the problem Minimum Partition into Plane Subsets, which consists of partitioning a given set of line segments into a minimum number of non-crossing subsets.
We provide a tight result for a fundamental problem arising from packing squares into a circular container: The critical density of packing squares into a disk is δ=5π8≈0.509. This implies that any set of (not necessarily equal) squares of total area A≤58 can always be packed into a disk with radius 1; in contrast, for any ε>0 there are sets of squares of total area 58+ε that cannot be packed, even if squares may be rotated. This settles the last (and arguably, most elusive) case of packing circular or square objects into a circular or square container: The critical densities for squares in a square (21), circles in a square ((3+22)π≈0.539) and circles in a circle (21) have already been established, making use of recursive subdivisions of a square container into pieces bounded by straight lines, or the ability to use recursive arguments based on similarity of objects and container; neither of these approaches can be applied when packing squares into a circular container. Our proof uses a careful manual analysis, complemented by a computer-assisted part that is based on interval arithmetic. Beyond the basic mathematical importance, our result is also useful as a blackbox lemma for the analysis of recursive packing algorithms. At the same time, our approach showcases the power of a general framework for computer-assisted proofs, based on interval arithmetic.
We give an overview of the 2020 Computational Geometry Challenge, which targeted the problem of partitioning the convex hull of a given planar point set P into the smallest number of convex faces, such that no point of P is contained in the interior of a face.
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 λ2=7/2−1/4≈1.035797…, such that for λ<λ2 the critical covering area A∗(λ) is A∗(λ)=3π(16λ2+325+256λ29), and for λ≥λ2, the critical area is A∗(λ)=π(λ2+2)/4; these values are tight. For the special case λ=1, i.e., for covering a unit square, the critical covering area is 256195π≈2.39301…. The proof uses a careful combination of manual and automatic analysis, demonstrating the power of the employed interval arithmetic technique.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.