Covering a set of points with a minimum number of lines
(2006) 6th Italian Conference, CIAC 2006 3998. p.6-17- 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(1-is 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
- 2006-05-29 - 2006-05-31
- external identifiers
-
- wos:000238119900004
- scopus:33746034919
- ISSN
- 0302-9743
- 1611-3349
- ISBN
- 978-3-540-34375-2
- DOI
- 10.1007/11758471
- project
- VR 2005-4085
- language
- English
- LU publication?
- yes
- id
- 15497dcd-27df-419f-b224-bc60f04f716c (old id 404292)
- date added to LUP
- 2016-04-01 11:42:17
- date last changed
- 2024-10-08 06:41:58
@inproceedings{15497dcd-27df-419f-b224-bc60f04f716c, 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(1-is 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 = {{978-3-540-34375-2}}, issn = {{0302-9743}}, language = {{eng}}, pages = {{6--17}}, 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}}, }