Document Open Access Logo

Efficient Generation of Rectangulations via Permutation Languages

Authors Arturo Merino , Torsten Mütze

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2021.54.pdf
  • Filesize: 1.19 MB
  • 18 pages

Document Identifiers

Author Details

Arturo Merino
  • TU Berlin, Germany
Torsten Mütze
  • University of Warwick, Coventry, United Kingdom
  • Charles University, Prague, Czech Republic

Funding

This work was supported by German Science Foundation grant 413902284.
  • Merino, Arturo: Supported by ANID Becas Chile 2019-72200522.
  • Mütze, Torsten: Supported by Czech Science Foundation grant GA 19-08554S.

Cite AsGet BibTex

Arturo Merino and Torsten Mütze. Efficient Generation of Rectangulations via Permutation Languages. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 54:1-54:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.SoCG.2021.54

Abstract

A generic rectangulation is a partition of a rectangle into finitely many interior-disjoint rectangles, such that no four rectangles meet in a point. In this work we present a versatile algorithmic framework for exhaustively generating a large variety of different classes of generic rectangulations. Our algorithms work under very mild assumptions, and apply to a large number of rectangulation classes known from the literature, such as generic rectangulations, diagonal rectangulations, 1-sided/area-universal, block-aligned rectangulations, and their guillotine variants. They also apply to classes of rectangulations that are characterized by avoiding certain patterns, and in this work we initiate a systematic investigation of pattern avoidance in rectangulations. Our generation algorithms are efficient, in some cases even loopless or constant amortized time, i.e., each new rectangulation is generated in constant time in the worst case or on average, respectively. Moreover, the Gray codes we obtain are cyclic, and sometimes provably optimal, in the sense that they correspond to a Hamilton cycle on the skeleton of an underlying polytope. These results are obtained by encoding rectangulations as permutations, and by applying our recently developed permutation language framework.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
  • Mathematics of computing → Discrete mathematics
