Exploiting Air-Pressure to Map Floorplans on Point Sets
Stefan Felsner · Journal of Graph Algorithms and Applications · 2014
Abstract. We prove a conjecture of Ackerman, Barequet and Pinter. Every floorplan with n segments can be embedded on every set of n points in generic position. The construction makes use of area universal floorplans also known as area universal rectangular layouts. The notion of area used in our context depends on a non-uniform density function. We, there-fore, have to generalize the theory of area universal floorplans to this situation. For the proof we use the air-pressure approach of Izumi, Takahashi and Kajitani. The method is then used to prove a result about accommodating points in floorplans that is slightly more general than the original conjecture. We close with some remarks on the counting problem that motivated the conjecture of Ackerman et al.