Grev Yao

Graph Yao  er en type geometrisk spændende , vægtet urettet graf , der forbinder et sæt geometriske punkter med den egenskab, at for ethvert par punkter i grafen har den korteste vej mellem dem en længde, der ikke overstiger deres euklidiske afstand med en konstant faktor .

Opkaldt efter Andrew Yao .

Beskrivelse

Hovedideen med at konstruere en todimensionel Yao-graf er at omgive hvert punkt med jævnt fordelte stråler , opdele planet i sektorer med lige store vinkler og forbinde hvert punkt med dets nærmeste naboer i hver af disse sektorer [1] . En heltalsparameter er forbundet med Yao-grafen , som er lig med antallet af stråler og sektorer beskrevet ovenfor. En større værdi af k giver en mere nøjagtig tilnærmelse til den euklidiske afstand [2] . Strækfaktoren overstiger ikke , hvor er lig med vinklen på sektorerne [3] . Den samme idé kan udvides til sæt af punkter i dimensioner større end to, men antallet af nødvendige sektorer vokser eksponentielt med dimensionen.

Andrew Yao brugte disse grafer til at bygge euklidiske minimumspændende træer i højdimensionelle rum [3] .

Yao graftegneprogrammer

• Keglebaserede skeletter i Computational Geometry Algorithms Library (CGAL) Arkiveret 27. marts 2019 på Wayback Machine

Se også

• Theta graf
• Poluyov Count

Noter

1. ↑ Overlejringsnetværk til trådløse systemer . Hentet 27. marts 2019. Arkiveret fra originalen 20. november 2021. (ubestemt)
2. ↑ Simple topologier . Hentet 27. marts 2019. Arkiveret fra originalen 20. november 2021. (ubestemt)
3. ↑ 1 2 Yao, 1982 , s. 721-736.

Litteratur

• Om konstruktion af minimumsspændende træer i k -dimensionelt rum og relaterede problemer // SIAM Journal on Computing . - 1982. - T. 11 , no. 4 . - doi : 10.1137/0211059 .