Guillotine partition

<h2 id="computing-a-guillotine-partition-with-a-smallest-edge-length">Computing a guillotine partition with a smallest edge-length</h2>
In the minimum edge-length rectangular-partition problem, the goal is to partition the original rectilinear polygon into rectangles, such that the total edge length is a minimum.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a>: 166–167 
This problem can be solved in time 
 
 
 
 O
 (
 
 n
 
 5
 
 
 )
 
 
 {\displaystyle O(n^{5})}
 
 even if the raw polygon has holes. The algorithm uses <a href="/facts/Dynamic_programming/CLcabtmk">dynamic programming</a> based on the following observation: there exists a minimum-length guillotine rectangular partition in which every maximal line segment contains a vertex of the boundary. Therefore, in each iteration, there are 
 
 
 
 O
 (
 n
 )
 
 
 {\displaystyle O(n)}
 
 possible choices for the next guillotine cut, and there are altogether 
 
 
 
 O
 (
 
 n
 
 4
 
 
 )
 
 
 {\displaystyle O(n^{4})}
 
 subproblems.
In the special case in which all holes are degenerate (single points), the minimum-length guillotine rectangular partition is at most 2 times the minimum-length rectangular partition.<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a>: 167–170  By a more careful analysis, it can be proved that the approximation factor is in fact at most 1.75. It is not known if the 1.75 is tight, but there is an instance in which the approximation factor is 1.5.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a> Therefore, the guillotine partition provides a constant-factor approximation to the general problem, which is NP-hard.
These results can be extended to a d-dimensional box: a guillotine-partition with minimum edge-length can be found in time 
 
 
 
 O
 (
 d
 
 n
 
 2
 d
 +
 1
 
 
 )
 
 
 {\displaystyle O(dn^{2d+1})}
 
, and the total (d-1)-volume in the optimal guillotine-partition is at most 
 
 
 
 2
 d
 −
 4
 +
 4
 
 /
 
 d
 
 
 {\displaystyle 2d-4+4/d}
 
 times that of an optimal d-box partition.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a>
Arora<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a> and Mitchell<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a> used the guillotine-partitioning technique to develop <a href="/facts/Polynomial-time_approximation_scheme/52Chjx9y">polynomial-time approximation schemes</a> for various geometric optimization problems.

<h2 id="number-of-guillotine-partitions">Number of guillotine partitions</h2>
Besides the computational problems, guillotine partitions were also studied from a combinatorial perspective. Suppose a given rectangle should be partitioned into smaller rectangles using guillotine cuts only. Obviously, there are infinitely many ways to do this, since even a single cut can take infinitely many values. However, the number of structurally-different guillotine partitions is bounded.

<ul><li>In two dimensions, there is an upper bound in 
 
 
 
 O
 
 (
 
 
 
 n
 !
 
 2
 
 5
 n
 −
 3
 
 
 
 
 n
 
 3
 
 /
 
 2
 
 
 
 
 )
 
 
 
 {\displaystyle O\left({\frac {n!2^{5n-3}}{n^{3/2}}}\right)}
 
 attributed to <a href="/facts/Donald_Knuth/GozNzDM6">Knuth</a>. the exact number is the <a href="/facts/Schr%25C3%25B6der_number/shyAgU2o">Schröder number</a>.<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a></li>
<li></li>
<li>In d dimensions, Ackerman, Barequet, Pinter and Romik<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a> give an exact summation formula, and prove that it is in 
 
 
 
 Θ
 
 (
 
 
 
 (
 2
 d
 −
 1
 +
 2
 
 
 d
 (
 d
 −
 1
 )
 
 
 
 )
 
 n
 
 
 
 
 n
 
 3
 
 /
 
 2
 
 
 
 
 )
 
 
 
 {\displaystyle \Theta \left({\frac {(2d-1+2{\sqrt {d(d-1)}})^{n}}{n^{3/2}}}\right)}
 
