Граф відносних околів

Граф відносних околів 100 випадкових точок у одиничному квадраті.

Граф відно́сних о́колів — це неорієнтований граф, визначений на множині точок на евклідовій площині з'єднанням двох точок p і q ребом тоді, коли не існує третьої точки r, яка ближче як до p, так і до q, ніж p і q одна до одної. Цей граф 1980 року запропонував Годфрід Туссен[en] як спосіб визначення на множині точок структури, яка відбиває людське сприйняття форми множини[1][2][3].

Алгоритми

Суповіт[4] показав, як ефективно побудувати граф відносних околів за час O(n log n)[5]. Граф можна обчислити за середній час O (n) для довільної множини точок, рівномірно розподілених у одиничному квадраті[6]. Граф відносних околів можна обчислити за лінійний час із тріангуляції Делоне множини точок[7][8].

Узагальнення

Оскільки граф визначений лише в термінах відстаней між точками, граф відносних околів можна визначити для множин точок у просторі будь-якої розмірності[1][9] і для неевклідових метрик[1][7][10][11].

Пов'язані графи

Граф відносних околsв є прикладом заснованого на лінзах[en] бета-кістяка. Це підграф тріангуляції Делоне. У свою чергу, евклідове мінімальне кістякове дерево є його підграфом, звідки випливає, що це зв'язний граф.

Граф Уркгарта, утворений видаленням найдовшого ребра з кожного трикутника в тріангуляції Делоне, спочатку запропоновано як швидкий метод обчислення графа відносних околів[12]. Хоча граф Уркхарта іноді відрізняється від графа відносних околів[13], його можна використати як апроксимацію графа відносних околів[14].

Примітки

  1. ↑ а б в Jaromczyk, Kowaluk, 1991, с. 181–191.
  2. ↑ Toussaint, 1980, с. 261–268.
  3. ↑ Jaromczyk, Toussaint, 1992, с. 1502–1517.
  4. ↑ Supowit, 1983.
  5. ↑ Supowit, 1983, с. 428–448.
  6. ↑ Katajainen, Nevalainen, Teuhola, 1987, с. 77–86.
  7. ↑ а б Jaromczyk, Kowaluk, 1987, с. 233–241.
  8. ↑ Lingas, 1994, с. 199–208.
  9. ↑ Agarwal, Matoušek, 1992, с. 58–65.
  10. ↑ O'Rourke, 1982, с. 189–192.
  11. ↑ Lee, 1985, с. 327–332.
  12. ↑ Urquhart, 1980, с. 556–557.
  13. ↑ Toussaint, 1980, с. 860.
  14. ↑ Andrade, de Figueiredo, 2001.

Література

  • Toussaint G. T. The relative neighborhood graph of a finite planar set // Pattern Recognition. — 1980. — Т. 12, вип. 4. — С. 261–268. — DOI:10.1016/0031-3203(80)90066-7.
  • Jaromczyk J.W., Toussaint G.T. Relative neighborhood graphs and their relatives // Proceedings of the IEEE. — 1992. — Т. 80, вип. 9. — С. 1502–1517. — DOI:10.1109/5.163414.
  • Supowit K. J. The relative neighborhood graph, with an application to minimum spanning trees // J. ACM. — 1983. — Т. 30, вип. 3. — С. 428–448. — DOI:10.1145/2402.322386.
  • Jyrki Katajainen, Olli Nevalainen, Jukka Teuhola. A linear expected-time algorithm for computing planar relative neighbourhood graphs // Information Processing Letters. — 1987. — Т. 25, вип. 2. — С. 77–86. — DOI:10.1016/0020-0190(87)90225-0.
  • Jaromczyk J. W., Kowaluk M. A note on relative neighborhood graphs // Proc. 3rd Symp. Computational Geometry. — New York, NY, USA : ACM, 1987. — С. 233–241. — DOI:10.1145/41958.41983.
  • Lingas A. A linear-time construction of the relative neighborhood graph from the Delaunay triangulation // Computational Geometry. — 1994. — Т. 4, вип. 4. — С. 199–208. — DOI:10.1016/0925-7721(94)90018-3.
  • Jaromczyk J. W., Kowaluk M. Constructing the relative neighborhood graph in 3-dimensional Euclidean space // Discrete Appl. Math.. — 1991. — Т. 31, вип. 2. — С. 181–191. — DOI:10.1016/0166-218X(91)90069-9.
  • Pankaj K. Agarwal, Jiří Matoušek. Relative neighborhood graphs in three dimensions // Proc. 3rd ACM–SIAM Symp. Discrete Algorithms. — 1992. — С. 58–65.
  • O'Rourke J. Computing the relative neighborhood graph in the L1 and L∞ metrics // Pattern Recognition. — 1982. — Т. 15, вип. 3. — С. 189–192. — DOI:10.1016/0031-3203(82)90070-X.
  • Lee D. T. Relative neighborhood graphs in the L1-metric // Pattern Recognition. — 1985. — Т. 18, вип. 5. — С. 327–332. — DOI:10.1016/0031-3203(85)90023-8.
  • Urquhart R. B. Algorithms for computation of relative neighborhood graph // Electronics Letters. — 1980. — Т. 16, вип. 14. — С. 556–557. — DOI:10.1049/el:19800386.
  • Toussaint G. T. Comment: Algorithms for computing relative neighborhood graph // Electronics Letters. — 1980. — Т. 16, вип. 22. — С. 860. — DOI:10.1049/el:19800611.
  • Diogo Vieira Andrade, Luiz Henrique de Figueiredo. Good approximations for the relative neighbourhood graph // Proc. 13th Canadian Conference on Computational Geometry. — 2001.

