凸多角形の点包含判定のための入力感応型最適アルゴリズム

• Item type: SIG Technical Reports(1)
• 公開日: 2006-05-18
• タイトル: 凸多角形の点包含判定のための入力感応型最適アルゴリズム
• タイトル / 言語: en
• タイトル: An optimal and input-sensitive algorithm for the point-inclusion problem of a convex polygon
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 明星大学経済学部
• 著者所属(英): en
• 著者所属(英): School of Economics, Meisei University
• 著者名: 仁尾, 都
• 著者名(英): Misato, Nio
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 凸多角形Ｐ∋質問点を判定する点包含判定問題において、Ｐの任意の２頂点ｖｓ、ｖｅの間の境界の長さの２等分点を含む辺と線分ｖｓｖｅのなす角の期待値が０であり、質問点がＰの中、あるいはＰの内点を中心とする半径が充分大きい円の中のいずれかで一様分布する場合、平均手間がＯ（１）となる入力感応型最適アルゴリズムを提案する。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: For the point-inclusion problem whether a convex polygon P includes a question point q or not, we propose an optimal and input-sensitive algorithm such that its computing time is O(log|P|) and especially O(1) on the average if the mean of the angles of the vectors vsve and vcvc+1 is 0, and q is distributed uniformly in P or in a circle whose center is in P and whose radius is large enough, where vs and ve are vertexes and vcvc+1 includes the middle point of the length of boundary of P between vs and ve.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2006, 号 49(2006-AL-106), p. 65-72, 発行日 2006-05-18
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会