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.

Note on covering monotone orthogonal polygons with star-shaped polygons

In English

Författare

Summary, in English

In 1986, Keil provided an O(n(2)) time algorithm for the problem of covering monotone orthogonal polygons with the minimum number of r-star-shaped orthogonal polygons. This was later improved to O(n) time and space by Gewali et al. in [L. Gewali, M. Keil, S.C. Ntafos, On covering orthogonal polygons with star-shaped polygons, Information Sciences 65 (1992) 45-63]. In this paper we simplify the latter algorithm-we show that with a little modification, the first step SWEEP 1 of the discussed algorithm-which computes the top ceilings of horizontal grid segments an be omitted. In addition, for the minimum orthogonal guard problem in the considered class of polygons, our approach provides a linear time algorithm which uses O(k) additional space, where k is the size of the optimal solution-the algorithm in [L. Gewali, M. Keil, S.C. Ntafos, On covering orthogonal polygons with star-shaped polygons, Information Sciences 65 (1992) 45-63] uses both O(n) time and O(n) additional space. (C) 2007 Elsevier B.V. All rights reserved.

Avdelning/ar

  • Computer Science

Publiceringsår

2007

Språk

Engelska

Sidor

220-227

Publikation/Tidskrift/Serie

Information Processing Letters

Volym

104

Issue

6

Dokumenttyp

Artikel i tidskrift

Förlag

Elsevier

Ämne

  • Computer Science

Nyckelord

  • orthogonal polygon
  • computational geometry
  • covering polygons

Status

Published

Projekt

  • VR 2005-4085

ISBN/ISSN/Övrigt

  • ISSN: 0020-0190