Enumerating Floorplans with Any Set of Columns
摘要
A floorplan is a partition of an axis-aligned rectangle into a set of smaller rectangles. Given an axis-aligned rectangle R and a set P of points in R we wish to partition R into a set S of rectangles so that each point in P is on the boundary of rectangles in S. We call such a partition of R a floorplan covering P. Intuitively P is the locations of columns and a floorplan covering P is a floorplan in which no column is in the proper inside of a room. If no two points in P have the same x-coordinate and no two points in P have the same y-coordinate, then one can generate all floorplans covering P in O(|P|) time for each. In this paper we design an algorithm to generate all floorplans covering P, when P is any set of points, which is more practical setting in architecture. The running time of the algorithm is O(|P|) time for each.