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
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-06-03 17:01:45
@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}},
}