ユニットディスクレンジ探索と応用【JST・京大機械翻訳】

Wang Haitao

プレプリント

J-GLOBAL ID：202202212089420689 整理番号：22P0334280

ユニットディスクレンジ探索と応用【JST・京大機械翻訳】

Unit-Disk Range Searching and Applications

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで

この文献はプレプリントです。プレプリントについてはこちらをご確認ください。

著者 (1件)：
資料名：
発行年： 2022年04月19日プレプリントサーバーでの情報更新日： 2022年04月19日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

平面におけるn点のセットPを考えて,著者らは,質問ユニットディスク(すなわち,すべてのクエリディスクが同じ半径を有する)におけるPのポイントの数を計算する問題を考察した。平面におけるシンプレックス範囲探索のための主な技術をこの問題に適応できることを示した。例えば,Matou対ekの結果により,O(n)空間のデータ構造を構築し,各クエリをO(√n)時間で答えることができる。この技法は,例えば,バッチレンジ探索,単位円の交差対,距離選択,離散2中心等のような,いくつかの他の古典的問題の改善につながり,そして,平面における一組のn単位ディスクと一組のn点を与えて,バッチ範囲探索問題は,その中の点の数を計算する。以前の研究[KatzとSharir,1997]は,O(n ̄4/3logn)時間で問題を解決し,一方,著者らの新しいアルゴリズムはO(n ̄4/3)時間で動作する。【JST・京大機械翻訳】

, , ,
, 【Automatic Indexing@JST】

その他のオペレーションズリサーチの手法 , 人工知能 , 図形・画像処理一般

前のページに戻る