抄録/ポイント:
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
平面におけるn点のセットPを考えて,著者らは,質問ユニットディスク(すなわち,すべてのクエリディスクが同じ半径を有する)におけるPのポイントの数を計算する問題を考察した。平面におけるシンプレックス範囲探索のための主な技術をこの問題に適応できることを示した。例えば,Matou対ekの結果により,O(n)空間のデータ構造を構築し,各クエリをO(√n)時間で答えることができる。この技法は,例えば,バッチレンジ探索,単位円の交差対,距離選択,離散2中心等のような,いくつかの他の古典的問題の改善につながり,そして,平面における一組のn単位ディスクと一組のn点を与えて,バッチ範囲探索問題は,その中の点の数を計算する。以前の研究[KatzとSharir,1997]は,O(n ̄4/3logn)時間で問題を解決し,一方,著者らの新しいアルゴリズムはO(n ̄4/3)時間で動作する。【JST・京大機械翻訳】