Abstract
Let P be a set of n points in the proper inside of an axis-aligned rectangle R, and each point in P is either h-type, v-type or f-type. We wish to partition R into a set S of \(n+1\) rectangles by n line segments so that each point in P is on the common boundary line segment between two rectangles in S, and also each h-type point in P is on a horizontal line segment and each v-type point in P is on a vertical line segment. (Each f-type point in P is on a line segment. f-type menas free type). Such a partition of R is called a feasible floorplan of R with respect to P. Each point in P corresponds to the location of a structurally necessary horizontal or vertical wall, or a column (pillar) to support upper part, and a feasible floorplan is a floorplan achieving suitable earthquake resistance. An algorithm to enumerate all feasible floorplans of R with respect to P is known when P consists of only f-type points.
In this paper when P consists of the three type points 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(|S_P|n)\) time using O(n) space, after \(O(n\log n)\) time preprocessing, where \(S_P\) is the set of the feasible floorplans of R with respect to P.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Ackerman, E., Barequet, G., Pinter, R.Y.: On the number of rectangulations. In: Proceedings of the SODA, pp. 729–738 (2004)
Ackerman, E., Barequet, G., Pinter, R.Y.: On the number of rectangulations of a planar point set. J. Comb. Theory Ser. A 113, 1072–1091 (2006)
Avis, D.: Generating rooted triangulations without repetitions. Algorithmica 16, 618–632 (1996)
Avis, D., Fukuda, K.: Reverse search for enumeration. Discrete Appl. Math. 65, 21–46 (1996)
Nakano, S.: Enumerating floorplans with n rooms. In: Eades, P., Takaoka, T. (eds.) ISAAC 2001. LNCS, vol. 2223, pp. 107–115. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-45678-3_10
Nakano, S.: Efficient generation of plane trees. Inf. Process. Lett. 84, 167–172 (2002)
Li, Z., Nakano, S.: Efficient generation of plane triangulations without repetitions. In: Orejas, F., Spirakis, P.G., van Leeuwen, J. (eds.) ICALP 2001. LNCS, vol. 2076, pp. 433–443. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-48224-5_36
Yamanaka, K., Rahman, M.S., Nakano, S.-I.: Floorplans with columns. In: Gao, X., Du, H., Han, M. (eds.) COCOA 2017. LNCS, vol. 10627, pp. 33–40. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-71150-8_3
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Yamanaka, K., Nakano, Si. (2020). Floorplans with Walls. In: Chen, J., Feng, Q., Xu, J. (eds) Theory and Applications of Models of Computation. TAMC 2020. Lecture Notes in Computer Science(), vol 12337. Springer, Cham. https://doi.org/10.1007/978-3-030-59267-7_5
Download citation
DOI: https://doi.org/10.1007/978-3-030-59267-7_5
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-59266-0
Online ISBN: 978-3-030-59267-7
eBook Packages: Computer ScienceComputer Science (R0)