야오 그래프

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

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

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

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

• CGAL(Computing Geometric Algorithm Library)의 콘 기반 스패너

참고 항목

• 세타 그래프
• 반야오 그래프

참조