Note on covering monotone orthogonal polygons with star-shaped polygons

Andrzej Lingas, Agnieszka Wasylewicz, Pawel Zylinski

    Forskningsoutput: TidskriftsbidragArtikel i vetenskaplig tidskriftPeer review

    Sammanfattning

    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.
    Originalspråkengelska
    Sidor (från-till)220-227
    TidskriftInformation Processing Letters
    Volym104
    Nummer6
    DOI
    StatusPublished - 2007

    Ämnesklassifikation (UKÄ)

    • Datavetenskap (datalogi)

    Fingeravtryck

    Utforska forskningsämnen för ”Note on covering monotone orthogonal polygons with star-shaped polygons”. Tillsammans bildar de ett unikt fingeravtryck.

    Citera det här