Advanced

Note on covering monotone orthogonal polygons with star-shaped polygons

Lingas, Andrzej LU ; Wasylewicz, Agnieszka and Zylinski, Pawel (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:
author
organization
publishing date
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
2007-12-13 08:02:25
date last changed
2017-02-12 04:07:20
@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},
  keyword      = {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},
  volume       = {104},
  year         = {2007},
}