University of Twente Student Theses
Greedy algorithms for anchored rectangle packings
Maat, M. T. (2020) Greedy algorithms for anchored rectangle packings.
This is the latest version of this item.
|
PDF
2MB |
| Abstract: | A lower-left anchored rectangle packing of a finite set of points S (including the origin) in the unit square is a set of axis-aligned rectangles in the unit square such that no two rectangles overlap, no points are in the interior of a rectangle and each rectangle has exactly one point of S as its lower left corner. A greedy algorithm to find such packings with large area was discovered before. It treats the points in a specific order. We derive principles for orderings for which this greedy algorithm yields a large area. We analyze the performance of a number of orderings empirically on a number of random point sets. Finally, we derive upper bounds for the worst case performance, and increase the best known lower bound on the worst case performance of an ordering to 0.9612. |
| Item Type: | Essay (Bachelor) |
| Faculty: | EEMCS: Electrical Engineering, Mathematics and Computer Science |
| Subject: | 31 mathematics |
| Programme: | Applied Mathematics BSc (56965) |
| Link to this item: | https://purl.utwente.nl/essays/82222 |
| Export this item as: | BibTeX EndNote HTML Citation Reference Manager |
Show download statistics for this publication
Show download statistics for this publicationRepository Staff Only: item control page