Abstract
We consider packing axis-aligned rectangles \(r_1,\ldots , r_n\) in the unit square \([0,1]^2\) such that a vertex of each rectangle \(r_i\) is a given point \(p_i\) (i.e., \(r_i\) is anchored at \(p_i\)); and explore the combinatorial structure of all locally maximal configurations. When the given points are lower-left corners of the rectangles, then the number of maximal packings is shown to be at most \(2^nC_n\), where \(C_n\) is the nth Catalan number. The number of maximal packings remains exponential in n when the points may be arbitrary corners of the rectangles. Our upper bounds are complemented with exponential lower bounds.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Ackerman, E.: Counting problems for geometric structures: rectangulations, floorplans, and quasi-planar graphs, PhD thesis, Technion (2016)
Ackerman, E., Barequet, G., Pinter, R.: On the number of rectangulations of a planar point set. J. Combin. Theory, Ser. A 113(6), 1072–1091 (2006)
Adamaszek, A., Wiese, A.: Approximation schemes for maximum weight independent set of rectangles. In: Proc. 54th FOCS. IEEE (2013)
Adamaszek, A., Wiese, A.: A quasi-PTAS for the two-dimensional geometric knapsack problem. In: Proc. 26th SODA. SIAM (2015)
Ahn, H.-K., Cheng, S.-W., Cheong, O., Golin, M., van Oostrum, R.: Competitive facility location: the Voronoi game. Theoret. Comput. Sci. 310, 457–467 (2004)
Ajtai, M., Chvátal, V., Newborn, M., Szemerédi, E.: Crossing-free subgraphs. Annals Discrete Math. 12, 9–12 (1982)
Avis, D., Fukuda, K.: Reverse search for enumeration Discrete Appl. Math. 65, 21–46 (1996)
Bansal, N., Khan, A.: Improved approximation algorithm for two-dimensional bin packing. In: Proc. 25th SODA, pp. 13–25. SIAM (2014)
Cheong, O., Har-Peled, S., Linial, N., Matoušek, J.: The one-round Voronoi game. Discrete Comput. Geom. 31, 125–138 (2004)
Dumitrescu, A., Schulz, A., Sheffer, A., Tóth, C.D.: Bounds on the maximum multiplicity of some common geometric graphs. SIAM J. Discrete Math. 27(2), 802–826 (2013)
Dumitrescu, A., Tóth, C.D.: Packing anchored rectangles. In: Proc. 23rd SODA, pp. 294–305. SIAM (2012); and Combinatorica 35(1), 39–61 (2015)
Francke, A., Tóth, C.D.: A census of plane graphs with polyline edges. In: Proc. 30th SoCG, pp. 242–250. ACM Press (2014)
Giménez, O., Noy, M.: Asymptotic enumeration and limit laws of planar graphs. J. AMS 22, 309–329 (2009)
Harren, R., Jansen, K., Prädel, L., van Stee, R.: A \((5/3+\varepsilon )\)-approximation for strip packing. Comput. Geom. 47(2), 248–267 (2014)
Kakoulis, K.G., Tollis, I.G.: Labeling algorithms, chap. 28. In: Tamassia, R. (ed.) Handbook of Graph Drawing and Visualization. CRC Press (2013)
Knuth, D., Raghunathan, A.: The problem of compatible representatives. SIAM J. Discete Math. 5, 36–47 (1992)
van Kreveld, M., Strijk, T., Wolff, A.: Point labeling with sliding labels. Comput. Geom. 13, 21–47 (1999)
Murata, H., Fujiyoshi, K., Nakatake, S., Kajitani, Y.: VLSI module placement based on rectangle-packing by the sequence-pair. IEEE Trans. CAD Integrated Circuits and Systems 15(12) (1996)
Santos, F., Seidel, R.: A better upper bound on the number of triangulations of a planar point set. J. Combin. Theory, Ser. A 102, 186–193 (2003)
Sharir, M., Sheffer, A.: Counting plane graphs: cross-graph charging schemes. Combinat. Probab. Comput. 22, 935–954 (2013)
Stanley, R.: Problem \(k^8\) in Catalan addendum to Enumerative Combinatorics, vol. 2, May 25, 2013. http://www-math.mit.edu/~rstan/ec/catadd.pdf
Thomas, H.: New combinatorial descriptions of the triangulations of cyclic polytopes and the second higher Stasheff-Tamari posets. Order 19(4), 327–342 (2002)
Tutte, W.: Recent Progress in Combinatorics: Proceedings of the 3rd Waterloo Conference on Combinatorics, May 1968. Academic Press, New York (1969)
Winkler, P.: Packing rectangles. In: Mathematical Mind-Benders, pp. 133–134, A.K. Peters Ltd., Wellesley (2007)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Balas, K., Tóth, C.D. (2015). On the Number of Anchored Rectangle Packings for a Planar Point Set. In: Xu, D., Du, D., Du, D. (eds) Computing and Combinatorics. COCOON 2015. Lecture Notes in Computer Science(), vol 9198. Springer, Cham. https://doi.org/10.1007/978-3-319-21398-9_30
Download citation
DOI: https://doi.org/10.1007/978-3-319-21398-9_30
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-21397-2
Online ISBN: 978-3-319-21398-9
eBook Packages: Computer ScienceComputer Science (R0)