ストレートウォーカーブル多角形におけるエッジガードについて

• Item type: SIG Technical Reports(1)
• 公開日: 1995-07-20
• タイトル: ストレートウォーカーブル多角形におけるエッジガードについて
• タイトル / 言語: en
• タイトル: Edge Guards in Straight Walkable Polygons
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東海大学開発工学部
• 著者所属(英): en
• 著者所属(英): School of High-Technology for Human Welfare, Tokai University
• 著者名: 譚, 学厚
• 著者名(英): Xuehou, Tan
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本研究ではストレートウォーカーブル多角形におけるエッジガード問題を調べる。この問題は美術館問題の一つの変種である。エッジガードは多角形の辺をパトロールできるガードである。単純多角形Pに頂点sとgが与えられるときに、sとgはPの境界線を二つの輪に分ける。二人のガードが二つの輪に沿ってsからgまで互い見えるようにパトロールすることを考える。パトロールの途中後戻りしないでsからgに到達することができれば、Pをストレートウォーカーブル多角形と言う。例えば、単調多角形と螺旋多角形はストレートウォーカーブル多角形である。本研究ではn頂点のストレートウォーカーブル多角形に対し〓(+)/5〓エッジガードが必要十分であるを証明する。さらに、直交ストレートウォーカーブル多角形に対し〓(+)/6〓エッジガードが必要十分であることも示す。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We study a variation of the art gallery problem with the galleries restricted to straight walkable polygons and with the guards allowed to patrol individual edges of a polygon. Given a simple polygon P with vertices s and g, polygon P is said straight walkable if we can move two points monotonically on two polygonal chains of P from s to g, one clockwise and the other counterclockwise, such that two points are always mutually visible. For instance, monotone polygons and spiral polygons are straight walkable. We show that 〓(n+2)/5〓 edge guards are occasionally necessary and always sufficient to watch an n-vertex gallery of this type. Furthermore, we also that if the given polygon is straight walkable and rectilinear, then 〓(n+3)/6〓 edge guards are necessary and sufficient.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1995, 号 71(1995-AL-046), p. 111-118, 発行日 1995-07-20
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会