OPTIMUM PARTITIONING OF RECTILINEAR LAYOUTS

Authors
NGUYEN VH
Citation
Vh. Nguyen, OPTIMUM PARTITIONING OF RECTILINEAR LAYOUTS, IEE proceedings. Computers and digital techniques, 143(6), 1996, pp. 440-442
Citations number
9
Categorie Soggetti
Computer Sciences","Computer Science Hardware & Architecture","Computer Science Theory & Methods
Journal title
IEE proceedings. Computers and digital techniques → ACNP
ISSN journal
13502387
Volume
143
Issue
6
Year of publication
1996
Pages
440 - 442
Database
ISI
SICI code
1350-2387(1996)143:6<440:OPORL>2.0.ZU;2-A
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 'fre e space partition'. A simple proof of a formula on the number of recta ngles in a minimum free space partition is presented. Based on this fo rmula, it is shown that a minimum free space partition can be computed using a well known geometric graph search algorithm in O(n(3/2) log n ) time.