Chen, Jianer ;
Huang, Qin ;
Kanj, Iyad ;
Xia, Ge
NearOptimal Algorithms for PointLine Covering Problems
Abstract
We study fundamental pointline covering problems in computational geometry, in which the input is a set S of points in the plane. The first is the Rich Lines problem, which asks for the set of all lines that each covers at least λ points from S, for a given integer parameter λ ≥ 2; this problem subsumes the 3PointsonLine problem and the Exact Fitting problem, which  the latter  asks for a line containing the maximum number of points. The second is the NPhard problem Line Cover, which asks for a set of k lines that cover the points of S, for a given parameter k ∈ ℕ. Both problems have been extensively studied. In particular, the Rich Lines problem is a fundamental problem whose solution serves as a building block for several algorithms in computational geometry.
For Rich Lines and Exact Fitting, we present a randomized Monte Carlo algorithm that achieves a lower running time than that of Guibas et al.’s algorithm [Computational Geometry 1996], for a wide range of the parameter λ. We derive lowerbound results showing that, for λ = Ω(√{n log n}), the upper bound on the running time of this randomized algorithm matches the lower bound that we derive on the time complexity of Rich Lines in the algebraic computation trees model.
For Line Cover, we present two kernelization algorithms: a randomized Monte Carlo algorithm and a deterministic algorithm. Both algorithms improve the running time of existing kernelization algorithms for Line Cover. We derive lowerbound results showing that the running time of the randomized algorithm we present comes close to the lower bound we derive on the time complexity of kernelization algorithms for Line Cover in the algebraic computation trees model.
BibTeX  Entry
@InProceedings{chen_et_al:LIPIcs.STACS.2022.21,
author = {Chen, Jianer and Huang, Qin and Kanj, Iyad and Xia, Ge},
title = {{NearOptimal Algorithms for PointLine Covering Problems}},
booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
pages = {21:121:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772228},
ISSN = {18688969},
year = {2022},
volume = {219},
editor = {Berenbrink, Petra and Monmege, Benjamin},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15831},
URN = {urn:nbn:de:0030drops158312},
doi = {10.4230/LIPIcs.STACS.2022.21},
annote = {Keywords: line cover, rich lines, exact fitting, kernelization, randomized algorithms, complexity lower bounds, algebraic computation trees}
}
09.03.2022
Keywords: 

line cover, rich lines, exact fitting, kernelization, randomized algorithms, complexity lower bounds, algebraic computation trees 
Seminar: 

39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Issue date: 

2022 
Date of publication: 

09.03.2022 