Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

On Separating Points by Lines

  • Published:
Discrete & Computational Geometry Aims and scope Submit manuscript

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

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4

Similar content being viewed by others

Notes

  1. To see this, fix a point \(p\in P\). The probability that another point \(q\in P\) is at distance \(\le 1/n\) from \(p\) is equal to the probability that \(q\) falls in the disk \(D\) of radius 1 / n centered in \(p\). It follows that the event occurs with probability equal to \(\mathsf {area}\left( {D}\right) = \pi /n^2\).

  2. The constant depends polynomially on d.

  3. By Theorem 3.7 with \(\mu =1/4c\), and \(\delta = c_1 \log \mathsf {n}/ \log \log \mathsf {n}\), where \(c_1\) is a sufficiently large constant.

  4. Observe that a pair \(x,y\) is separated by a partition with probability at least half. Let X be the number of partitions separating this pair. The expected number of partitions separating this pair is \(\mu = \mathbb {E}[ X ] = M/2 = O( \log \mathsf {n})\). Setting \(\delta = 1/2\), we have by Theorem 3.7 that \(\mathbb {P}\!\,[ { X \le (1-\delta ) \mu } ] \le \exp ( - \mu \delta ^2 / 2) \le 1/n^{\Omega (1)}\), by making \(c_2\) sufficiently large. It follows that with high probability, the pair is separated in at least \((1-\delta )\mu = (c_2/2)\log \mathsf {n}\) partitions.

