Covering a set of points with a minimum number of lines
(2006) 6th Italian Conference, CIAC 2006 3998. p.617 Abstract
 We consider the minimum line covering problem: given a set S of n points in the plane, we want to find the smallest number l of straight lines needed to cover all n points in S. We show that this problem can be solved in O(n log l) time if l is an element of O(log(1is an element of) n), and that this is optimal in the algebraic computation tree model (we show that the Omega(n log l) lower bound holds for all values of l up to O(root n)). Furthermore, a O(log l)factor approximation can be found within the same O(n log I) time bound if l is an element of O((4)root n). For the case when l is an element of Omega(log n) we suggest how to improve the time complexity of the exact algorithm by a factor exponential in l.
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/404292
 author
 Grantson Borgelt, Magdalene ^{LU} and Levcopoulos, Christos ^{LU}
 organization
 publishing date
 2006
 type
 Chapter in Book/Report/Conference proceeding
 publication status
 published
 subject
 host publication
 Lecture Notes in Computer Science (Algorithms and Complexity. Proceedings)
 volume
 3998
 pages
 6  17
 publisher
 Springer
 conference name
 6th Italian Conference, CIAC 2006
 conference location
 Rome, Italy
 conference dates
 20060529  20060531
 external identifiers

 wos:000238119900004
 scopus:33746034919
 ISSN
 16113349
 03029743
 ISBN
 9783540343752
 DOI
 10.1007/11758471
 project
 VR 20054085
 language
 English
 LU publication?
 yes
 id
 15497dcd27df419fb224bc60f04f716c (old id 404292)
 date added to LUP
 20160401 11:42:17
 date last changed
 20210811 04:42:24
@inproceedings{15497dcd27df419fb224bc60f04f716c, abstract = {We consider the minimum line covering problem: given a set S of n points in the plane, we want to find the smallest number l of straight lines needed to cover all n points in S. We show that this problem can be solved in O(n log l) time if l is an element of O(log(1is an element of) n), and that this is optimal in the algebraic computation tree model (we show that the Omega(n log l) lower bound holds for all values of l up to O(root n)). Furthermore, a O(log l)factor approximation can be found within the same O(n log I) time bound if l is an element of O((4)root n). For the case when l is an element of Omega(log n) we suggest how to improve the time complexity of the exact algorithm by a factor exponential in l.}, author = {Grantson Borgelt, Magdalene and Levcopoulos, Christos}, booktitle = {Lecture Notes in Computer Science (Algorithms and Complexity. Proceedings)}, isbn = {9783540343752}, issn = {16113349}, language = {eng}, pages = {617}, publisher = {Springer}, title = {Covering a set of points with a minimum number of lines}, url = {http://dx.doi.org/10.1007/11758471}, doi = {10.1007/11758471}, volume = {3998}, year = {2006}, }