License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2016.60
URN: urn:nbn:de:0030-drops-59527
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/5952/
Go to the corresponding LIPIcs Volume Portal

Afshani, Peyman ; Berglin, Edvin ; van Duijn, Ingo ; Sindahl Nielsen, Jesper

Applications of Incidence Bounds in Point Covering Problems

pdf-format:
LIPIcs-SoCG-2016-60.pdf (0.5 MB)

Abstract

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*(2^n) (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 Szemeredi-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*(k^(dk)) 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 R^3 with running time O*((Ck^2/log^(1/5) k)^k), improving on the previous time of O*((k^2/1.3)^k).

BibTeX - Entry

@InProceedings{afshani_et_al:LIPIcs:2016:5952,
  author =	{Peyman Afshani and Edvin Berglin and Ingo van Duijn and Jesper Sindahl Nielsen},
  title =	{{Applications of Incidence Bounds in Point Covering Problems}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{60:1--60:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{S{\'a}ndor Fekete and Anna Lubiw},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/5952},
  URN =		{urn:nbn:de:0030-drops-59527},
  doi =		{10.4230/LIPIcs.SoCG.2016.60},
  annote =	{Keywords: Point Cover, Incidence Bounds, Inclusion Exclusion, Exponential Algorithm}
}

Keywords: Point Cover, Incidence Bounds, Inclusion Exclusion, Exponential Algorithm
Collection: 32nd International Symposium on Computational Geometry (SoCG 2016)
Issue Date: 2016
Date of publication: 10.06.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI