Separating families of convex sets

2012/11/13 by Dániel Gerbner, D. Gerbner, Gerbner, D. +3
Computer Science · Mathematics · #52C45 #Advanced Optimization Algorithms Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Metric Geometry (math.MG) #Optimization and Search Problems #math.CO #math.MG #msc:52C45

paper · pdf · doi:10.48550/arxiv.1211.2982

arxiv created 2012/11/13 · openalex publication_date 2012/11/13 · arxiv updated 2012/11/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Two elements, x and y, are separated by a set S if it contains exactly one of x and y. We prove that any set of n points in general position in the plane can be separated by O(nloglog n/log n) convex sets, and for some point sets Ω(n/log n) convex sets are necessary.

Related

• Separation of Convex Sets via Barrier Cones
• On the separation theorems for convex sets on the unit sphere
• Separation in Simply Linked Neighbourly 4-Polytopes
• A Non-Convex Separation Through an Alternative Proof for the Supporting Hyperplane Theorem
• Convex decompositions of point sets in the plane