야오 그래프

Yao graph
Yao graph.svg

계산 기하학에서, 앤드류 야오의 이름을 딴 야오 그래프기하학적 스패너의 일종으로, 그래프의 모든 점 쌍에 대해, 그들의 최단 경로유클리드 거리의 일정한 요인 내에 있는 길이를 갖는 특성들과 기하학적 점들의 집합을 연결하는 가중 비방향 그래프다.

2차원 야오 그래프의 기초가 되는 기본 아이디어는 균일한 간격의 광선으로 주어진 각 지점을 둘러싸서 평면을 동일한 각도의 섹터로 분할하고 각 지점을 이 섹터의 가장 가까운 이웃과 연결하는 것이다.[1]야오 그래프와 연관된 정수 매개변수 k ≥ 6은 위에서 설명한 광선과 섹터의 수입니다. k 이 클수록 유클리드 거리에 더 가까운 근사치를 산출한다.[2]확장 계수는 최대 /( \theta - 1 -이며 여기서 섹터의 각이다.[3]동일한 아이디어를 2차원 이상 점 집합까지 확장할 수 있지만, 필요한 섹터의 수는 차원에 따라 기하급수적으로 증가한다.

앤드류 야오는 이 그래프를 사용하여 고차원 유클리드 최소 스패닝 트리를 만들었다.[3]

Yao 그래프 그리기 소프트웨어

참고 항목

참조

  1. ^ "Overlay Networks for Wireless Systems" (PDF).
  2. ^ "Simple Topologies" (PDF).
  3. ^ a b Yao, A. C. (1982), "On constructing minimum spanning trees in k-dimensional space and related problems", SIAM Journal on Computing, 11 (4): 721–736, CiteSeerX 10.1.1.626.3161, doi:10.1137/0211059.