Name
Abstract | ||
|---|---|---|
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(vertical bar S-P vertical bar) time using O (n) space, where S-P is the set of the feasible floorplans of R with respect to P, while the known algorithms need either O (n vertical bar S-P vertical bar) time and O (n) space or O (log n vertical bar S-P vertical bar) time and O (n(3)) space. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1587/transfun.E101.A.1392 | IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES |
Keywords | Field | DocType |
enumeration, floorplan, algorithm | Algebra,Theoretical computer science,Mathematics | Journal |
Volume | Issue | ISSN |
E101A | 9 | 0916-8508 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Katsuhisa Yamanaka | 1 | 60 | 15.73 |
| Md. Saidur Rahman | 2 | 342 | 41.83 |
| Shin-ichi Nakano | 3 | 246 | 24.40 |