. When d=2 this bound becomes 
 
 
 
 Θ
 
 (
 
 
 
 (
 3
 +
 2
 
 
 2
 
 
 
 )
 
 n
 
 
 
 
 n
 
 3
 
 /
 
 2
 
 
 
 
 )
 
 
 
 {\displaystyle \Theta \left({\frac {(3+2{\sqrt {2}})^{n}}{n^{3/2}}}\right)}
 
.</li>
<li>Asinowski, Barequet, Mansour and Pinter<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a> also study the number of cut-equivalence classes of guillotine partitions.</li></ul>
<h2 id="coloring-guillotine-partitions">Coloring guillotine partitions</h2>
A polychromatic coloring of a <a href="/facts/Planar_graph/plREagr9">planar graph</a> is a coloring of its vertices such that, in each <a href="/facts/Face_(graph_theory)/W0MqKkyE">face</a> of the graph, each color appears at least once. Several researchers have tried to find the largest k such that a polychromatic k-coloring always exists. An important special case is when the graph represents a partition of a rectangle into rectangles.

<ul><li>Dinitz, Katz and Krakovski<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a> proved that there always exists a polychromatic 3-coloring.</li>
<li>Aigner-Horev, Katz, Krakovski and Loffler<a class="footnote-ref" id="fnref:12" href="#fn:12">12</a> proved that, in the special sub-case in which the graph represents a guillotine partition, a strong polychromatic 4-coloring always exists.</li>
<li>Keszegh<a class="footnote-ref" id="fnref:13" href="#fn:13">13</a> extended this result to d-dimensional guillotine partitions, and provided an efficient coloring algorithm.</li>
<li>Dimitrov, Aigner-Horev and Krakovski<a class="footnote-ref" id="fnref:14" href="#fn:14">14</a> finally proved that there always exists a strong polychromatic 4-coloring.</li></ul>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Binary_space_partitioning/sn9MhTSB">Binary space partitioning</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Lengauer, Thomas (1990), "Circuit Partitioning", Combinatorial Algorithms for Integrated Circuit Layout, Wiesbaden: Vieweg+Teubner Verlag, pp. 251–301, doi:10.1007/978-3-322-92106-2_6, ISBN 978-3-322-92108-6, retrieved 2021-01-16 <a href="978-3-322-92108-6" target="_blank">978-3-322-92108-6</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Du, Ding-Zhu; Ko, Ker-I.; Hu, Xiaodong (2012). Design and Analysis of Approximation Algorithms. Springer Optimization and Its Applications. New York: Springer-Verlag. pp. 165–209, chapter 5 "guillotine cut". ISBN 978-1-4614-1700-2. <a href="978-1-4614-1700-2" target="_blank">978-1-4614-1700-2</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Du, Ding-Zhu; Ko, Ker-I.; Hu, Xiaodong (2012). Design and Analysis of Approximation Algorithms. Springer Optimization and Its Applications. New York: Springer-Verlag. pp. 165–209, chapter 5 "guillotine cut". ISBN 978-1-4614-1700-2. <a href="978-1-4614-1700-2" target="_blank">978-1-4614-1700-2</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Gonzalez, Teofilo; Zheng, Si-Qing (1989-06-01). "Improved bounds for rectangular and guillotine partitions". Journal of Symbolic Computation. 7 (6): 591–610. doi:10.1016/S0747-7171(89)80042-2. ISSN 0747-7171. <a href="https://doi.org/10.1016%2FS0747-7171%2889%2980042-2" target="_blank">https://doi.org/10.1016%2FS0747-7171%2889%2980042-2</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Gonzalez, Teofilo F.; Razzazi, Mohammadreza; Shing, Man-Tak; Zheng, Si-Qing (1994-05-01). "On optimal guillotine partitions approximating optimal d-box partitions". Computational Geometry. 4 (1): 1–11. doi:10.1016/0925-7721(94)90013-2. ISSN 0925-7721. <a href="https://doi.org/10.1016%2F0925-7721%2894%2990013-2" target="_blank">https://doi.org/10.1016%2F0925-7721%2894%2990013-2</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Arora, S. (October 1996). "Polynomial time approximation schemes for Euclidean TSP and other geometric problems". Proceedings of 37th Conference on Foundations of Computer Science. pp. 2–11. doi:10.1109/SFCS.1996.548458. ISBN 0-8186-7594-2. S2CID 1499391. <a href="0-8186-7594-2" target="_blank">0-8186-7594-2</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Mitchell, Joseph S. B. (1999-01-01). "Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems". SIAM Journal on Computing. 28 (4): 1298–1309. doi:10.1137/S0097539796309764. ISSN 0097-5397. <a href="https://epubs.siam.org/doi/abs/10.1137/S0097539796309764" target="_blank">https://epubs.siam.org/doi/abs/10.1137/S0097539796309764</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Yao, Bo; Chen, Hongyu; Cheng, Chung-Kuan; Graham, Ronald (2003-01-01). "Floorplan representations: Complexity and connections". ACM Transactions on Design Automation of Electronic Systems. 8 (1): 55–80. doi:10.1145/606603.606607. ISSN 1084-4309. S2CID 1645358. <a href="https://doi.org/10.1145/606603.606607" target="_blank">https://doi.org/10.1145/606603.606607</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Ackerman, Eyal; Barequet, Gill; Pinter, Ron Y.; Romik, Dan (2006-05-31). "The number of guillotine partitions in d dimensions". Information Processing Letters. 98 (4): 162–167. doi:10.1016/j.ipl.2006.01.011. ISSN 0020-0190. <a href="http://www.sciencedirect.com/science/article/pii/S0020019006000305" target="_blank">http://www.sciencedirect.com/science/article/pii/S0020019006000305</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Asinowski, Andrei; Barequet, Gill; Mansour, Toufik; Pinter, Ron Y. (2014-09-28). "Cut equivalence of d-dimensional guillotine partitions". Discrete Mathematics. 331: 165–174. doi:10.1016/j.disc.2014.05.014. ISSN 0012-365X. <a href="https://doi.org/10.1016%2Fj.disc.2014.05.014" target="_blank">https://doi.org/10.1016%2Fj.disc.2014.05.014</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Dinitz, Yefim; Katz, Matthew J.; Krakovski, Roi (2009-12-01). "Guarding rectangular partitions". International Journal of Computational Geometry & Applications. 19 (6): 579–594. doi:10.1142/S0218195909003131. ISSN 0218-1959. <a href="https://www.worldscientific.com/doi/abs/10.1142/S0218195909003131" target="_blank">https://www.worldscientific.com/doi/abs/10.1142/S0218195909003131</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">Horev, Elad; Katz, Matthew J.; Krakovski, Roi; Löffler, Maarten (2009-06-15). "Polychromatic 4-coloring of guillotine subdivisions". Information Processing Letters. 109 (13): 690–694. doi:10.1016/j.ipl.2009.03.006. ISSN 0020-0190. <a href="http://www.sciencedirect.com/science/article/pii/S0020019009000854" target="_blank">http://www.sciencedirect.com/science/article/pii/S0020019009000854</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">Keszegh, Balázs (2008). "Polychromatic Colorings of n-Dimensional Guillotine-Partitions". In Hu, Xiaodong; Wang, Jie (eds.). Computing and Combinatorics. Lecture Notes in Computer Science. Vol. 5092. Berlin, Heidelberg: Springer. pp. 110–118. doi:10.1007/978-3-540-69733-6_12. ISBN 978-3-540-69733-6. <a href="978-3-540-69733-6" target="_blank">978-3-540-69733-6</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
<li id="fn:14">Dimitrov, Darko; Horev, Elad; Krakovski, Roi (2009-05-06). "Polychromatic colorings of rectangular partitions". Discrete Mathematics. 309 (9): 2957–2960. doi:10.1016/j.disc.2008.07.035. ISSN 0012-365X. <a href="https://doi.org/10.1016%2Fj.disc.2008.07.035" target="_blank">https://doi.org/10.1016%2Fj.disc.2008.07.035</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></li>
</ol>

Guillotine partition open-in-new

Guillotine partition