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 -