근접성 문제
Proximity problems근접 문제는 기하학적 물체들 사이의 거리 추정을 포함하는 계산 기하학적 기하학의 문제의 한 종류다.
"가장 근접한 점 문제"라는 용어는 가장 가까운 이웃을 찾는 것과 동의어로도 사용되지만,[1] 점으로만 언급된 이러한 문제의 일부분을 가장 가까운 점 문제로 언급하기도 한다.
이러한 많은 문제의 공통적인 특성은 개체 집합에 대해 어떤 종류의 최소 거리를 계산하는 효율적인 알고리즘이 있다면, 이 알고리즘을 확인하는 것은 사소한 일이라는 관찰에 기초하여 요소 고유성 문제로부터 감소시킴으로써 계산 복잡성에 대한 θ(n log n)을 확립할 수 있는 가능성이다.자세는 0과 같다.
원자 문제
이러한 문제들은 계산상의 복잡성 문제를 일으키지 않지만, 그들 중 일부는 기하학의 컴퓨터 어플리케이션에서의 편재성 때문에 눈에 띈다.
- 선 세그먼트 쌍 사이의 거리.예를 들어, 점에서 선까지의 거리와는 달리, 하나의 공식으로 표현할 수 없다.그 계산은 특히 3D 이상의 치수에서 가능한 구성을 신중하게 열거해야 한다.[2]
- 모든 기하학적 데이터를 포함하는 최소 축 정렬 하이퍼 직각인 경계 상자
포인트 문제
- 가장 가까운 점 쌍: N개의 점이 주어진 경우, 둘 사이의 거리가 가장 작은 두 점을 찾으십시오.
- 가장 근접한 점 쿼리 / 가장 가까운 인접 점 쿼리: 지정된 N개의 점, 지정된 쿼리 점까지의 거리가 가장 작은 점을 찾으십시오.
- 모든 가장 가까운 이웃 문제(가장 가까운 이웃 그래프 구성):N개의 점이 주어진 경우, 각 점에 대해 가장 가까운 점을 찾으십시오.
- 점 집합의 지름: N개의 점이 주어진 경우, 둘 사이의 거리가 가장 큰 두 개를 찾으십시오.
- 점 집합의 너비: N개의 점이 주어진 경우, 거리가 가장 작고 모든 점이 있는 두 개의 (하이퍼) 평면을 찾으십시오.
- 점 집합에 대한 최소 스패닝 트리
- 델라우나이 삼각측량
- 보로노이 다이어그램
- 가장 작은 범위 구: N개의 점이 주어진 경우, 모든 점을 둘러싸는 가장 작은 구(원)를 찾으십시오.
- 가장 큰 빈 원: 평면에 N개의 포인트가 주어지면 볼록한 선체 내에서 가장 큰 원을 찾아 그 중 어느 것도 감싸지 마십시오.
- 가장 작은 둘러싸인 직사각형: 위에서 언급한 경계 상자 문제와 달리 직사각형은 어떤 방향으로도 될 수 있다.
- 비어 있는 가장 큰 직사각형
- 기하학적 스패너(Geomical Spanner), 정점 쌍에 대해 최대 'k'배 무게의 경로를 갖는 정점 집합에 대한 가중 그래프. 고정된 'k'에 대해 이들 점 사이의 공간 거리를 최대 'k' 곱한 값으로 한다.
기타
참조
- 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. 근접성 문제는 6장과 7장에서 다룬다.
- ^ J. R. Sack and J. Urrutia (eds.) (2000). Handbook of Computational Geometry. North Holland. ISBN 0-444-82537-1.
{{cite book}}:author=일반 이름 포함(도움말) - ^ V. J. Lumelsky (1985). "On fast computation of distance between line segments". Inf. Process. Lett. 21 (2): 55–61. doi:10.1016/0020-0190(85)90032-8.
