The browser you are using is not supported by this website. All versions of Internet Explorer are no longer supported, either by us or Microsoft (read more here: https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Please use a modern browser to fully experience our website, such as the newest versions of Edge, Chrome, Firefox or Safari etc.

Covering a set of points with a minimum number of lines

Author

Summary, in English

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.

Department/s

  • Computer Science

Publishing year

2006

Language

English

Pages

6-17

Publication/Series

Lecture Notes in Computer Science (Algorithms and Complexity. Proceedings)

Volume

3998

Document type

Conference paper

Publisher

Springer

Topic

  • Computer Science

Conference name

6th Italian Conference, CIAC 2006

Conference date

2006-05-29 - 2006-05-31

Conference place

Rome, Italy

Status

Published

Project

  • VR 2005-4085

ISBN/ISSN/Other

  • ISSN: 0302-9743
  • ISSN: 1611-3349
  • ISBN: 978-3-540-34375-2