Keywords
  • Exhaustive generation
  • Gray code
  • flip graph
  • polytope
  • generic rectangulation
  • diagonal rectangulation
  • cartogram
  • floorplan
  • permutation pattern

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. E. Ackerman, G. Barequet, and R. Y. Pinter. A bijection between permutations and floorplans, and its applications. Discrete Appl. Math., 154(12):1674-1684, 2006. URL: https://doi.org/10.1016/j.dam.2006.03.018.
  2. E. Ackerman, G. Barequet, and R. Y. Pinter. On the number of rectangulations of a planar point set. J. Combin. Theory Ser. A, 113(6):1072-1091, 2006. URL: https://doi.org/10.1016/j.jcta.2005.10.003.
  3. K. Amano, S. Nakano, and K. Yamanaka. On the number of rectangular drawings: Exact counting and lower and upper bounds, 2007. IPSJ SIG Technical Report 2007-AL-115 (5). Google Scholar
  4. A. Asinowski, G. Barequet, M. Bousquet-Mélou, T. Mansour, and R. Y. Pinter. Orders induced by segments in floorplans and (2-14-3, 3-41-2)-avoiding permutations. Electron. J. Combin., 20(2):Paper 35, 43, 2013. Google Scholar
  5. A. Asinowski and T. Mansour. Separable d-permutations and guillotine partitions. Ann. Comb., 14(1):17-43, 2010. URL: https://doi.org/10.1007/s00026-010-0043-8.
  6. D. Avis and K. Fukuda. Reverse search for enumeration. Discrete Appl. Math., 65(1-3):21-46, 1996. First International Colloquium on Graphs and Optimization (GOI), 1992 (Grimentz). URL: https://doi.org/10.1016/0166-218X(95)00026-N.
  7. J. R. Bitner, G. Ehrlich, and E. M. Reingold. Efficient generation of the binary reflected Gray code and its applications. Comm. ACM, 19(9):517-521, 1976. URL: https://doi.org/10.1145/360336.360343.
  8. J. Cardinal, V. Sacristán, and R. I. Silveira. A note on flips in diagonal rectangulations. Discrete Math. Theor. Comput. Sci., 20(2):Paper No. 14, 22, 2018. Google Scholar
  9. J. Conant and T. Michaels. On the number of tilings of a square by rectangles. Ann. Comb., 18(1):21-34, 2014. URL: https://doi.org/10.1007/s00026-013-0209-2.
  10. The Combinatorial Object Server: URL: http://www.combos.org/rect.
  11. G. Ehrlich. Loopless algorithms for generating permutations, combinations, and other combinatorial configurations. J. Assoc. Comput. Mach., 20:500-513, 1973. URL: https://doi.org/10.1145/321765.321781.
  12. D. Eppstein, E. Mumford, B. Speckmann, and K. Verbeek. Area-universal and constrained rectangular layouts. SIAM J. Comput., 41(3):537-564, 2012. URL: https://doi.org/10.1137/110834032.
  13. R. Fujimaki, Y. Inoue, and T. Takahashi. An asymptotic estimate of the numbers of rectangular drawings or floorplans. In 2009 IEEE International Symposium on Circuits and Systems (ISCAS), pages 856-859, 2009. URL: https://doi.org/10.1109/ISCAS.2009.5117891.
  14. E. Hartung, H. P. Hoang, T. Mütze, and A. Williams. Combinatorial generation via permutation languages. In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 1214-1225. SIAM, 2020. URL: https://doi.org/10.1137/1.9781611975994.74.
  15. E. Hartung, H. P. Hoang, T. Mütze, and A. Williams. Combinatorial generation via permutation languages. I. Fundamentals, 2020. To appear in Trans. Amer. Math. Soc.; preprint available at URL: https://arxiv.org/abs/1906.06069.
  16. B. D. He. A simple optimal binary representation of mosaic floorplans and Baxter permutations. Theoret. Comput. Sci., 532:40-50, 2014. URL: https://doi.org/10.1016/j.tcs.2013.05.007.
  17. H. P. Hoang and T. Mütze. Combinatorial generation via permutation languages. II. Lattice congruences, 2020. To appear in Israel J. Math.; preprint available at URL: https://arxiv.org/abs/1911.12078.
  18. X. Hong, G. Huang, Y. Cai, J. Gu, S. Dong, C.-K. Cheng, and J. Gu. Corner block list: An effective and efficient topological representation of non-slicing floorplan. In E. Sentovich, editor, Proceedings of the 2000 IEEE/ACM International Conference on Computer-Aided Design, 2000, San Jose, California, USA, November 5-9, 2000, pages 8-12. IEEE Computer Society, 2000. URL: https://doi.org/10.1109/ICCAD.2000.896442.
  19. Y. Inoue, T. Takahashi, and R. Fujimaki. Counting rectangular drawings or floorplans in polynomial time. IEICE Trans. Fundam. Electron. Commun. Comput. Sci., 92-A(4):1115-1120, 2009. URL: https://doi.org/10.1587/transfun.E92.A.1115.
  20. D. E. Knuth. The Art of Computer Programming. Vol. 4A. Combinatorial algorithms. Part 1. Addison-Wesley, Upper Saddle River, NJ, 2011. Google Scholar
  21. S. Law and N. Reading. The Hopf algebra of diagonal rectangulations. J. Combin. Theory Ser. A, 119(3):788-824, 2012. URL: https://doi.org/10.1016/j.jcta.2011.09.006.
  22. E. Meehan. The Hopf algebra of generic rectangulations, 2019. URL: http://arxiv.org/abs/1903.09874.
  23. A. Merino and T. Mütze. Combinatorial generation via permutation languages. III. Rectangulations, 2021. Full preprint version of the present article. URL: http://arxiv.org/abs/2103.09333.
  24. W. J. Mitchell, J. P. Steadman, and R. S. Liggett. Synthesis and optimization of small rectangular floor plans. Environment and Planning B: Planning and Design, 3(1):37-70, 1976. URL: https://doi.org/10.1068/b030037.
  25. S. Nakano. Enumerating floorplans with n rooms. In Algorithms and computation (Christchurch, 2001), volume 2223 of Lecture Notes in Comput. Sci., pages 107-115. Springer, Berlin, 2001. URL: https://doi.org/10.1007/3-540-45678-3_10.
  26. OEIS Foundation Inc. The on-line encyclopedia of integer sequences, 2020. URL: http://oeis.org.
  27. R. H. J. M. Otten. Automatic floorplan design. In J. S. Crabbe, C. E. Radke, and H. Ofek, editors, Proceedings of the 19th Design Automation Conference, DAC '82, Las Vegas, Nevada, USA, June 14-16, 1982, pages 261-267. ACM/IEEE, 1982. URL: https://doi.org/10.1145/800263.809216.
  28. V. Pilaud and F. Santos. Quotientopes. Bull. Lond. Math. Soc., 51(3):406-420, 2019. URL: https://doi.org/10.1112/blms.12231.
  29. N. Reading. Generic rectangulations. European J. Combin., 33(4):610-623, 2012. URL: https://doi.org/10.1016/j.ejc.2011.11.004.
  30. F. Ruskey. Combinatorial Gray code. In M.-Y. Kao, editor, Encyclopedia of Algorithms, pages 342-347. Springer, 2016. Google Scholar
  31. C. Savage. A survey of combinatorial Gray codes. SIAM Rev., 39(4):605-629, 1997. URL: https://doi.org/10.1137/S0036144595295272.
  32. Z. C. Shen and C. C. N. Chu. Bounds on the number of slicing, mosaic, and general floorplans. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 22(10):1354-1361, 2003. URL: https://doi.org/10.1109/TCAD.2003.818136.
  33. M. Takagi and S. Nakano. Listing all rectangular drawings with certain properties. Systems and Computers in Japan, 35(4):1-8, 2004. URL: https://doi.org/10.1002/scj.10563.
  34. M. van Kreveld and B. Speckmann. On rectangular cartograms. Comput. Geom., 37(3):175-187, 2007. URL: https://doi.org/10.1016/j.comgeo.2006.06.002.
  35. A. Williams. The greedy Gray code algorithm. In Algorithms and Data Structures - 13th International Symposium, WADS 2013, London, ON, Canada, August 12-14, 2013. Proceedings, pages 525-536, 2013. URL: https://doi.org/10.1007/978-3-642-40104-6_46.
  36. K. Yamanaka, M. S. Rahman, and S. Nakano. Enumerating floorplans with columns. IEICE Trans. Fundam. Electron. Commun. Comput. Sci., 101-A(9):1392-1397, 2018. URL: https://doi.org/10.1587/transfun.E101.A.1392.
  37. B. Yao, H. Chen, C.-K. Cheng, and R. L. Graham. Floorplan representations: Complexity and connections. ACM Trans. Design Autom. Electr. Syst., 8(1):55-80, 2003. URL: https://doi.org/10.1145/606603.606607.
  38. S. Yoshii, D. Chigira, K. Yamanaka, and S. Nakano. Constant time generation of rectangular drawings with exactly n faces. IEICE Trans. Fundam. Electron. Commun. Comput. Sci., 89-A(9):2445-2450, 2006. URL: https://doi.org/10.1093/ietfec/e89-a.9.2445.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact