Yao graph

In computational geometry, the Yao graph, named after Andrew Yao, is a kind of geometric spanner, a weighted undirected graph connecting a set of geometric points with the property that, for every pair of points in the graph, their shortest path has a length that is within a constant factor of their Euclidean distance.

The basic idea underlying the two-dimensional Yao graph is to surround each of the given points by equally spaced rays, partitioning the plane into sectors with equal angles, and to connect each point to its nearest neighbor in each of these sectors.^[1] Associated with a Yao graph is an integer parameter $k \geq 6$ which is the number of rays and sectors described above; larger values of $k$ produce closer approximations to the Euclidean distance.^[2] The stretch factor is at most $1/(\cos \theta -\sin \theta )$ , where $\theta$ is the angle of the sectors.^[3] The same idea can be extended to point sets in more than two dimensions, but the number of sectors required grows exponentially with the dimension.

Andrew Yao used these graphs to construct high-dimensional Euclidean minimum spanning trees.^[3]

Software for drawing Yao graphs

Cone-based Spanners in Computational Geometry Algorithms Library (CGAL)

References

^ "Overlay Networks for Wireless Systems" (PDF).
^ "Simple Topologies" (PDF).
^ ^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.

Read other articles:

Glasgow

Pour les articles homonymes, voir Glasgow (homonymie). Glasgow en scots : Glesga en écossais : Glaschu Héraldique Drapeau À partir du haut et de gauche à droite : le Centre scientifique de Glasgow, la Statue équestre du Duc de Wellington et la Galerie d'art moderne, l'Hôtel de ville, Vue de Glasgow, la Royal Exchange Square, la Grue Finnieston et l'Université de Glasgow. Administration Pays Royaume-Uni Nation Écosse Council area Glasgow Ancien comté Lanarkshire Régio...

Judiciary of Louisiana

Politics of Louisiana Constitution and law United States Constitution Louisiana Constitution Louisiana law Executive Governor John Bel Edwards (D) State Cabinet Lieutenant Governor Billy Nungesser (R) Secretary of State Kyle Ardoin (R) Attorney General Jeff Landry (R) State Treasurer John Schroder (R) Commissioner of Agriculture and Forestry Mike Strain (R) Commissioner of Insurance Jim Donelon (R) Public Service Commission Board of Elementary and Secondary Education Legislature State Senate ...

Daftar Bupati Aceh Utara

Kepala PemerintahanKabupaten Aceh UtaraLambang Kabupaten Aceh UtaraPetahanaMahyuzar (Pj)sejak 14 Juli 2023Pemerintah DaerahGelarBupatiKediamanPendopo Bupati Aceh UtaraDibentuk1969Pejabat pertamaTeuku Muda HusinSitus webwww.acehutara.go.id/ Berikut ini adalah Daftar Bupati Aceh Utara dari tahun 1945 dikutip dari buku Aceh Utara: Dari Kerajaan Samudera Pasai ke Era Industrialisasi” yang diterbitkan Pemerintah Aceh Utara tahun 2002. Kabupaten Aceh Utara telah dipimpin 19 bupati sejak tahu...

Ofon Na Edi Asem Fo

2022 single by Daddy LumbaOfon Na Edi Asem FoSingle by Daddy LumbaReleasedDecember 23, 2022GenreHighlifeLength5:36LabelLumba ProductionsSongwriter(s)Charles Kwadwo Fosuh (Daddy Lumba)Producer(s)Daddy Lumba, Kweku Mensah Ofon Na Edi Asem Fo is a song by Ghanaian highlife and afro-pop musician Daddy Lumba, released on December 23, 2022.[1][2][3] Background The song is Daddy Lumba's first project since the release of his 33rd studio album Enko Den in December 2016. It was...

Al Ain

Al Ain العينcityAl AinA view over Green Mubazarrah BenderaCountryUnited Arab EmiratesEmirateAbu DhabiSubdivisions Kotas dan Desa Al JimiAl QattaraAl MuaijiAl MutaredhAl TuwayyaAl FoahAl MasoudiAl KhrairAl old Sarooj Pemerintahan • JenisConstitutional monarchy • SheikhKhalifa bin Zayed Al Nahyan • Crown PrinceMohammed Bin Zayed Bin Sultan Al NahyanPopulasi (2009) • Total374.000Zona waktuUTC+4 (UAE Standard Time) Jabal Hafeet Shahin Al A...

大字 (数字)

この項目には、一部のコンピュータや閲覧ソフトで表示できない文字が含まれています（詳細）。数字の大字（だいじ）は、漢数字の一種。通常用いる単純な字形の漢数字（小字）の代わりに同じ音の別の漢字を用いるものである。概要壱万円日本銀行券（「壱」が大字）弐千円日本銀行券（「弐」が大字）漢数字には「一」「二」「三」と続く小字と、「壱」「�...

Benjamin Constant

Disambiguazione – Se stai cercando altri significati, vedi Benjamin Constant (disambigua). Benjamin ConstantBenjamin Constant Dati generaliTitolo di studioLaurea in lettere ProfessioneScrittoreSaggista Henri-Benjamin Constant de Rebecque (Losanna, 25 ottobre 1767 – Parigi, 8 dicembre 1830) è stato uno scrittore, politico, scienziato politico, nobile ed intellettuale francese di origine svizzera. Indice 1 Biografia 1.1 Primi anni 1.2 Studi tra Erlangen, Edimburgo e Parigi 1.3 S...

In the Cut (film)

2003 film by Jane Campion In the CutTheatrical posterDirected byJane CampionScreenplay by Jane Campion Susanna Moore Based onIn the Cutby Susanna MooreProduced by Nicole Kidman Laurie Parker Starring Meg Ryan Mark Ruffalo Jennifer Jason Leigh Nick Damici Sharrieff Pugh CinematographyDion BeebeEdited byAlexandre de FranceschiMusic byHilmar Örn HilmarssonProductioncompanyPathé Productions LtdDistributed by Screen Gems (through Sony Pictures Releasing;[1] United States) Pathé Distribu...

艾哈迈德·塞古·杜尔

艾哈迈德·塞古·杜尔总统杜尔、代表几内亚共和国在美国马里兰访问华盛顿特区期间抵达安德鲁斯空军基地。 (1982年6月) 第一任几内亚总统任期1958年10月2日—1984年3月26日前任无，职务设立继任路易斯·兰萨纳·贝阿沃吉个人资料出生(1922-01-09)1922年1月9日法兰西第三共和国法属西非法拉纳逝世1984年3月26日(1984歲—03—26)（62歲）美國克利夫兰, 俄亥俄州墓地科奈克里大清�...

اعتلال القرنية السطحي النقطي

اعتلال القرنية السطحي النقطي معلومات عامة الاختصاص طب العيون من أنواع التهاب القرنية والملتحمة تعديل مصدري - تعديل اعتلال القرنية السطحي النقطي لتايغيسون (بالإنجليزية: Thygeson's superficial punctate keratopathy)‏ أحد أمراض العيون. نشر فيليب تايغيسون مقالاً عنه عام 1950 في مجلة الر�...

Live at Montreux 2006

Live at Montreux 2006: They All Came Down to MontreuxLive album by Deep PurpleReleased12 June 2007Recorded15 July 2006 in MontreuxGenreHard rock, heavy metalLength67:33LabelEagleDeep Purple live albums chronology Live in Denmark 1972(2007) Live at Montreux 2006: They All Came Down to Montreux(2007) Live at Montreux 2011(2011) Live at Montreux 2006: They All Came Down to MontreuxVideo by Deep PurpleReleased12 July 2007Recorded15 July 2006 in MontreuxGenreHard rockLength102:14 58:45Lab...

نادي بكاه كيلان

نادي بكاه كيلان الاسم الكامل نادي بكاه كيلان لكرة القدم تأسس عام 5 أغسطس 2002 الملعب ملعب شهيد عضدي دشت رشت، إيران(السعة: 11,000) البلد إيران الدوري دوري المحترفين الإيراني 2007-2008 2007-2008 تعديل مصدري - تعديل نادي بكاه كيلان لكرة القدم (بالفارسية: باشگاه فوتبال پگاه گیلان) ، هي ...

Caterham

Town in Surrey, England For other uses, see Caterham (disambiguation). Human settlement in EnglandCaterhamRoundabout in the centre of Caterham valleyFlagCaterhamLocation within SurreyArea9.41 km2 (3.63 sq mi)Population21,030 (2011 census)[1]• Density2,235/km2 (5,790/sq mi)OS grid referenceTQ3456Civil parishCaterham on the HillCaterham ValleyDistrictTandridgeShire countySurreyRegionSouth EastCountryEnglandSovereign stateUnited Kingdom...

Pemberontakan Dungan (1895–1896)

Untuk pemberontakan tahun 1862–1877, lihat Pemberontakan Dungan (1862–1877). Pemberontakan DunganTanggal1895-1896LokasiQinghai, GansuHasil Kemenangan QingPihak terlibat Kekaisaran Qing, loyalis Khafiya Sufi Pemberontak Muslim, Yihewani, dan pemberontak Khafiya SufiTokoh dan pemimpin Yang ChangjunDong FuxiangBrigadir Jenderal Tang YanheYang ZengxinMa Anliang[1]Ma GuoliangMa FuluMa FuxiangMa HaiyanWei Kuang-tao 魏光燾[2] Ma Yonglin †Ma Dahan †Ma WanfuKekuata...

Australia Cup

Australia's largest national knockout association football competition For other uses, see Australia Cup (disambiguation). Football tournamentAustralia CupOrganising bodyFootball AustraliaFounded24 February 2014; 10 years ago (2014-02-24)Region Australia New ZealandNumber of teams761 (in 2024)Qualifier forAFC Champions League TwoCurrent championsSydney FC(2nd title)Most successful club(s)Adelaide United (3 titles)Television broadcasters Australia: Network 10 Paramo...

سيكو غاساما

سيكو غاساما (باللغات المتعددة: Sekou Gassama Cissokho)‏ معلومات شخصية الميلاد 6 مايو 1995 (29 سنة) جرانوليريس الطول 1.89 م (6 قدم 2 1⁄2 بوصة) مركز اللعب مهاجم الجنسية السنغال إسبانيا أخوة وأخوات مامادو جاساما معلومات النادي النادي الحالي راسينغ سانتاندير(معارًا...

Additive white Gaussian noise

Basic noise model used in information theory This article relies largely or entirely on a single source. Relevant discussion may be found on the talk page. Please help improve this article by introducing citations to additional sources.Find sources: Additive white Gaussian noise – news · newspapers · books · scholar · JSTOR (February 2020) Additive white Gaussian noise (AWGN) is a basic noise model used in information theory to mimic the effect of many...

Khetran

Ethnic group in Balochistan and Pakistan The Khetrans are an ethnolinguistic group primarily native to Barkhan in Balochistan and Dera Ghazi Khan in Punjab, Pakistan. The total population was estimated to be about 150,000 in 2017, at least two-thirds of which are speakers of their native Khetrani, an Indo-Aryan language. A sizeable population in Barkhan can speak Balochi, while Khetrans who have settled to the east in the Dera Ghazi Khan speak Saraiki.[1][2] Origins According...

Kappa Pi

International art honor society Kappa PiΚΠFounded1911; 113 years ago (1911)University of KentuckyTypeHonor societyAffiliationIndependentStatusActiveEmphasisArtScopeInternationalMottoArt Colors Life and Enriches LivingColors Purple and GoldFlowerPurple IrisPublicationThe Sketchbook and SketchPadChapters360Headquarters307 South Fifth AvenueCleveland, Mississippi 38732 United StatesWebsitewww.kappapiart.com[1] Kappa Pi (ΚΠ) International Art Honor Socie...

Plotter

Questa voce o sezione sull'argomento periferiche non cita le fonti necessarie o quelle presenti sono insufficienti. Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti. In informatica il plotter (lett. tracciatore)[1][2][3] è una tipologia di stampante specializzata nella stampa di supporti di grande formato. È il dispositivo di output ideale per i sistemi CAD, dove è impiegato per la stampa di...

PROFILPELAJAR.COM