2026/07/27 by Mark de Berg, Debajyoti Kar, Arindam Khan +1
Computer Science · #cs.CG
Let K be a family of pairwise disjoint objects in the plane. We say that a subset K^*⊆ K is separable if it admits a sequence of guillotine cuts that separate all objects in 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 ℝ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 ≈ 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.