On Separating Points by Lines

2017/06/06 by Sariel Har-Peled, Har-Peled, Sariel, Mitchell Jones +1 · 1 citation
Computer Science · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Data Management and Algorithms #FOS: Computer and information sciences #Graph Labeling and Dimension Problems

paper · pdf · doi:10.48550/arxiv.1706.02004

openalex publication_date 2017/06/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Given a set P of n points in the plane, its separability is the minimum number of lines needed to separate all its pairs of points from each other. We show that the minimum number of lines needed to separate n points, picked randomly (and uniformly) in the unit square, is Θ( n^2/3), where Θ hides polylogarithmic factors. In addition, we provide a fast approximation algorithm for computing the separability of a given point set in the plane. Finally, we point out the connection between separability and partitions.

Cited by

• Time to Spike? Understanding the Representational Power of Spiking Neural Networks in Discrete Time

Related

• Separating Colored Points with Minimum Number of Rectangles
• On the Parameterized Complexity of Red-Blue Points Separation
• On Equal Point Separation by Planar Cell Decompositions
• Few Cuts Meet Many Point Sets
• Separating families of convex sets