Applications of incidence bounds in point covering problems

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review



  • Peyman Afshani
  • ,
  • Edvin Berglin
  • Ingo Van Duijn
  • ,
  • Jesper Sindahl Nielsen

In the Line Cover problem a set of n points is given and the task is to cover the points using either the minimum number of lines or at most k lines. In Curve Cover, a generalization of Line Cover, the task is to cover the points using curves with d degrees of freedom. Another generalization is the Hyperplane Cover problem where points in d-dimensional space are to be covered by hyperplanes. All these problems have kernels of polynomial size, where the parameter is the minimum number of lines, curves, or hyperplanes needed. First we give a non-parameterized algorithm for both problems in O∗(2n) (where the O∗(•) notation hides polynomial factors of n) time and polynomial space, beating a previous exponential-space result. Combining this with incidence bounds similar to the famous Szemerédi-Trotter bound, we present a Curve Cover algorithm with running time O∗((Ck/log k)(d-1)k), where C is some constant. Our result improves the previous best times O∗((k/1.35)k) for Line Cover (where d = 2), O∗(kdk) for general Curve Cover, as well as a few other bounds for covering points by parabolas or conics. We also present an algorithm for Hyperplane Cover in double-struck R3 with running time O∗((Ck2/log1/5k)k), improving on the previous time of O∗((k2/1.3)k).

Original languageEnglish
Title of host publication32nd International Symposium on Computational Geometry, SoCG 2016
EditorsSándor Fekete, Anna Lubiw
Number of pages15
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Publication year1 Jun 2016
ISBN (Electronic)9783959770095
Publication statusPublished - 1 Jun 2016
Event32nd International Symposium on Computational Geometry, SoCG 2016 - Boston, United States
Duration: 14 Jun 201617 Jun 2016


Conference32nd International Symposium on Computational Geometry, SoCG 2016
LandUnited States
Sponsoret al, National Science Foundation (NSF), Princeton University, The Center for Geometry and its Applications (SRC-GAIA), The Fields Institute for Research in Mathematical Sciences, Tufts University
SeriesLeibniz International Proceedings in Informatics

    Research areas

  • Exponential algorithm, Incidence bounds, Inclusion exclusion, Point cover

See relations at Aarhus University Citationformats

Download statistics

No data available

ID: 108480631