Read other articles:

Pagi-Pagi Ambyar

Pagi-Pagi AmbyarGenreGelar wicaraPresenterNassarDewi PersikCaren DelanoRian IbramNegara asalIndonesiaBahasa asliBahasa IndonesiaProduksiDurasi90 menit (Senin-Jumat)Rumah produksiTrans TVDistributorTrans MediaRilis asliJaringanTrans TVFormat gambarDolby Digital HD 16:9Format audioStereoDolby Digital 5.1Rilis19 Oktober 2020 (2020-10-19) –sekarangAcara terkaitPagi-Pagi Pasti HappyBrownisSore-Sore AmbyarRamadan Itu BerkahKetawa Itu BerkahSweet DaddyBukan Bisik-Bisik (di Trans7) Pagi-...

 

 

RC Celta de Vigo

Celta VigoNama lengkap Real Club Celta de Vigo, S.A.D.JulukanLos Celestes (Biru langit)Los Celtiñas (The Lovely/Little Celts)Berdiri23 Agustus 1923; 100 tahun lalu (1923-08-23)StadionBalaídos(Kapasitas: 32.500)PemilikGrupo Corporativo Ges, S.L.Presiden Carlos MouriñoLigaLa Liga2022–2023La Liga, ke-13 dari 20Situs webSitus web resmi klub Kostum kandang Musim ini Real Club Celta de Vigo, atau biasa dikenal dengan nama Celta Vigo, atau hanya Celta, adalah sebuah tim sepak bola Spa...

 

 

WrestleMania XXVI

WrestleMania XXVI Poster menampilkan (dari kiri ke kanan) Shawn Michaels, Triple H, John Cena, The Undertaker dan Batista Tema Destruction in the Desert Get All Fired Up. Lagu Tema I Made It (Cash Money Heroes) oleh Kevin Rudolf feat. Birdman, Jay Sean dan Lil Wayne Thunderstruck oleh AC/DC Be Yourself oleh Audioslave The Show oleh Since October Detail Promosi WWE Tanggal 28 Maret, 2010 Tempat Stadion Universitas Phoenix Kota Glendale, Arizona Kehadiran 72,219 Kronologi Bayar-Per-Tayang Elim...

KMXR

Radio station in Corpus Christi, TexasKMXRCorpus Christi, TexasBroadcast areaCorpus Christi metropolitan areaFrequency93.9 MHzBrandingBig 93.9ProgrammingFormatClassic hitsAffiliationsPremiere NetworksOwnershipOwneriHeartMedia(iHM Licenses, LLC)Sister stationsKKTX, KNCN, KRYS-FM, KSAB, KUNOHistoryFirst air dateJanuary 1970; 54 years ago (1970-01)Former call signsKSIX-FM (1970–1980)KEXX (1980–1985)KSTE (1985–1989)Technical informationFacility ID55163ClassC1ERP100,00...

 

 

