Near-Optimal Algorithms for Point-Line Covering Problems

Kanj, I.; Xia, Ge; Huang, Q.; Chen, J.

Near-Optimal Algorithms for Point-Line Covering Problems

Abstract

We study fundamental point-line 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 3-Points-on-Line problem and the Exact Fitting problem, which – the latter – asks for a line containing the maximum number of points. The second is the NP-hard problem Line Cover, which asks for a set of k lines that cover the points of S, for a given parameter k ∈ N. 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 lower-bound 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 lower-bound 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.

Title	Near-Optimal Algorithms for Point-Line Covering Problems
Creator	Kanj, I.
	Xia, Ge
	Huang, Q.
	Chen, J.
Publisher	39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)
Academic Department	Computer Science
Division	Natural Sciences
Organization	Lafayette College
Date Issued	2022
Date Available	2023-03-23
Type	Article
Language	English
Keyword	exact ftting
	rich lines
	line cover
	algebraic computation trees
	randomized algorithms
	complexity lower bounds
	kernelization
Bibliographic Citation	Chen, J., et al. (2022) "Near-Optimal Algorithms for Point-Line Covering Problems." In Petra Berenbrink and Benjamin Monmege (eds.), 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022) (Article 21). Dagstuhl Publishing.
Standard Identifier	DOI 10.4230/LIPIcs.STACS.2022.21
Standard Identifier	Handle 10385/s7526f233
Permalink	http://hdl.handle.net/10385/s7526f233
Rights Statement	Creative Commons - Attribution
Rights Holders	Chen, J.
	Huang, Q.
	Xia, Ge
	Kanj, I.