Enumerating Floorplans with Columns
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E101-A No.9 pp.1392-1397
- Publication Date
- 2018/09/01
- Publicized
- 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)
- Category
Authors
Katsuhisa YAMANAKA
Iwate University
Md. Saidur RAHMAN
Bangladesh University of Engineering and Technology
Shin-ichi NAKANO
Gunma University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Katsuhisa YAMANAKA, Md. Saidur RAHMAN, Shin-ichi NAKANO, "Enumerating Floorplans with Columns" in IEICE TRANSACTIONS on Fundamentals,
vol. E101-A, no. 9, pp. 1392-1397, September 2018, doi: 10.1587/transfun.E101.A.1392.
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(|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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E101.A.1392/_p
Copy
@ARTICLE{e101-a_9_1392,
author={Katsuhisa YAMANAKA, Md. Saidur RAHMAN, Shin-ichi NAKANO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Enumerating Floorplans with Columns},
year={2018},
volume={E101-A},
number={9},
pages={1392-1397},
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(|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.},
keywords={},
doi={10.1587/transfun.E101.A.1392},
ISSN={1745-1337},
month={September},}
Copy
TY - JOUR
TI - Enumerating Floorplans with Columns
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1392
EP - 1397
AU - Katsuhisa YAMANAKA
AU - Md. Saidur RAHMAN
AU - Shin-ichi NAKANO
PY - 2018
DO - 10.1587/transfun.E101.A.1392
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E101-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 2018
AB - 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.
ER -
English
