2024-03-29T04:54:11Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:000317442023-04-27T10:00:04Z01164:02592:02607:02611
凸多角形の点包含判定のための入力感応型最適アルゴリズムAn optimal and input-sensitive algorithm for the point-inclusion problem of a convex polygonjpnhttp://id.nii.ac.jp/1001/00031744/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=31744&item_no=1&attribute_id=1&file_no=1Copyright (c) 2006 by the Information Processing Society of Japan明星大学経済学部仁尾, 都凸多角形P∋質問点を判定する点包含判定問題において、Pの任意の2頂点vs、veの間の境界の長さの2等分点を含む辺と線分vsveのなす角の期待値が0であり、質問点がPの中、あるいはPの内点を中心とする半径が充分大きい円の中のいずれかで一様分布する場合、平均手間がO(1)となる入力感応型最適アルゴリズムを提案する。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.AN1009593X情報処理学会研究報告アルゴリズム(AL)200649(2006-AL-106)65722006-05-182009-06-30