 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Packing anchored rectangles |
scientific article; zbMATH DE number 7053280
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Packing anchored rectangles |
scientific article; zbMATH DE number 7053280 |
Statements
Packing anchored rectangles (English)
0 references
3 May 2016
0 references
10 May 2019
0 references
Consider a finite set \(S\) of points in the unit square \([0,1]^2\), one of which is the origin \((0,0)\). Further consider packings of axis-aligned rectangles with a point from \(S\) in the lower left corner and with no points from \(S\) in the interior. The problem is now to maximize the total area of these rectangles. It is conjectured that, for any finite set \(S\), one can always find such a packing that covers an area of at least \(1/2\). In the current paper, two algorithms for solving this packing problem are considered, and it is proved that an area of 0.09121 can always be obtained. Earlier, not even a positive lower bound was known.
0 references
greedy algorithm
0 references
packing
0 references
rectangle
0 references
math.CO
0 references
cs.CG
0 references
0 references
0 references
0.930400252342224
0 references
0.8805227279663086
0 references
0.8755192756652832
0 references