Monasteries on the slopes of Popocatépetl

Historic site in Areas south and east of Popocatépetl, MexicoEarliest monasteries on the slopes of PopocatépetlView of the church façade of the monastery in TepoztlánLocationAreas south and east of Popocatépetl, MexicoBuilt16th CenturyBuilt forThe Augustinians, the Franciscans and the Dominicans UNESCO World Heritage SiteTypeCulturalCriteriaii, ivDesignated1994 (18th session)Reference no.702RegionLatin America and the Caribbean The Earliest Monasteries on the Slopes of Popocatepetl ...

 

 

Ritus Romawi

Altar gereja Santa Cecilia in Trastevere di Roma, tahun 1700 Ritus Romawi atau Ritus Roma merupakan istilah ritus liturgis dari Gereja Roma. Istilah Ritus Latin biasanya bukan diartikan sebagai suatu ritus liturgis melainkan sebagai Gereja Partikular dalam Gereja Katolik yang kadang-kadang disebut pula sebagai Patriarkat Barat, yang di dalamnya terdapat ritus-ritus liturgis selain Ritus Roma yang masih digunakan sampai sekarang. Sebagaimana ritus-ritus liturgis lainnya, Ritus Roma telah berke...

SNRPG

Protein-coding gene in the species Homo sapiens SNRPGAvailable structuresPDBHuman UniProt search: PDBe RCSB List of PDB id codes3CW1, 3PGW, 3S6N, 4F7U, 4PJO, 4V98, 4WZJ, 3JCRIdentifiersAliasesSNRPG, SMG, Sm-G, small nuclear ribonucleoprotein polypeptide GExternal IDsOMIM: 603542 HomoloGene: 37730 GeneCards: SNRPG Gene location (Human)Chr.Chromosome 2 (human)[1]Band2p13.3Start70,281,362 bp[1]End70,293,740 bp[1]RNA expression patternBgeeHumanMouse (ortholog)Top expressed...

 

 

克莱门特·艾德礼

艾德礼伯爵 阁下The Rt Hon. The Earl AttleeKG OM CH PC FRS联合王国首相任期1945年7月26日—1951年10月26日君主乔治六世副职赫伯特·莫里森前任温斯顿·丘吉尔继任温斯顿·丘吉尔联合王国副首相任期1942年2月19日—1945年5月23日（战时内阁）君主乔治六世首相温斯顿·丘吉尔前任职位创立继任赫伯特·莫里森反对党领袖任期1951年10月26日—1955年11月25日君主乔治六世伊丽莎白二�...

 

 

History of taxation in the United Kingdom

James Gilray: The Friend of the People; & his Petty New Tax Gatherer paying John Bull a visit (1806) The history of taxation in the United Kingdom includes the history of all collections by governments under law, in money or in kind, including collections by monarchs and lesser feudal lords, levied on persons or property subject to the government, with the primary purpose of raising revenue. Background Main article: Taxation in medieval England Prior to the formation of the Kingdom of Gr...

Network-attached storage

Computer data storage server Not to be confused with storage area network or network access server. A 5-bay NAS server Network-attached storage (NAS) is a file-level (as opposed to block-level storage) computer data storage server connected to a computer network providing data access to a heterogeneous group of clients. The term NAS can refer to both the technology and systems involved, or a specialized device built for such functionality (as unlike tangentially related technologies such as l...

 

 

Dragon Quest: The Adventure of Dai

Japanese manga by Riku Sanjo and Koji Inada and its franchise Dragon Quest: The Adventure of DaiCover of the first tankōbon volume, featuring Dai (front), Hadlar (back), Gome (bottom) and Brass (bottom right)DRAGON QUEST –ダイの大冒険–(Doragon Kuesuto: Dai no Daibōken)GenreAdventure[1]Fantasy[1]Created byYuji Horii MangaWritten byRiku SanjoIllustrated byKoji InadaPublished byShueishaEnglish publisherNA: Viz MediaImprintJump ComicsMagazineWeekly ...

 

 

List of thriller films of the 1990s

This list is incomplete; you can help by adding missing items. (August 2008) Thriller films By decade Pre-1940s 1940s 1950s 1960s 1970s 1980s 1990s 2000s 2010s 2020s vte A list of thriller films released in the 1990s. Title Director Cast Country Subgenre/notes 1990 After Dark, My Sweet James Foley Jason Patric, Rachel Ward, Bruce Dern United States Psychological thriller[1] The Ambulance Larry Cohen Eric Roberts, James Earl Jones, Red Buttons United States} [2] Bad Influence ...

