近接性の問題
近接問題は、幾何学的オブジェクト間の 距離の推定を伴う計算幾何学における問題の一種です。
点のみで表現されるこれらの問題のサブセットは、最近接点問題と呼ばれることもありますが、[ 1 ]「最近接点問題」という用語は、最近傍探索と同義にも使用されます。
これらの問題の多くに共通する特徴は、オブジェクトのセットに対して何らかの最小距離を計算する効率的なアルゴリズムがあれば、この距離が 0 に等しいかどうかを確認するのは簡単であるという観察に基づいて、要素の一意性の問題から削減することで、計算の複雑さのΘ ( n log n ) 下限を確立できる可能性があることです。
原子力問題
これらの問題は計算の複雑さという点では何ら問題にはなりませんが、幾何学のコンピューターアプリケーションで広く使用されているため、注目に値する問題もあります。
- 線分間の距離。例えば点から直線までの距離とは異なり、単一の式で表すことはできません。特に3次元以上の高次元では、考えられる構成を注意深く列挙する必要があります。[ 2 ]
- 境界ボックス、すべての幾何学的データを含む最小の軸に沿った超長方形
ポイントに関する問題
- 最も近い点のペア: N 個の点が与えられたとき、それらの間の距離が最小となる 2 つの点を見つけます。
- 最近傍点クエリ: N個の点が与えられた場合、指定されたクエリ点までの距離が最小となる点を検索します。
- 全近傍問題（最近傍グラフの構築）：N個の点が与えられたとき、それぞれの点について最も近い点を見つける
- 直径（計算幾何学）：N個の点が与えられたとき、それらの間の距離が最大となる2つの点を見つける
- 点集合の幅：N点が与えられたとき、それらの間の距離が最小で、かつすべての点がその間にある2つの（超）平面を見つける。
- 点集合の 最小全域木
- ドロネー三角形分割
- ボロノイ図
- 最小の囲み球: N 個の点が与えられたとき、それらすべてを囲む最小の球（円）を見つけます。
- 最大の空円:平面上のN点が与えられたとき、それらの凸包を中心とし、それらの点を囲まない最大の円を求める
- 最小の囲み長方形:前述の境界ボックス問題とは異なり、長方形は任意の方向を取ることができる。
- 最大の空の長方形
- 幾何学的スパナは、頂点として点の集合上の重み付きグラフであり、頂点のペアごとに、それらの点間の空間距離の最大 'k' 倍の重みを持つパスが、固定の 'k' に対して存在します。
他の
参考文献
- フランコ・P・プレパラタ、マイケル・イアン・シャモス（1985年）『計算幾何学入門』 Springer -Verlag . ISBN 0-387-96131-3. 第1版: ISBN 0-387-96131-3; 第2刷、訂正・増補、1988年：ISBN 3-540-96131-3; ロシア語訳、1989年：ISBN 5-03-001041-6。近接問題については、第 6 章と第 7 章で説明します。
- ^ JR SackとJ. Urrutia（編）（2000年）『計算幾何学ハンドブック』ノースホランド、ISBN 0-444-82537-1。
{{cite book}}:|author=一般的な名前があります（ヘルプ） - ^ VJ Lumelsky (1985). 「線分間の距離の高速計算について」. Inf. Process. Lett. 21 (2): 55– 61. doi : 10.1016/0020-0190(85)90032-8 .
