Du är här

Covering a set of points with a minimum number of lines

Författare:
Publiceringsår: 2006
Språk: Engelska
Sidor: 6-17
Publikation/Tidskrift/Serie: Lecture Notes in Computer Science (Algorithms and Complexity. Proceedings)
Volym: 3998
Dokumenttyp: Konferensbidrag
Förlag: Springer

Sammanfattning

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.

Disputation

Nyckelord

  • Technology and Engineering

Övrigt

6th Italian Conference, CIAC 2006
2006-05-29/2006-05-31
Rome, Italy
Published
  • VR 2005-4085
Yes
  • ISSN: 0302-9743
  • ISBN: 978-3-540-34375-2

Box 117, 221 00 LUND
Telefon 046-222 00 00 (växel)
Telefax 046-222 47 20
lu [at] lu [dot] se

Fakturaadress: Box 188, 221 00 LUND
Organisationsnummer: 202100-3211
Om webbplatsen

LERU logo U21 logo