Graficul de vecinătate relativă

Un grafic de vecinătate relativă este un grafic nedirecționat definit pe o mulțime de puncte din planul euclidian prin conectarea a două puncte p și q cu o muchie atunci când nu există un al treilea punct r care să fie mai aproape de p și q decât p și q sunt de fiecare. alte. Acest grafic a fost propus de Godfried Toussaint în 1980 ca o modalitate de a defini o structură pe un set de puncte care reflectă percepția umană asupra formei mulțimii [1] [2] [3] .

Algoritmi

Supovit [4] a arătat cum se construiește eficient un grafic de vecinătate relativă în timp O( n  log  n ) [5] . Graficul poate fi calculat în timp mediu O ( n ) pentru o mulțime arbitrară de puncte distribuite uniform în pătratul unității [6] . Graficul de vecinătate relativă poate fi calculat în timp liniar din triangulația Delaunay a unui set de puncte [7] [8] .

Generalizări

Deoarece un grafic este definit doar în termeni de distanțe dintre puncte, un grafic de vecinătate relativă poate fi definit pentru seturi de puncte dintr-un spațiu de orice dimensiune [1] [9] și pentru metrici non-euclidiene [1] [7] [10 ] ] [11] .

Grafice înrudite

Graficul de vecinătate relativă este un exemplu de nucleu beta bazat pe . Acesta este un subgraf al triangulației Delaunay . La rândul său, arborele de acoperire minim euclidian este subgraful său, ceea ce implică faptul că este un graf conex .

Graficul Urquhart , format prin îndepărtarea celei mai lungi muchii din fiecare triunghi într-o triunghiulare Delaunay, a fost propus inițial ca o metodă rapidă pentru calcularea unui grafic de vecinătate relativă [12] . Deși graficul Urquhart este uneori diferit de graficul de vecinătate relativă [13] , el poate fi folosit ca o aproximare a graficului de vecinătate relativă [14] .

Note

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

Literatură