Semi-Yao graph

The k-semi-Yao graph (k-SYG) of a set of n objects P is a geometric proximity graph, which was first described to present a kinetic data structure for maintenance of all the nearest neighbors on moving objects.[1] It is named for its relation to the Yao graph, which is named after Andrew Yao.

Construction

The k-SYG is constructed as follows. The space around each point p in P is partitioned into a set of polyhedral cones of opening angle , meaning the angle of each pair of rays inside a polyhedral cone emanating from the apex is at most , and then p connects to k points of P in each of the polyhedral cones whose projections on the cone axis is minimum.

Properties

  • The k-SYG, where k = 1, is known as the theta graph, and is the union of two Delaunay triangulations.[2]
  • For a small and an appropriate cone axis, the k-SYG gives a supergraph of the k-nearest neighbor graph (k-NNG).[3][4] For example, in 2D, if we partition the plane around each point into six wedges of equal angles, and pick the cone axes on directions of the cone bisectors, we obtain a k-SYG as a supergraph for the k-NNG.

See also

References

  1. ^ Rahmati, Zahed (2014). Simple, Faster Kinetic Data Structures (PDF) (Thesis). University of Victoria.
  2. ^ Bonichon, N.; Gavoille, C.; Hanusse, N.; Ilcinkas, D. (2010). "Connections between theta-graphs, Delaunay triangulations, and orthogonal surfaces". Graph Theoretic Concepts in Computer Science. pp. 266–278.
  3. ^ Rahmati, Z.; Abam, M. A.; King, V.; Whitesides, S.; Zarei, A. (2015). "A simple, faster method for kinetic proximity problems". Computational Geometry. 48 (4): 342–359. arXiv:1311.2032. doi:10.1016/j.comgeo.2014.12.002.
  4. ^ Rahmati, Z.; Abam, M. A.; King, V.; Whitesides, S. (2019). "Kinetic k-Semi-Yao Graph and its Applications". Computational Geometry. 77: 10–26. arXiv:1412.5697. doi:10.1016/j.comgeo.2015.11.001.

Read other articles:

Basbousa

BasbousaBasbousa dihiasi dengan kenariJenisHidangan penutupTempat asalMesirDaerahTimur Tengah, Tanduk Afrika, BalkanBahan utamaSemolina atau farina, sirupSunting kotak info • L • BBantuan penggunaan templat ini  Media: Basbousa Basbousa (Turkish: revani or ravanicode: tr is deprecated , bahasa Arab Mesir: بسبوسة) adalah sebuah kue manis Timur Tengah tradisional dan Mesir.[1] Kue tersebut dibuat dari semolina atau farina yang dimasak dan dicampur sirup ...

 

Tennessee

Disambiguazione – Se stai cercando altri significati, vedi Tennessee (disambigua). Tennesseestato federato(EN) State of Tennessee (dettagli) (dettagli) Tennessee – VedutaNashville LocalizzazioneStato Stati Uniti AmministrazioneCapoluogoNashville GovernatoreBill Lee (R) dal 2019 Data di istituzione1º giugno 1796 TerritorioCoordinatedel capoluogo36°10′N 86°47′W / 36.166667°N 86.783333°W36.166667; -86.783333 (Tennessee)Coordinate: 36°10′N 86°...

 

Janet & Jamilah

Janet & JamilahGenre Drama Roman SkenarioAnnisa FitrianiCeritaAnnisa FitrianiSutradaraAnika MaraniPemeran Aisyah Aqilah Pangeran Lantang Fadi Alaydrus Amara Sophie Ratu Rafa Penggubah lagu temaRichard PondaagLagu pembukaBukan Salah Jodoh oleh Adriansyah MartinLagu penutupBukan Salah Jodoh oleh Adriansyah MartinPenata musikSamuel PratamaNegara asalIndonesiaBahasa asliBahasa IndonesiaJmlh. musim1Jmlh. episode33ProduksiProduser eksekutif Monika Rudijono Hermawan Sutanto Eva S. Kurnia ...

Metralindole

Chemical compound MetralindoleClinical dataRoutes ofadministrationOralATC codenoneLegal statusLegal status In general: ℞ (Prescription only) Identifiers IUPAC name 2,4,5,6-tetrahydro-9-methoxy-4-methyl-1H-3,4,6a-triazafluoranthene CAS Number54188-38-4HCl: 53734-79-5 YPubChem CID68713ChemSpider61964UNII2QW3FL6OPAHCl: M15TM76Y3L YCompTox Dashboard (EPA)DTXSID0045705 Chemical and physical dataFormulaC15H17N3OMolar mass255.321 g·mol−13D model (JSmol)Interac...

 

