Transforming rectangles into squares
Jonathan Klawitter · 2014
In this bachelor thesis we introduce the Squarability problem: When can a set of axisaligned rectangles be transformed into squares without changing combinatorial properties? This means, that we do not allow to change whether, how and in which order the rectangles respectively squares intersect. We use a sweep line algorithm to compute the combinatorial information from geometrically given rectangles. We give a full characterisation of triangle-free rectangle arrangements via enhanced intersection graphs. We define a mixed integer linear program to solve any instance of the Squarability problem. We give some exemplary instances, which indicate that the problem is in general not that easy to solve. However, we show that some classes of rectangle arrangements can always be transformed into squares in the desired way.