TY - GEN
T1 - On separating points by lines
AU - Har-Peled, Sariel
AU - Jones, Mitchell
N1 - Publisher Copyright:
© Copyright 2018 by SIAM.
PY - 2018
Y1 - 2018
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. 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 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. 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 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=85045536078&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85045536078&partnerID=8YFLogxK
U2 - 10.1137/1.9781611975031.59
DO - 10.1137/1.9781611975031.59
M3 - Conference contribution
AN - SCOPUS:85045536078
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 918
EP - 932
BT - 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018
A2 - Czumaj, Artur
PB - Association for Computing Machinery
T2 - 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018
Y2 - 7 January 2018 through 10 January 2018
ER -