IEICE TRANSACTIONS on Information
Finding the Minimum Number of Open-Edge Guards in an Orthogonal Polygon is NP-Hard
Summary :
We study the problem of determining the minimum number of open-edge guards which guard the interior of a given orthogonal polygon with holes. Here, an open-edge guard is a guard which is allowed to be placed along open edges of a polygon, that is, the endpoints of the edge are not taken into account for visibility purpose. It is shown that finding the minimum number of open-edge guards for a given orthogonal polygon with holes is NP-hard.
- Publication
- IEICE TRANSACTIONS on Information Vol.E100-D No.7 pp.1521-1525
- Publication Date
- 2017/07/01
- Publicized
- 2017/04/05
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.2016EDL8251
- Type of Manuscript
- LETTER
- Category
- Fundamentals of Information Systems
Authors
Chuzo IWAMOTO
Hiroshima University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Chuzo IWAMOTO, "Finding the Minimum Number of Open-Edge Guards in an Orthogonal Polygon is NP-Hard" in IEICE TRANSACTIONS on Information,
vol. E100-D, no. 7, pp. 1521-1525, July 2017, doi: 10.1587/transinf.2016EDL8251.
Abstract: We study the problem of determining the minimum number of open-edge guards which guard the interior of a given orthogonal polygon with holes. Here, an open-edge guard is a guard which is allowed to be placed along open edges of a polygon, that is, the endpoints of the edge are not taken into account for visibility purpose. It is shown that finding the minimum number of open-edge guards for a given orthogonal polygon with holes is NP-hard.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2016EDL8251/_p
Copy
@ARTICLE{e100-d_7_1521,
author={Chuzo IWAMOTO, },
journal={IEICE TRANSACTIONS on Information},
title={Finding the Minimum Number of Open-Edge Guards in an Orthogonal Polygon is NP-Hard},
year={2017},
volume={E100-D},
number={7},
pages={1521-1525},
abstract={We study the problem of determining the minimum number of open-edge guards which guard the interior of a given orthogonal polygon with holes. Here, an open-edge guard is a guard which is allowed to be placed along open edges of a polygon, that is, the endpoints of the edge are not taken into account for visibility purpose. It is shown that finding the minimum number of open-edge guards for a given orthogonal polygon with holes is NP-hard.},
keywords={},
doi={10.1587/transinf.2016EDL8251},
ISSN={1745-1361},
month={July},}
Copy
TY - JOUR
TI - Finding the Minimum Number of Open-Edge Guards in an Orthogonal Polygon is NP-Hard
T2 - IEICE TRANSACTIONS on Information
SP - 1521
EP - 1525
AU - Chuzo IWAMOTO
PY - 2017
DO - 10.1587/transinf.2016EDL8251
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E100-D
IS - 7
JA - IEICE TRANSACTIONS on Information
Y1 - July 2017
AB - We study the problem of determining the minimum number of open-edge guards which guard the interior of a given orthogonal polygon with holes. Here, an open-edge guard is a guard which is allowed to be placed along open edges of a polygon, that is, the endpoints of the edge are not taken into account for visibility purpose. It is shown that finding the minimum number of open-edge guards for a given orthogonal polygon with holes is NP-hard.
ER -
English
