近接性の問題

近接問題とは、計算幾何学における問題の一種で、幾何学的オブジェクト間の距離を推定する問題である。

これらの問題のうち、点のみで表現されるものは、最近傍点問題と呼ばれることもありますが、^{[ 1 ]}「最近傍点問題」という用語は、最近傍探索と同義語としても使用されます。

これらの問題の多くに共通する特徴は、オブジェクトのセットに対して何らかの最小距離を計算する効率的なアルゴリズムが存在する場合、この距離が 0 に等しいかどうかを確認するのは自明であるという観察に基づき、要素の一意性問題から還元することによって、計算複雑性のΘ ( n log n ) 下限を確立できる可能性があることです。

これらの問題は計算上の複雑さという点では課題とならないものの、幾何学のコンピュータ応用において広く用いられているため、注目に値するものもある。

• 2 つの線分間の距離。点から線までの距離などとは異なり、単一の式で表すことはできません。その計算には、特に 3D 以上の次元では、可能な構成を慎重に列挙する必要があります。^{[ 2 ]}
• バウンディングボックスとは、すべての幾何学的データを含む、軸に沿った最小の超直方体のことである。

• 最も近い点のペア：N個の点が与えられたとき、それらの間の距離が最小となる2つの点を見つける。
• 最近点クエリ／最近傍クエリ：N個の点が与えられたとき、指定されたクエリ点からの距離が最小となる点を見つける。
• すべての最近傍問題（最近傍グラフの構築）：N個の点が与えられたとき、それぞれの点に対して最も近い点を見つける。
• 直径（計算幾何学）：N個の点が与えられたとき、それらの間の距離が最も大きい2つの点を見つける。
• 点集合の幅：N個の点が与えられたとき、それらの間の距離が最小で、かつすべての点がそれらの間に含まれる2つの（超）平面を見つける。
• 点の集合に対する 最小全域木
  • ユークリッド最小全域木
• ドロネー三角形分割
• ボロノイ図
• 最小の包含球：N個の点が与えられたとき、それらすべてを包含する最小の球（円）を見つける。
• 最大の空円：平面上のN個の点が与えられたとき、それらの凸包を中心とし、かつそれらの点を一切含まない最大の円を見つける。
• Smallest enclosing rectangle: unlike the bounding box problem mentioned above, the rectangle may be of any orientation
• Largest empty rectangle
• Geometric spanner, a weighted graph over a set of points as its vertices which for every pair of vertices has a path between them of weight at most 'k' times the spatial distance between these points for a fixed 'k'.

• Shortest path among obstacles
• Distance of closest approach

• Franco P. Preparata and Michael Ian Shamos (1985). Computational Geometry - An Introduction. Springer-Verlag. ISBN 0-387-96131-3. 1st edition: ISBN 0-387-96131-3; 2nd printing, corrected and expanded, 1988: ISBN 3-540-96131-3; Russian translation, 1989: ISBN 5-03-001041-6. The proximity problems are covered in chapters 6 and 7.