Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Curves, points, inci ...
Article

Curves, points, incidences and covering

Arijit Bishnu (1), Mathew Francis (1), Pritam Majumder (1)
(1) Indian Statistical Institute [ISI]
Download article
Open on arXiv
Submitted on
November 11, 2025
Accepted on
June 20, 2026
Published on
September 7, 2026
Last modified on
September 22, 2026
Volume 28
vol. 28:3
Combinatorics
DOI
10.46298/dmtcs.16899
License
Attribution 4.0 International (CC BY 4.0)
Indicators
64
Views
37
Downloads

Curves, points, incidences and covering

Arijit Bishnu (1), Mathew Francis (1), Pritam Majumder (1)
(1) Indian Statistical Institute [ISI]
Abstract
Given a point set, mostly a grid in our case, we seek upper and lower bounds on the number of curves that are needed to cover the point set. We say a curve covers a point if the curve passes through the point. We consider such coverings by monotonic curves, lines, orthoconvex curves, circles, etc. We also study a problem that is converse of the covering problem -- if a set of $n^2$ points in the plane is covered by $n$ lines then can we say something about the configuration of the points?
Keywords
  • Combinatorics
  • Computational Geometry
  • Discrete Mathematics
Preview
Loading PDF preview...
References

  1. P. Afshani, E. Berglin, I. van Duijn, and J. S. Nielsen. Applications of incidence bounds in point covering problems. In 32nd SoCG, June 14-18, 2016, volume 51 of LIPIcs, pages 60:1-60:15, 2016.

    DOI : 10.4230/LIPIcs.SoCG.2016.60

  2. N. Alon. Combinatorial nullstellensatz. Combinatorics, Probability and Computing, 8(1-2):7-29, 1999. doi: 10.1017/S0963548398003411.

    DOI : 10.1017/s0963548398003411

  3. G. E. Andrews. An asymptotic expression for the number of solutions of a general class of diophantine equations. Trans. Amer. Math. Soc., 99:272-277, 1961.

    DOI : 10.1090/s0002-9947-1961-0120222-7

  4. E. M. Arkin, J. S. Mitchell, and C. D. Piatko. Minimum-link watchman tours. Information Processing Letters, 86(4):203-207, 2003. doi: 10.1016/s0020-0190(02)00502-1.

    DOI : 10.1016/s0020-0190(02)00502-1

  5. B. C. Berndt and R. A. Rankin. Ramanujan: Letters and Commentary. Amer. Math. Soc., Providence, RI, 1995. ISBN 0821804707.

    DOI : 10.1090/hmath/009

  6. A. Biniaz. Improved bounds for covering paths and trees in the plane. Journal of Computational Geometry, 15(1):88-108, 2024.

    DOI : 10.20382/jocg.v15i1a4

  7. J. Boissonnat, K. Dutta, A. Ghosh, and S. Kolay. Tight kernels for covering and hitting: Point hy- perplane cover and polynomial point hitting set. In LATIN 2018, April 16-19, 2018, Proceedings, volume 10807 of Lecture Notes in Computer Science, pages 187-200. Springer, 2018.

    DOI : 10.1007/978-3-319-77404-6_15

  8. E. Bombieri and J. Pila. The number of integral points on arcs and ovals. Duke Mathematical Journal, 59 (2):337 -357, 1989. doi: 10.1215/S0012-7094-89-05915-2.

    DOI : 10.1215/s0012-7094-89-05915-2

  9. P. Brass, W. Moser, and J. Pach. Research problems in discrete geometry. Springer, 2005.

    DOI : 10.1007/0-387-29929-7

  10. J. Cerný, Z. Dvorák, V. Jelínek, and J. Kára. Noncrossing hamiltonian paths in geometric graphs. Discrete Applied Mathematics, 155(9):1096-1105, 2007.

    DOI : 10.1016/j.dam.2005.12.010

  11. J. Chen, Q. Huang, I. Kanj, and G. Xia. Near-optimal algorithms for point-line covering problems. arXiv preprint arXiv:2012.02363, 2021.

    DOI : 10.48550/arXiv.2012.02363

  12. M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh. Parameterized Algorithms. Springer, 1st edition, 2015. ISBN 3319212745, 9783319212746.

    DOI : 10.5555/2815661

  13. R. P. Dilworth. A decomposition theorem for partially ordered sets. Annals of Mathematics, 51(1):161- 166, 1950. doi: 10.2307/1969503.

    DOI : 10.2307/1969503

  14. A. Dumitrescu and C. D. Tóth. Covering grids by trees. In CCCG, 2014.

  15. A. Dumitrescu, D. Gerbner, B. Keszegh, and C. D. Tóth. Covering paths for planar point sets. Discrete and Computational Geometry, 51(2):462-484, 2014. doi: 10.1007/s00454-013-9563-4.

    DOI : 10.1007/s00454-013-9563-4

  16. K. Engel. Sperner Theory. Encyclopedia of Mathematics and its Applications. Cambridge University Press, 1997.

    DOI : 10.1017/CBO9780511574719

  17. P. Erdös. Problems and results in combinatorial geometry. Annals of the New York Academy of Sciences, 440:1-11, 1985.

    DOI : 10.1111/j.1749-6632.1985.tb14533.x

  18. M. Grantson and C. Levcopoulos. Covering a set of points with a minimum number of lines. In Italian Conference on Algorithms and Complexity, pages 6-17. Springer, 2006.

    DOI : 10.1007/11758471_4

  19. L. Guth. Polynomial Methods in Combinatorics. University Lecture Series 64. Amer. Math. Soc., 2016. ISBN 9781470428907.

    DOI : 10.1090/ulect/064

  20. P. Ivanisvili, O. Klein, and R. Vershynin. Covering the hypercube, the uncertainty principle, and an interpolation formula. The Electronic Journal of Combinatorics, 32(4), 2025.

    DOI : 10.37236/12756

  21. B. Keszegh. Covering paths and trees for planar grids. Geombinatorics Quarterly, 24(1):5-10, 2014.

  22. S. Kratsch, G. Philip, and S. Ray. Point line cover: The easy kernel is essentially tight. ACM Trans. Algorithms, 12(3):40:1-40:16, 2016. doi: 10.1145/2832912.

    DOI : 10.1145/2832912

  23. E. Landau. Uber die einteilung der positiven ganzen zahlen in vier klassen ¨nach der mindeszahl der zu ihrer additiven zusammensetzung erforderlichen quadrate. Arch. Math. Phys., 13:305-312, 1908.

  24. N. Linial and J. Radhakrishnan. Essential covers of the cube by hyperplanes. Journal of Combinatorial Theory, Series A, 109(2):331-338, 2005.

  25. J. Pach and P. K. Agarwal. Combinatorial geometry. Wiley-Interscience series in discrete mathematics and optimization. Wiley, 1995. ISBN 978-0-471-58890-0. doi: 10.1002/9781118033203.

    DOI : 10.1002/9781118033203

  26. L. Saurmann and Z. Xu. Essential covers of the hypercube require many hyperplanes. Combina- torics, Probability and Computing, 34(3):326-337, 2024.

    DOI : 10.1017/s0963548324000257

  27. A. Sheffer. Polynomial Methods and Incidence Theory. Cambridge Studies in Advanced Mathematics. Cambridge University Press, 2022. doi: 10.1017/9781108959988.

    DOI : 10.1017/9781108959988

  28. E. Szemerédi and W. Trotter. Extremal problems in discrete geometry. Combinatorica, 3:3-4, 1983. doi: 10.1007/BF02579194.

    DOI : 10.1007/bf02579194

  29. J. Matousek. Lectures on discrete geometry, volume 212 of Graduate texts in mathematics. Springer, 2002.

    DOI : 10.1007/978-1-4613-0039-7