| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4949131 | Computational Geometry | 2017 | 26 Pages |
Abstract
In this paper, we answer questions posed by Katz and Morgenstern (2011) by presenting the following results: (i) the MLSC problem is polynomially tractable even for orthogonal polygons with holes, (ii) the MCSC problem is NP-complete when P is allowed to have holes, and (iii) an O(n3logâ¡n)-time 2-approximation algorithm for the MCSC problem on [NE]-star-shaped orthogonal polygons with n vertices (similarly, [NW]-, [SE]-, or [SW]-star-shaped orthogonal polygons).
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Stephane Durocher, Omrit Filtser, Robert Fraser, Ali D. Mehrabi, Saeed Mehrabi,