Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Covering a set of points with a minimum number of lines

Grantson Borgelt, Magdalene LU and Levcopoulos, Christos LU orcid (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:
author
and
organization
publishing date
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
1611-3349
0302-9743
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
2021-08-11 04:42:24
@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         = {1611-3349},
  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},
}