Loading...
research article
On Optimum Partitioning of Rectilinear Layouts
Nguyen, Viet Hai
Given a set S of nonoverlapping axis-parallel rectangles placed inside a rectangular region B, a partition of the space B\S is called a ‘free space partition’. A simple proof of a formula on the number of rectangles in a minimum free space partition is presented. Based on this formula, it is shown that a minimum free space partition can be computed using a well known geometric graph search algorithm in O(n3/2 log n) time.
Type
research article
Authors
Nguyen, Viet Hai
Publication date
1996
Volume
143
Issue
6
Start page
440
End page
442
Subjects
Peer reviewed
REVIEWED
EPFL units
Available on Infoscience
January 16, 2007
Use this identifier to reference this record