2026-07-24T18:31:34Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24247 2025-11-12T13:39:23Z ddc:004 open_access

An Improved Guillotine Cut for Squares Chalermsook, Parinya Kugelmann, Axel Orgo, Ly Uniyal, Sumedha Zarsav, Minoo Guillotine cuts Geometric Approximation Algorithms Rectangles Squares Given a set of n non-overlapping geometric objects, can we separate a constant fraction of them using straight-line cuts that extend from edge to edge? In 1996, Urrutia posed this question for compact convex objects. Pach and Tardos later refuted it for general line segments by constructing a family where any separable subfamily has size at most O (n^{log₃ 2}). However, for axis-parallel rectangles, they provided positive evidence, showing that an Ω(1/log n)-fraction can be separated. This problem naturally arises in geometric approximation algorithms. In particular, when restricting cuts to only orthogonal straight lines, known as a guillotine cut sequence, any bound on the separability ratio directly translates into a clean and simple dynamic programming for computing a maximum independent set of geometric objects. This paper focuses on the case when the objects are squares. For squares of arbitrary sizes, an Ω(1)-fraction can be separated (Abed et al., APPROX 2015), recently improved to 1/40 (and 1/160 ≈ 0.62% for the weighted case) (Khan and Pittu, APPROX 2020). We further improve this bound, showing that a 9/256 ≈ 3.51% can be separated for the weighted case. This result significantly narrows the possible range for squares to [3.51%, 50%]. The key to our improvement is a refined analysis of the existing framework. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Parinya Chalermsook and Axel Kugelmann and Ly Orgo and Sumedha Uniyal and Minoo Zarsav 2025 Is Part Of LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.WADS.2025.16 urn:nbn:de:0030-drops-242472 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.16 eng https://creativecommons.org/licenses/by/4.0/legalcode