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.

Linear-time 3-approximation algorithm for the r-star covering problem

På svenska

Author

Summary, in English

The complexity status of the minimum r-star cover problem for orthogonal polygons had been open for many years, until 2004 when Ch. Worman and J. M. Keil proved it to be polynomially tractable (Polygon decomposition and the orthogonal art gallery problem, IJCGA 17(2) (2007), 105-138). However, since their algorithm has (O) over tilde (n(17))-time complexity, where (O) over tilde (.) hides a polylogarithmic factor, and thus it is not practical, in this paper we present a linear-time 3-approximation algorithm. Our approach is based upon the novel partition of an orthogonal polygon into so-called o-star-shaped orthogonal polygons.

Department/s

  • Computer Science

Publishing year

2012

Language

English

Pages

103-141

Publication/Series

International Journal of Computational Geometry and Applications

Volume

22

Issue

2

Document type

Journal article

Publisher

World Scientific Publishing

Topic

  • Computer Science

Keywords

  • Approximation algorithms
  • r-star cover
  • orthogonal polygon

Status

Published

ISBN/ISSN/Other

  • ISSN: 0218-1959