References

  1. Ambrus, G., Bárány, I.: Longest convex chains. Random Structures Algorithms 35(2), 137–162 (2009)

    Article  MathSciNet  Google Scholar 

  2. Agarwal, P.K., Ezra, E., Sharir, M.: Near-linear approximation algorithms for geometric hitting sets. Algorithmica 63(1–2), 1–25 (2012)

    Article  MathSciNet  Google Scholar 

  3. Agarwal, P.K., Matoušek, J., Schwarzkopf, O.: Computing many faces in arrangements of lines and segments. SIAM J. Comput. 27(2), 491–505 (1998)

    Article  MathSciNet  Google Scholar 

  4. Agarwal, P.K., Matoušek, J., Sharir, M.: On range searching with semialgebraic sets. II. SIAM J. Comput. 42(6), 2039–2062 (2013)

    Article  MathSciNet  Google Scholar 

  5. Agarwal, P.K., Pan, J.: Near-linear algorithms for geometric hitting sets and set covers. In: Proceedings of the 30th Annual Symposium on Computational Geometry (SoCG), pp. 271–279 (2014)

  6. Brönnimann, H., Goodrich, M.T.: Almost optimal set covers in finite VC-dimension. Discrete Comput. Geom. 14(4), 463–479 (1995)

    Article  MathSciNet  Google Scholar 

  7. Călinescu, G., Dumitrescu, A., Karloff, H.J., Wan, P.-J.: Separating points by axis-parallel lines. Internat. J. Comput. Geom. Appl. 15(6), 575–590 (2005)

    Article  MathSciNet  Google Scholar 

  8. Chazelle, B., Friedman, J.: A deterministic view of random sampling and its use in geometry. Combinatorica 10(3), 229–249 (1990)

    Article  MathSciNet  Google Scholar 

  9. Chazelle, B., Welzl, E.: Quasi-optimal range searching in space of finite vc-dimension. Discrete Comput. Geom. 4, 467–489 (1989)

    Article  MathSciNet  Google Scholar 

  10. Clarkson, K.L.: Algorithms for polytope covering and approximation. In: F.K.H.A. Dehne, J.-R. Sack, N. Santoro, S. Whitesides (eds.) Proceedings of the 3rd Workshop on Algorithms and Data Structures (WADS). Lecture Notes in Computer Science, vol. 709, pp. 246–252. Springer, New York (1993)

    Google Scholar 

  11. Dalal, K.: Counting the onion. Random Structures Algorithms 24(2), 155–165 (2004)

    Article  MathSciNet  Google Scholar 

  12. de Berg, M., Cheong, O., van Kreveld, M., Overmars, M.H.: Computational Geometry: Algorithms and Applications, 3rd edn. Springer, Santa Clara (2008)

    Book  Google Scholar 

  13. Devillers, O., Hurtado, F., Mora, M., Seara, C.: Separating several point sets in the plane. In: Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG), pp. 81–84 (2001)

  14. Dobkin, D.P., Kirkpatrick, D.G.: A linear algorithm for determining the separation of convex polyhedra. J. Algorithms 6(3), 381–392 (1985)

    Article  MathSciNet  Google Scholar 

  15. Dubhashi, D.P., Panconesi, A.: Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, Cambridge (2009)

    Book  Google Scholar 

  16. Fekete, S.P.: On simple polygonalizations with optimal area. Discrete Comput. Geom. 23(1), 73–110 (2000)

    Article  MathSciNet  Google Scholar 

  17. Freimer, R., Mitchell, J.S.B., Piatko, C.D.: On the complexity of shattering using arrangements. Technical Report TR 91-1197, Department of Computer Science, Cornell University, Ithaca (1991)

  18. Har-Peled, S.: Geometric Approximation Algorithms. Mathematical Surveys and Monographs, vol. 173. American Mathematical Society, Boston, MA (2011)

    MATH  Google Scholar 

  19. Har-Peled, S.: On the expected complexity of random convex hulls. (2011). CoRR, arXiv:1111.5340

  20. Har-Peled, S., Jones, M.: On separating points by lines. In: Czumaj, A. (ed.) Proceedings of the 29th ACM-SIAM Sympososium on Discrete Algorithms (SODA’19), pp. 918–932. SIAM (2018)

    Chapter  Google Scholar 

  21. Har-Peled, S., Lidicky, B.: Peeling the grid. SIAM J. Discret. Math. 27(2), 650–655 (2013)

    Article  MathSciNet  Google Scholar 

  22. Haussler, D., Welzl, E.: \(\varepsilon \)-nets and simplex range queries. Discrete Comput. Geom. 2, 127–151 (1987)

    Article  MathSciNet  Google Scholar 

  23. Hinton, G., Salakhutdinov, R.: Reducing the dimensionality of data with neural networks. Science 313(5786), 504–507 (2006)

    Article  MathSciNet  Google Scholar 

  24. Kynčl, J.: Vapnik–Chervonenkis dimension of lines in the plane. (2012). http://mathoverflow.net/questions/98412/vapnik-chervonenkis-dimension-of-lines-in-the-plane

  25. Matoušek, J.: Efficient partition trees. Discrete Comput. Geom. 8, 315–334 (1992)

    Article  MathSciNet  Google Scholar 

  26. Nandy, S.C., Asano, T., Harayama, T.: Shattering a set of objects in 2D. Discret. Appl. Math. 122(1–3), 183–194 (2002)

    Article  MathSciNet  Google Scholar 

  27. Sharir, M., Agarwal, P.K.: Davenport–Schinzel Sequences and Their Geometric Applications. Cambridge University Press, New York (1995)

    MATH  Google Scholar 

  28. Steiger, W., Zhao, J.: Generalized ham-sandwich cuts. Discrete Comput. Geom. 44(3), 535–545 (2010)

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgements

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.

Funding

Funding was provided by Division of Computing and Communication Foundations (Grant Nos. 1421231, 1217462).

Author information

Authors and Affiliations

  1. Department of Computer Science, University of Illinois, 201 N. Goodwin Avenue, Urbana, IL, 61801, USA

    Sariel Har-Peled & Mitchell Jones

Authors
  1. Sariel Har-Peled
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Mitchell Jones
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Mitchell Jones.

Additional information

Editor in Charge: Kenneth Clarkson

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

A preliminary version of this paper appeared in SODA 2018 [20].

S. Har-Peled: Work on this paper was partially supported by NSF AF Awards CCF-1421231, and CCF-1217462.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Har-Peled, S., Jones, M. On Separating Points by Lines. Discrete Comput Geom 63, 705–730 (2020). https://doi.org/10.1007/s00454-019-00103-z

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00454-019-00103-z

Search

Navigation