Note on covering monotone orthogonal polygons with star-shaped polygons

Andrzej Lingas, Agnieszka Wasylewicz, Pawel Zylinski

    Research output: Contribution to journalArticlepeer-review

    6 Citations (SciVal)

    Abstract

    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.
    Original languageEnglish
    Pages (from-to)220-227
    JournalInformation Processing Letters
    Volume104
    Issue number6
    DOIs
    Publication statusPublished - 2007

    Subject classification (UKÄ)

    • Computer Science

    Keywords

    • orthogonal polygon
    • computational geometry
    • covering polygons

    Fingerprint

    Dive into the research topics of 'Note on covering monotone orthogonal polygons with star-shaped polygons'. Together they form a unique fingerprint.

    Cite this