Enumerating Floorplans with Columns

Katsuhisa YAMANAKA  Md. Saidur RAHMAN  Shin-ichi NAKANO  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E101-A   No.9   pp.1392-1397
Publication Date: 2018/09/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E101.A.1392
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
enumeration,  floorplan,  algorithm,  

Full Text: PDF(663.8KB)
>>Buy this Article

Given an axis-aligned rectangle R and a set P of n points in the proper inside of R we wish to partition R into a set S of n+1 rectangles so that each point in P is on the common boundary between two rectangles in S. We call such a partition of R a feasible floorplan of R with respect to P. Intuitively, P is the locations of columns and a feasible floorplan is a floorplan in which no column is in the proper inside of a room, i.e., columns are allowed to be placed only on the partition walls between rooms. In this paper we give an efficient algorithm to enumerate all feasible floorplans of R with respect to P. The algorithm is based on the reverse search method, and enumerates all feasible floorplans in O(|SP|) time using O(n) space, where SP is the set of the feasible floorplans of R with respect to P, while the known algorithms need either O(n|SP|) time and O(n) space or O(log n|SP|) time and O(n3) space.