Free Space Modeling for Placing Rectangles without Overlapping

Marc Bernard (Centre de Recherche en Informatique de Dijon, France)

François Jacquenet (Centre de Recherche en Informatique de Dijon, France)

Abstract: The placement of rectangular objects without overlapping on a bounded surface is a generic problem that may have many applications. Space planning, chipset placement, cutting-stock problems, point-feature label placement, or the placement of articles on a newspaper page, are all instances of this more abstract problem.
All these applications are concerned with the insertion of rectangular objects on a part of a bounded free surface. It is therefore important to be able to efficiently model the free space of the bounded surface.
In this article we present a method to compute free space. The method is based on an iterative insertion process. Our algorithm neither depends on the size of the object to insert, nor on the method of placement. The first feature improves efficiency, while the second allows us to compare different placement methods, and to parameterize the placement system using resolution heuristics.

Keywords: Placement, algorithms, free space

Categories: I.3, I.3.5, I.3.6, I.6