Луганская область

Эта статья — об административной единице Украины. О субъекте Российской Федерации см. Луганская Народная Республика. Регион УкраиныОбластьЛуганская областьукр. Луганська область Флаг Герб 48°55′ с. ш. 39°01′ в. д.HGЯO Страна  Украина Включает 8 районо...

 

وثيقة إعلان قيام دولة إسرائيل

وثيقة إعلان قيام دولة إسرائيل   (بالعبرية: ההכרזה על הקמת מדינת ישראל)‏، و(بالإنجليزية: Declaration of the Establishment of the State of Israel)‏  البلد فلسطين  الموقعون دانيال أستر،  ودافيد ريمز،  وإسحاق بن تسفي،  وإليعازر كابلان،  ومائير فيلنر،  وبنحاس روزن،  ومائير آرغوف،...

Championnat de France de football 2000-2001

Division 12000-2001 Généralités Sport Football Organisateur(s) Ligue Nationale de Football Édition 63e Date du 28 juillet 2000au 19 mai 2001 Participants 18 équipes Site web officiel L’argument http://www.lfp.fr/ligue1/historique/classement.asp?type_classement (valeur &saison=2000/2001) n’existe pas dans le modèle appelé Palmarès Tenant du titre AS Monaco (7) Promu(s) en début de saison Lille OSCEA GuingampToulouse FC Vainqueur FC Nantes (8) Deuxième Olympique lyonn...

 

Thomas Young

Pour les articles homonymes, voir Young et Thomas Young (homonymie). Thomas YoungThomas Young, pionnier de l'optique ondulatoire.BiographieNaissance 13 juin 1773Milverton, Somerset (Royaume-Uni de Grande-Bretagne)Décès 10 mai 1829 (à 55 ans)Londres, Royaume-Uni de Grande-Bretagne et d'IrlandeNationalité BritanniqueDomicile 48, Welbeck Street W1 (d)Formation Université d'ÉdimbourgSt George's, université de LondresUniversité de GöttingenEmmanuel CollegeInstitut universitaire de t...

 

So geht das jede Nacht

Cet article est une ébauche concernant une chanson, le Concours Eurovision de la chanson et l’Allemagne. Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants. So geht das jede Nacht Chanson de Freddy Quinn au Concours Eurovision de la chanson 1956 Sortie 1956 Durée 2:06 Langue Allemand Genre Rock 'n' roll Auteur Peter Mösser (de) Compositeur Lothar Olias (de) Chansons représentant l'Allemagne au C...

Boston–Edison Historic District

Historic district in Michigan, United States United States historic placeBoston–Edison Historic DistrictU.S. National Register of Historic PlacesU.S. Historic districtMichigan State Historic Site Homes on West Boston BoulevardLocationBounded by Edison Ave., Woodward Ave., Linwood Ave., and W. Boston Blvd.Detroit, Michigan, U.S.Coordinates42°22′54″N 83°5′50″W / 42.38167°N 83.09722°W / 42.38167; -83.09722Area256 acres (104 ha)Architectural styleCo...

 

Sekolah negeri (pemerintah)

Sebuah sekolah negeri di Johor, Malaysia. Sekolah Negeri adalah sekolah yang dioperasikan/disediakan oleh pemerintah dengan segala fasilitas gratis, mulai dari kelas hingga guru digaji oleh pemerintah untuk memberikan fasilitas kepada rakyat Indonesia. Di pedesaan, biasanya sekolah negeri begitu banyak diminati karena biaya pendidikan yang relatif terjangkau. Namun pada kenyataan, banyak orang tua memilih sekolah swasta dengan rela mengeluarkan uang SPP yang banyak setiap bulannya hanya untuk...

 

National Institute for Space Research

Brazilian space technology organization This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: National Institute for Space Research – news · newspapers · books · scholar · JSTOR (September 2019) (Learn how and when to remove this message) National Institute for Space ResearchInstituto Nacional de Pesquisas Espacia...

NGC 738

