Note on covering monotone orthogonal polygons with star-shaped polygons
(2007) In Information Processing Letters 104(6). p.220-227- 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... (More)
- 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. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/654043
- author
- Lingas, Andrzej LU ; Wasylewicz, Agnieszka and Zylinski, Pawel
- organization
- publishing date
- 2007
- type
- Contribution to journal
- publication status
- published
- subject
- keywords
- orthogonal polygon, computational geometry, covering polygons
- in
- Information Processing Letters
- volume
- 104
- issue
- 6
- pages
- 220 - 227
- publisher
- Elsevier
- external identifiers
-
- wos:000250315500006
- scopus:34548437350
- ISSN
- 0020-0190
- DOI
- 10.1016/j.ipl.2007.06.015
- project
- VR 2005-4085
- language
- English
- LU publication?
- yes
- id
- e911f4f3-b227-41a3-bcd5-a385e5104a52 (old id 654043)
- date added to LUP
- 2016-04-01 16:11:58
- date last changed
- 2022-01-28 18:01:19
@article{e911f4f3-b227-41a3-bcd5-a385e5104a52,
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.}},
author = {{Lingas, Andrzej and Wasylewicz, Agnieszka and Zylinski, Pawel}},
issn = {{0020-0190}},
keywords = {{orthogonal polygon; computational geometry; covering polygons}},
language = {{eng}},
number = {{6}},
pages = {{220--227}},
publisher = {{Elsevier}},
series = {{Information Processing Letters}},
title = {{Note on covering monotone orthogonal polygons with star-shaped polygons}},
url = {{http://dx.doi.org/10.1016/j.ipl.2007.06.015}},
doi = {{10.1016/j.ipl.2007.06.015}},
volume = {{104}},
year = {{2007}},
}