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 -