Finding the Minimum Number of Open-Edge Guards in an Orthogonal Polygon is NP-Hard

Chuzo IWAMOTO

doi:10.1587/transinf.2016EDL8251

Finding the Minimum Number of Open-Edge Guards in an Orthogonal Polygon is NP-Hard

Chuzo IWAMOTO

Full Text Views

0

Share
Cite this

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

open-edge guards, orthogonal polygons, art gallery problem

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://globals.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 -