On Linear-Size Guillotine-Separable Subsets of Fat Convex Objects, Disks, and Squares
2026-07-27 • Computational Geometry
Computational Geometry
AI summaryⓘ
The authors study when a group of non-overlapping fat convex shapes in the plane or higher dimensions can be separated from each other using a sequence of straight cuts that don’t intersect the shapes (called guillotine cuts). Previous work showed this is possible for squares and some special cases but left open whether this can be done for all fat convex shapes, like disks. The authors solved this problem affirmatively, proving that any family of such shapes always contains a large subset that can be separated this way, even in higher dimensions. They also improved known proportions of separable subsets for axis-aligned squares and disks using new techniques.
guillotine cutsfat convex objectsseparable subsetdisksaxis-aligned squaresrecursive separabilityhyperplane cutspacking inequalityconvex geometrycombinatorial geometry
Authors
Mark de Berg, Debajyoti Kar, Arindam Khan, Rudrayan Kundu
Abstract
Let $\mathcal{K}$ be a family of pairwise disjoint objects in the plane. We say that a subset $\mathcal{K}^*\subseteq \mathcal{K}$ is \emph{separable} if it admits a sequence of guillotine cuts that separate all objects in $\mathcal{K}^*$ from each other while not cutting any of them. Urrutia (1996) asked whether any family of $n$ convex objects has a separable subset of size $Ω(n)$. Pach and Tardos (2000) answered this question negatively for line segments, but established positive results for fat objects of similar size. More recently, it was shown that sets of arbitrarily-sized axis-aligned squares also admit a separable subset of linear size. However, the question whether any set of arbitrarily-sized fat convex objects has a separable subset of linear size has remained open, even for disks. A major obstacle is that the existing technique for arbitrarily-sized squares uses only axis-aligned cuts, while even for disks, axis-aligned cuts alone are insufficient to obtain a separable subset of linear size. We resolve this longstanding open problem by proving that every family of pairwise disjoint fat convex objects has a separable subset of linear size. Our result extends to higher dimensions: any family of pairwise disjoint arbitrarily-sized fat convex objects in $\mathbb{R}^d$, where $d$ is a fixed constant, has a subset of linear size that is recursively separable by a sequence of hyperplane cuts. Our framework also yields improved guarantees for important special cases. For axis-aligned squares with axis-aligned guillotine cuts, we leverage additional structural properties of squares to show that at least $13.46\%$ of the squares are separable, improving the previous best bound of $9/256 \approx 3.51\%$ due to Chalermsook, Kugelmann, Orgo, Uniyal, and Zarsav (2025). For disks, by exploiting Oler's packing inequality, we prove that at least $n/93$ disks can always be separated.