Webbläsaren som du använder stöds inte av denna webbplats. Alla versioner av Internet Explorer stöds inte längre, av oss eller Microsoft (läs mer här: * https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Var god och använd en modern webbläsare för att ta del av denna webbplats, som t.ex. nyaste versioner av Edge, Chrome, Firefox eller Safari osv.

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

In English

Författare

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.

Avdelning/ar

  • Computer Science

Publiceringsår

2012

Språk

Engelska

Sidor

103-141

Publikation/Tidskrift/Serie

International Journal of Computational Geometry and Applications

Volym

22

Issue

2

Dokumenttyp

Artikel i tidskrift

Förlag

World Scientific Publishing

Ämne

  • Computer Science

Nyckelord

  • Approximation algorithms
  • r-star cover
  • orthogonal polygon

Status

Published

ISBN/ISSN/Övrigt

  • ISSN: 0218-1959