TY - JOUR

T1 - On Separating Points by Lines

AU - Har-Peled, Sariel

AU - Jones, Mitchell

N1 - Funding Information:
The authors thank Danny Halperin for asking the question that led to the results in Sect. 3. The authors also thank the anonymous referees for their detailed comments.
Publisher Copyright:
© 2019, Springer Science+Business Media, LLC, part of Springer Nature.

PY - 2020/4/1

Y1 - 2020/4/1

N2 - 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, denoted by sep (P). We show that the minimum number of lines needed to separate n points, picked randomly (and uniformly) in the unit square, is Θ ~ (n2 / 3) , where Θ ~ hides polylogarithmic factors. In addition, we provide a fast O(log (sep (P))) -approximation algorithm for computing the separability of a given point set in the plane. Finally, we point out the connection between separability and partitions.

AB - 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, denoted by sep (P). We show that the minimum number of lines needed to separate n points, picked randomly (and uniformly) in the unit square, is Θ ~ (n2 / 3) , where Θ ~ hides polylogarithmic factors. In addition, we provide a fast O(log (sep (P))) -approximation algorithm for computing the separability of a given point set in the plane. Finally, we point out the connection between separability and partitions.

UR - http://www.scopus.com/inward/record.url?scp=85066504821&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85066504821&partnerID=8YFLogxK

U2 - 10.1007/s00454-019-00103-z

DO - 10.1007/s00454-019-00103-z

M3 - Article

AN - SCOPUS:85066504821

SN - 0179-5376

VL - 63

SP - 705

EP - 730

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

IS - 3

ER -