가장 가까운 이웃 그래프

Nearest neighbor graph
유클리드 평면에서 100개의 점을 나타내는 가장 가까운 이웃 그래프.

가장 가까운 이웃 그래프(NNG)는 평면의 유클리드 거리와 같은 미터법 공간의 점 집합에 대해 정의된 방향 그래프다.NNG는 각 점에 대한 정점을 가지고 있으며, q가 p의 가장 가까운 이웃일 때마다 p에서 q까지의 방향 에지를 가지고 있으며, p로부터의 거리는 p 그 자체를 제외한 모든 주어진 점 중에서 최소이다.[1]

이러한 그래프의 많은 사용에서 가장자리의 방향은 무시되고 NNG는 대신 비방향 그래프로 정의된다.그러나 가장 가까운 이웃 관계는 대칭 관계가 아니다. 즉, 정의의 p는 반드시 q에 가장 가까운 이웃이 아니다.알고리즘의 이론적 논의에서 흔히 일반적인 위치의 일종, 즉 가장 가까운 (k-near) 이웃은 각 물체에 대해 고유하다고 가정한다.알고리즘의 구현에서는 이것이 항상 그렇지는 않다는 것을 명심할 필요가 있다.각 물체에 대해 가장 가까운 이웃을 고유하게 만들 필요가 있는 상황의 경우, 설정된 P를 인덱싱할 수 있으며, 예를 들어 가장 큰 인덱스를 가장 가까운 이웃으로 가져갈 수 있다.[2]

k-가장 가까운 이웃 그래프(k-NNG)는 p와 q 사이의 거리가 p에서 다른 물체까지의 k-th 최소 거리 중 하나일 경우 두 개의 꼭지점 p와 q가 에지로 연결된 그래프다.NNG는 k-NNG의 특별한 경우로서, 즉 1-NNG이다. k-NNG는 분리기 정리를 따른다. 분리기 정리를 따른다: O(kn1/d1 − 1/d) 점을 제거하여 각각 최대 n(d + 1)/(d + 2) 정점 2개로 분할할 수 있다.[3]

또 다른 변화는 가장 가까운 점 대신 가장 먼 점으로 각 점이 가장 먼 점으로 연결되는 가장 먼 이웃 그래프(FNG)이다.

평면과 다차원 공간의 점들에 대한 NNG는 예를 들어 데이터 압축, 동작 계획 및 설비 위치 등에서 응용 프로그램을 찾는다.통계 분석에서 이 그래프의 다음 경로에 기초한 가장 가까운 이웃사슬 알고리즘을 사용하여 계층적 군집을 신속하게 찾을 수 있다.가장 가까운 이웃 그래프도 계산 기하학의 주제다.

이 방법을 사용하여 연결 상태를 알 수 없는 노드에서 그래프를 유도할 수 있다.

점 집합에 대한 NNG

1차원 케이스

선의 점 집합의 경우 점의 가장 가까운 이웃은 선을 따라 정렬된 경우 점의 왼쪽 또는 오른쪽(또는 둘 다) 인접이다.따라서 NNG는 여러 경로의 경로 또는 숲이며, 정렬을 통해 O(n log n) 시간에 생성될 수 있다.생성된 NNG는 소자 고유성 문제에 대한 해답을 주기 때문에 이 추정치는 특정 연산 모델에 대해 점증적으로 최적이다. NNG의 에지가 0-길이인지 여부를 확인하는 데 충분하다.[4]

상위 치수

달리 명시되지 않는 한, NNG는 서문에 기술된 바와 같이 가장 가까운 이웃이 고유하게 정의된 디그람이라고 가정한다.

  1. NNG에서 지시된 경로를 따라 에지 길이는 증가하지 않는다.[2]
  2. 길이 2의 사이클만 NNG에서 가능하며, 최소 2개의 정점을 가진 NNG의 약하게 연결된 각 구성요소는 정확히 하나의 2 사이클을 가진다.[2]
  3. 평면의 점에 대해 NNG는 정점도가 최대 6인 평면 그래프다.포인트가 일반적 위치에 있다면 그 정도는 최대 5이다.[2]
  4. 평면이나 그 이상의 치수에서 점 집합의 NNG(가장 가까운 이웃이 여러 개 허용되는 비방향 그래프로 처리됨)는 딜라우나이 삼각측량, 가브리엘 그래프, 세미야오 그래프의 하위 그래프다.[5]포인트가 일반 위치에 있거나 가장 가까운 단일 인접 조건이 부과되는 경우, NNG는 유클리드 최소 스패닝 트리의 하위 그래프인 숲이다.

참조

  1. ^ Franco P. Preparata and Michael Ian Shamos (1985). Computational Geometry - An Introduction. Springer-Verlag. ISBN 0-387-96131-3. 1st edition; 2nd printing, corrected and expanded, 1988; Russian translation, 1989.
  2. ^ a b c d Eppstein, D.; Paterson, M. S.; Yao, Frances (1997). "On nearest-neighbor graphs". Discrete and Computational Geometry. 17 (3): 263–282. doi:10.1007/PL00009293.
  3. ^ Miller, Gary L.; Teng, Shang-Hua; Thurston, William; Vavasis, Stephen A. (1997). "Separators for sphere-packings and nearest neighbor graphs". Journal of the Association for Computing Machinery. 44 (1): 1–29. doi:10.1145/256292.256294.
  4. ^ Aggarwal, Alok; Kipnis, Shlomo (August 1988). "Lecture #10, March 10, 1988: Closest pair". In Aggarwal, Alok; Wein, Joel (eds.). Computational Geometry: Lecture Notes for 18.409, Spring 1988. Massachusetts Institute of Technology Laboratory for Computer Science. Observation 1, p. 2.
  5. ^ Rahmati, Z.; King, V.; Whitesides, S. (2013). Kinetic data structures for all nearest neighbors and closest pair in the plane. Proceedings of the 29th ACM Symposium on Computational Geometry. pp. 137–144. doi:10.1145/2462356.2462378.