NGC 738 La galaxie lenticulaire NGC 738 Données d’observation(Époque J2000.0) Constellation Triangle Ascension droite (α) 01h 56m 45,7s[1] Déclinaison (δ) 33° 03′ 30″ [1] Magnitude apparente (V) 14,9 [2] 15,9 dans la Bande B[2] Brillance de surface 12,16 mag/am2[2] Dimensions apparentes (V) 0,4′ × 0,2′ [2] Décalage vers le rouge +0,014607 ± 0,000093[1] Angle de position 155°[2] Localisation dans la constellation : Triangle Astrométri...

 

Surah Qaf

Surah ke-50Qaf QafTeks ArabTerjemahan KemenagKlasifikasiMakkiyahNama lainal-Basiqat (Yang Tinggi-Tinggi)JuzJuz 26Jumlah ruku3 rukuJumlah ayat45 ayat Surah Qaf Surah Qaf (Arab: ق, Qaf) adalah surah ke-50 dalam al-Qur'an. Surah ini tergolong surah Makkiyah yang terdiri atas 45 ayat. Dinamakan Qaf karena surah ini dimulai dengan huruf Qaf. Menurut hadits yang diriwayatkan Imam Muslim, bahwa Nabi Muhammad senang membaca surah ini pada raka'at pertama salat subuh dan pada salat hari raya. Sedang ...

 

Coleraine

Town in County Londonderry, Northern Ireland For other uses, see Coleraine (disambiguation). Human settlement in Northern IrelandColeraineIrish: Cúil RaithinScots: Cowlrain or CowlraineColeraine Town HallOpenStreetMap of ColeraineLocation within Northern IrelandPopulation24,483 (2021 Census)[1]Irish grid referenceC844328DistrictCauseway Coast and GlensCountyCounty LondonderryCountryNorthern IrelandSovereign stateUnited KingdomPost townCOLERAINEPostcode distri...

Ahmad Al-Abdullah Al-Sabah

Kuwaiti politician and Prime Minister of Kuwait (born 1952) Ahmad Al-Abdullah Al-Sabahأحمد العبد الله الأحمد الصباحAl Sabah in 2010Prime Minister of KuwaitIncumbentAssumed office 15 May 2024MonarchMishal Al-Ahmad Al-Jaber Al-SabahPreceded byMohammad Sabah Al-Salem Al-SabahMinister of OilIn officeFebruary 2009 – May 2011MonarchSabah Al-Ahmad Al-Jaber Al-SabahPrime MinisterNasser Mohammed Al-Ahmed Al-SabahPreceded byMohammad Al OlaimSucceeded byMohammad A...

 

Mendeleev's predicted elements

Elements predicted to exist but not yet found on the first periodic table Part of a series on thePeriodic tableMendeleev's 1871 periodic table Periodic table forms 18-column 32-column Alternative and extended forms Periodic table history D. Mendeleev 1871 table 1869 predictions Discovery of elements Naming and etymology for people for places controversies (in East Asia) Systematic element names Sets of elements By periodic table structure Groups (1–18) 1 (alkali metals) 2 (al...

 

Capi di governo della Slovacchia

Voce principale: Presidente del Governo della Repubblica Slovacca. Il presidente del Governo della Slovacchia (in slovacco Predseda vlády Slovenskej republiky), conosciuto informalmente come premier (Premiér), è il capo del governo slovacco. Viene nominato dal Presidente della Repubblica ed è responsabile di fronte al Consiglio nazionale (il parlamento unicamerale). Indice 1 Governo provvisorio per la Slovacchia (1918) 2 Repubblica Sovietica Slovacca (1919) 3 Presidenti della terra di Sl...

Erin Gray

Erin Gray nel 2009 Erin Gray (Honolulu, 7 gennaio 1950) è un'attrice statunitense. Indice 1 Biografia 2 Vita privata 3 Filmografia 3.1 Cinema 3.2 Televisione 4 Doppiatrici italiane 5 Note 6 Altri progetti 7 Collegamenti esterni Biografia Ex-modella e ballerina[1][2][3], tra i suoi ruoli più noti figurano quello del colonnello Wilma Deering nella serie televisiva fantascientifica Buck Rogers (1979-1981) e quello di Kate Summers Stratton nella sit-com Il mio amico Rick...

 

Route nationale 6 (Luxembourg)

Pour les articles homonymes, voir N6 et Route nationale 6. Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus. Cet article ne cite pas suffisamment ses sources (octobre 2008). Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références »...