University of Twente Student Theses

Login

Greedy algorithms for anchored rectangle packings

Maat, M. T. (2020) Greedy algorithms for anchored rectangle packings.

This is the latest version of this item.

[img] 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:http://purl.utwente.nl/essays/82222
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page