Jonathan Gadea Harder:
Anchored Rectangle Cover
Let S be a set of points located in the unit square [0, 1]^2, which contains (0, 0). An open conjecture states that for any S it is possible to cover half of the area by rectangles inside the unit square, with the conditions that the lower-left corner of each rectangle is a point in S and that the rectangles are non-overlapping and axes-parallel.
The focus of this thesis is to suggest an algorithm, which for any S determines what the maximum area is that can be covered by rectangles. This algorithm improves the running time of the currently best-known algorithm with running time poly(n)*n! to poly(n)*2^n by the use of dynamic programming. To analyze how this algorithm performs, lower bounds for different types of instances are proven, e.g. that the conjecture can be confirmed for n