Note on covering monotone orthogonal polygons with star-shaped polygons
Author
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.
Department/s
- Computer Science
Publishing year
2007
Language
English
Pages
220-227
Publication/Series
Information Processing Letters
Volume
104
Issue
6
Document type
Journal article
Publisher
Elsevier
Topic
- Computer Science
Keywords
- orthogonal polygon
- computational geometry
- covering polygons
Status
Published
Project
- VR 2005-4085
ISBN/ISSN/Other
- ISSN: 0020-0190