Title :
Optimum partitioning of rectilinear layouts
Author_Institution :
Dept. Inf., Eidgenossische Tech. Hochschule, Zurich, Switzerland
fDate :
11/1/1996 12:00:00 AM
Abstract :
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
Keywords :
computational complexity; computational geometry; graph theory; search problems; computation time; formula proof; free space partition; geometric graph search algorithm; minimum free space partition; nonoverlapping axis-parallel rectangles; rectangular region; rectilinear layout optimum partitioning;
Journal_Title :
Computers and Digital Techniques, IEE Proceedings -
DOI :
10.1049/ip-cdt:19960640
