An Improved Guillotine Cut for Squares

Thumbnail Image

Files

An_Improved_Guillotine_Cut_for_Squares.pdf (729.27 KB)

Access rights

openAccess
CC BY
publishedVersion

URL

Journal Title

Journal ISSN

Volume Title

A4 Artikkeli konferenssijulkaisussa
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.

Authors

Date

2025-08-29

Department

Department of Computer Science

Major/Subject

Mcode

Degree programme

Language

en

Pages

Series

19th International Symposium on Algorithms and Data Structures, WADS 2025, Leibniz International Proceedings in Informatics, LIPIcs ; Volume 349

Abstract

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 (nlog3 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.

Description

Publisher Copyright: © Parinya Chalermsook, Axel Kugelmann, Ly Orgo, Sumedha Uniyal, and Minoo Zarsav. | openaire: EC/H2020/759557/EU//ALGOCom

Keywords

Geometric Approximation Algorithms, Guillotine cuts, Rectangles, Squares

Other note

DOI

10.4230/LIPIcs.WADS.2025.16

Citation

Chalermsook, P, Kugelmann, A, Orgo, L, Uniyal, S & Zarsav, M 2025, An Improved Guillotine Cut for Squares. in P Morin & E Oh (eds), 19th International Symposium on Algorithms and Data Structures, WADS 2025., 16, Leibniz International Proceedings in Informatics, LIPIcs, vol. 349, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, International Symposium on Algorithms and Data Structures, Toronto, Canada, 11/08/2025. https://doi.org/10.4230/LIPIcs.WADS.2025.16

Permanent link to this item

https://urn.fi/URN:NBN:fi:aalto-202511058666

Collections

[article-cris] Perustieteiden korkeakoulu / SCI