Finding the Minimum Number of Face Guards is NP-Hard

• IWAMOTO Chuzo

  Graduate School of Engineering, Hiroshima University

• KITAGAKI Yusuke

  Graduate School of Engineering, Hiroshima University

• MORITA Kenichi

  Graduate School of Engineering, Hiroshima University

Abstract

We study the complexity of finding the minimum number of face guards which can observe the whole surface of a polyhedral terrain. Here, a face guard is allowed to be placed on the faces of a terrain, and the guard can walk around on the allocated face. It is shown that finding the minimum number of face guards is NP-hard.

Journal

• IEICE Transactions on Information and Systems

  IEICE Transactions on Information and Systems E95.D (11), 2716-2719, 2012

  The Institute of Electronics, Information and Communication Engineers

Keywords

• face guards
• polyhedral terrains
• NP-hard

Details

• CRID: 1390282679355379712
• NII Article ID: 10031142899
• NII Book ID: AA10826272
• DOI: 10.1587/transinf.e95.d.2716
• ISSN: 17451361
• ISSN: 09168532
• Web Site: https://www.jstage.jst.go.jp/article/transinf/E95.D/11/E95.D_2716/_pdf
• Text Lang: en
• Data Source:
  • JaLC
  • Crossref
  • CiNii Articles
  • KAKEN
• Abstract License Flag: Disallowed