Out of the Cellar

1984 studio album by RattOut of the CellarStudio album by RattReleasedFebruary 17, 1984 (1984-02-17)[1]Studio Village Recorder (Los Angeles) Sound City (Los Angeles) Genre Heavy metal[2][3] glam metal[4][5] Length36:41LabelAtlanticProducerBeau HillRatt chronology Ratt(1983) Out of the Cellar(1984) Invasion of Your Privacy(1985) Singles from Out of the Cellar Round and RoundReleased: February 1984 (US)[6] Wanted ManRelease...

 

 

The Tin Scratchers

Book by Ion Idriess The Tin Scratchers First editionAuthorIon IdriessCover artistClem SealeLanguageEnglishGenreautobiographyPublisherAngus and RobertsonPublication date1959Publication placeAustraliaPages260 pp The Tin Scratchers: The Story of Tin Mining in the Far North is a 1959 autobiographical book by Ion Idriess.[1] The book is an account of Idriess' attempts at making a fortune mining in the Cape York Peninsula and how he became involved in tin mining. [2] From his o...

 

 

Everglades National Park

National park in Florida (US) Everglades National ParkIUCN category II (national park)Sunset over the Everglades river of grass, January 2013Location in FloridaShow map of FloridaLocation in the United StatesShow map of the United StatesLocationMiami-Dade, Monroe, & Collier counties, Florida, United StatesNearest cityFlorida CityEverglades CityCoordinates25°18′45″N 80°41′15″W / 25.3125000°N 80.6875000°W / 25.3125000; -80.6875000[1]Area1,508...

Around the World in 80 Days (film 2004)

Around the World in 80 DaysSutradaraFrank CoraciProduserBill BadalatoHal LiebermanSkenarioDavid TitcherDavid BenulloDavid GoldsteinBerdasarkanAround the World in Eighty Daysoleh Jules VernePemeran Jackie Chan Steve Coogan Cécile de France Jim Broadbent Penata musikTrevor JonesDavid A. StewartSinematograferPhil MeheuxPenyuntingTom LewisPerusahaanproduksiWalden MediaDistributorWalt Disney PicturesTanggal rilis 13 Juni 2004 (2004-06-13) (Los Angeles, California) 16 Juni 2004 ...

 

 

Aragonese language

Romance language of northern Aragon, Spain Aragonés redirects here. For people with the surname Aragonés, see Aragonés (surname). AragonesearagonésPronunciation[aɾaɣoˈnes]Native toSpainRegionAragon; northern and central Huesca and northern ZaragozaEthnicityAragoneseNative speakersActive speakers: 10,000–12,000 (2017)[1]Active and passive speakers: 30,000–50,000 (2017)[1]Language familyIndo-European ItalicLatino-FaliscanLatinRomanceItalo-WesternWest...

 

 

Береговий Сергій Георгійович

Береговий Сергій Георгійович Старший солдатЗагальна інформаціяНародження25 вересня 1976(1976-09-25)КиївСмерть14 липня 2015(2015-07-14) (38 років)ЛуганськеПохованняСовський цвинтарВійськова службаПриналежність УкраїнаВид ЗС Збройні силиРід військ Механізовані військаФо�...

Educación superior

Los términos educación superior,[1]​ enseñanza superior, estudios superiores, educación profesional y educación terciaria aluden a la última etapa del proceso de aprendizaje académico, es decir, a todas las trayectorias formativas post-secundarias que cada país contempla en su sistema. Se imparte en las universidades, en las academias superiores o en las instituciones de formación profesional superior, entre otros.[2]​ Es un paso posterior a la educación secundaria, y es...

 

 

Коническое сечение

У этого термина существуют и другие значения, см. Конус (значения). Конические сечения: окружность, эллипс, парабола (плоскость сечения параллельна образующей конуса), гипербола. Три основных конических сечения Кони́ческое сече́ние, или ко́ника[1], — пересечение пл�...