Kreivi Yao

Graafi Yao on eräänlainen geometrinen ulottuva painotettu suuntaamaton graafi , joka yhdistää geometristen pisteiden joukon ominaisuuteen, että minkä tahansa kaavion pisteparin lyhimmän polun pituus ei ylitä niiden euklidista etäisyyttä vakiokertoimella .

Nimetty Andrew Yaon mukaan .

Kuvaus

Kaksiulotteisen Yao-graafin rakentamisen pääideana on ympäröidä jokainen piste tasaisesti jakautuneilla säteillä , jakaa taso sektoreihin, joilla on yhtäläiset kulmat, ja yhdistää jokainen piste sen lähimpiin naapureihin kussakin näistä sektoreista [1] . Yao-graafiin liittyy kokonaislukuparametri , joka on yhtä suuri kuin edellä kuvattu säteiden ja sektoreiden lukumäärä. Suurempi k :n arvo antaa tarkemman approksimation euklidiselle etäisyydelle [2] . Venytyskerroin ei ylitä , missä on yhtä suuri kuin sektorien kulma [3] . Sama idea voidaan laajentaa pistejoukkoon, jonka mitat ovat suurempia kuin kaksi, mutta tarvittavien sektoreiden määrä kasvaa eksponentiaalisesti dimension mukana. $k\geqslant 6$ $1/(\cos \theta -\sin \theta )$ $\theta$

Andrew Yao käytti näitä kaavioita rakentaakseen euklidisia vähimmäisvirittäviä puita suuriulotteisissa tiloissa [3] .

Yao-kaavion piirustusohjelmat

Cone-Based Skeletons in the Computational Geometry Algorithms Library (CGAL) Arkistoitu 27. maaliskuuta 2019 Wayback Machinessa

Katso myös

Theta-kaavio
Poluyov Count

Muistiinpanot

↑ Peittoverkot langattomille järjestelmille . Haettu 27. maaliskuuta 2019. Arkistoitu alkuperäisestä 20. marraskuuta 2021. (määrätön)
↑ Yksinkertaiset topologiat . Haettu 27. maaliskuuta 2019. Arkistoitu alkuperäisestä 20. marraskuuta 2021. (määrätön)
↑ 1 2 Yao, 1982 , s. 721–736.

Kirjallisuus

Vähimmäisvirittävän puiden rakentamisesta k - ulotteisessa avaruudessa ja siihen liittyvistä ongelmista // SIAM Journal on Computing . - 1982. - T. 11 , no. 4 . - doi : 10.1137/0211059 .