文献

J-GLOBAL ID：202002265455367928   整理番号：20A0769530

最適ARTギャラリー位置決めはNP困難である【JST・京大機械翻訳】

Optimal Art Gallery Localization is NP-hard

著者 (4件)： Bose Prosenjit (School of Computer Science, Carleton University, Ottawa, Canada) ,  De Carufel Jean-Lou (School of Electrical Engineering and Computer Science, U. of Ottawa, Canada) ,  Shaikhet Alina (School of Computer Science, Carleton University, Ottawa, Canada) ,  Smid Michiel (School of Computer Science, Carleton University, Ottawa, Canada)
資料名： Computational Geometry: Theory and Applications  (Computational Geometry: Theory and Applications)
巻： 88  ページ： Null  発行年： 2020年 
JST資料番号： W0536A  ISSN： 0925-7721  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 最新のGallery Localization(AGL)は,内部にそれ自身を位置決めするために,簡単な多角形Pにおけるブロードキャスト塔のセットTを配置する問題である。任意の点p∈Pに対して,各タワーt∈T ∩V(p)(V(p)はpの可視性多角形を示す)に対して,点pはtとpの間のユークリッド距離の座標を受け取り,この情報からpはその座標を決定することができる。AGL問題の計算複雑性を研究した。著者らは,簡単な多角形Pにおいてどこでも点を局在化できる最小数のブロードキャスト塔を決定する問題がNP困難であることを示した。著者らは,Boole3充足可能性問題から著者らの問題への縮小を示して,この減少が多項式時間を取るという証明を与えた。Copyright 2020 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 位置決め ,  計算量 ,  塔状構造物 ,  可視度 ,  *NP困難 ,  GPS ,  充足可能性問題 ,  ブロードキャスト
準シソーラス用語： 多項式時間 ,  局在化 ,  Euclid距離 ,  *ギャラリ , 【Automatic Indexing@JST】

著者キーワード (5件)： 美術館 ,  三層化 ,  GPS ,  多角形分割 ,  位置決め

分類 (2件)： グラフ理論基礎  (IA02020S) ,  その他のオペレーションズリサーチの手法  (KA03070E)

タイトルに関連する用語 (3件)： ART ,  ギャラリー ,  NP困難