Diagrama Voronoi

Diagrama Voronoi a unui set aleatoriu de puncte în plan (toate punctele sunt incluse în imagine).

În matematică , o diagrama Voronoi (numită după Georgij Voronoi ), numit Voronoi tessellation , descompunerea Voronoi sau Dirichlet tessellation (numit dupa Lejeune Dirichlet ) este un tip particular de descompunere a unui spațiu metric determinat de distanțele în raport cu un anumit discret set de elemente ale spațiului (de exemplu, un set finit de puncte ).

În cel mai simplu și cel mai comun caz, cel al planului , având în vedere un set finit de puncte S , diagrama Voronoi pentru S este partiția planului care asociază o regiune V (p) la fiecare punct $p\in S$ ${\ displaystyle p \ în S}$ $p \ în S$ în așa fel încât toate punctele din perimetrul lui V (p) să fie mai aproape de p decât de orice alt punct din S.

Definiție

În orice set ( topologic ) discret de puncte S din spațiul euclidian și pentru aproape fiecare punct x , există un punct în S cel mai apropiat de x . „Aproape” este o clarificare necesară, deoarece unele puncte x pot fi echidistante de la 2 sau mai multe puncte ale lui S.

Dacă S conține doar două puncte, a și b, atunci locul geometric al punctelor echidistant de a și b este un hiperplan , adică un subspatiu afin de codimensiune 1. hiperplan va fi limita dintre mulțimea tuturor punctelor cele mai apropiate de o că b este mulțimea tuturor punctelor mai aproape de b decât o. Este axa segmentului ab .

În general, ansamblul de puncte cel mai apropiat de un punct $c\in S$ ${\ displaystyle c \ in S}$ $c \ în S$ că în orice alt punct al lui S este partea internă a unui politop (posibil fără margini) numit domeniu Dirichlet sau celulă Voronoi de c . Mulțimea acestor politopi este o teselare a întregului spațiu și se numește teselarea Voronoi corespunzătoare mulțimii S. Dacă dimensiunea spațiului este de numai 2, este ușor să graficați teselările Voronoi; în acest caz se referă de obicei semnificația diagramei Voronoi .

Proprietate

Graficul dual pentru o diagramă Voronoi corespunde triangulației Delaunay în raport cu același set de puncte S.
Perechea de puncte cea mai apropiată de S va corespunde unei perechi de celule Voronoi adiacente într-o diagramă Voronoi.
Două puncte sunt vârfurile adiacente ale învelișului convex al lui S și numai dacă celulele lor Voronoi au o latură infinită în comun.

Istorie

Utilizarea informală a diagramelor Voronoi poate fi urmărită până la Descartes în 1644. Dirichlet a folosit diagramele Voronoi bidimensionale și tridimensionale în studiile sale de forme pătratice în 1850. Medicul britanic John Snow a folosit o diagramă Voronoi în 1854 pentru a ilustra modul în care majoritatea oamenii care au murit în epidemia de holeră din Soho trăiau mai aproape de una dintre pompele Broad Street infectate decât orice altă pompă de apă.

Diagramele Voronoi își derivă numele de la matematicianul rus Georgii Fedoseevich Voronoi care a definit și a studiat cazul general n- dimensional în 1908. Diagramele Voronoi care își găsesc aplicația în geofizică și meteorologie pentru a analiza datele distribuite spațial (cum ar fi măsurătorile precipitațiilor) sunt numite Poligoane Thiessen , numite după meteorologul american Alfred H. Thiessen . În fizica materiei condensate , asemenea teselări sunt cunoscute și sub denumirea de celule Wigner-Seitz . Teselările Voronoi ale rețelei reciproce de impuls sunt numite zone Brillouin . Pentru rețelele generale din grupurile Lie , celulele sunt pur și simplu numite domenii fundamentale . În spațiile metrice generice, celulele sunt adesea denumite poligoane fundamentale .

Exemple

O secțiune a unei diagrame Voronoi pentru un set aleatoriu de puncte dintr-un cub. Rețineți că, în general, cu această procedură nu se obține o diagramă Voronoi bidimensională, în ciuda faptului că celulele, care sunt poliedre convexe, au secțiuni care sunt ele însele convexe.

Multe teselări Voronoi ale unor rețele regulate de puncte în două sau trei dimensiuni se dovedesc a fi teselări familiare:

o grilă bidimensională triunghiulară produce o teselare a hexagonelor, care va fi regulată dacă punctele grilei sunt vârfurile triunghiurilor echilaterale; o grilă dreptunghiulară va avea la rândul său o diagramă Voronoi compusă din dreptunghiuri, care vor fi și ele pătrate dacă grila a fost pătrată.
Două rețele bidimensionale triunghiulare regulate aliniate corespunzător pe două planuri paralele produc configurația prismelor hexagonale cu romburi la capetele care pot fi observate în stupi .
Presupunând că teselează spațiul cu cuburi, grila obținută prin plasarea unui punct în centrul fiecărei fețe a unui cub produce o teselare a dodecaedrelor rombice ca diagramă Voronoi.
Dacă, pe de altă parte, punctele sunt plasate în centrul fiecărui cub, obținem o teselare formată din octaedre trunchiate .

Revenind la plan, având două seturi $X, Da$ ${\ displaystyle X, Y}$ $X Y$ numere reale discrete, diagrama Voronoi în raport cu mulțimea $\{(x,y)\mid x\in X,y\in Y\}$ ${\ displaystyle \ {(x, y) \ mid x \ în X, y \ în Y \}}$ $\ {(x, y) \ mid x \ în X, y \ în Y \}$ produce o teselare compusă din dreptunghiuri (ale căror puncte nu sunt neapărat centrele).

Generalizări

Celulele Voronoi pot fi definite în valori ne-euclidiene (cum ar fi distanța Mahalanobis sau cea a geometriei taxiului ). Cu toate acestea, în astfel de cazuri nu este garantat faptul că teselarea Voronoi există (sau că este într - adevăr o teselare), deoarece locusul punctelor echidistant de la două puncte de date poate să nu fie un sub spațiu al codimensiunii 1 (chiar și în cazul bidimensional ).

Celulele Voronoi pot fi definite și prin măsurarea distanțelor la alte obiecte decât punctele. Diagrama Voronoi a acestor celule este numită și axa medială . Chiar și atunci când obiectele sunt segmente, celulele Voronoi pot avea margini non-drepte. Axa medială este utilizată în descompunerea imaginii, recunoașterea optică a caracterelor și alte aplicații de calcul. În știința materialelor, microstructurile policristaline din anumite aliaje metalice sunt de obicei reprezentate folosind teselări Voronoi. O versiune simplificată a diagramei Voronoi pentru segmente drepte neizolate este structura obținută prin traversarea bisectoarelor unghiurilor lor.

Diagrama aproximativă Voronoi a unui set de puncte. Observați culorile umbrite ale granițelor dintre celulele Voronoi.

Descrierea diagramei Voronoi a n puncte în spațiul d- dimensional necesită spațiu $O(n^{\lceil d/2\rceil })$ ${\ displaystyle O (n ^ {\ lceil d / 2 \ rceil})}$ $O (n ^ {{\ lceil d / 2 \ rceil}})$ . Cu toate acestea, diagramele Voronoi sunt adesea nerealizabile pentru d > 2. O alternativă în aceste cazuri este utilizarea diagramelor aproximative Voronoi, în care celulele Voronoi au margini moi, care pot fi aproximate. ^[1]

Aplicații

Structura unei diagrame Voronoi poate fi exploatată pentru a descoperi punctul lui S cel mai apropiat de un punct dat x fără a calcula distanța lui x de la fiecare element al lui S la fiecare cerere. O astfel de căutare poate avea aplicații geografice în sistemele de informații geografice (de exemplu „găsiți spitalul cel mai aproape de o anumită casă”) sau în căutarea unor articole similare într-o bază de date .

Diagramele Voronoi sunt utile și în fizica polimerilor ; ele pot fi de fapt utilizate pentru a reprezenta volumul liber al polimerului. Ele pot fi, de asemenea, utilizate în studierea capacităților rețelelor fără fir .

Curiozitate

-Software-ul de modding a hărților Company of Heroes 2 calculează teritoriul afectat de punctele strategice ale jocului folosind o diagramă Voronoi de complexitate variabilă, după cum este exemplificat prin comanda „Calculați Voronoi”, prezentă în devkitul menționat anterior.

Notă

^ S. Arya, T. Malamatos și DM Mount, diagrame Voronoi eficiente în spațiu , Proc. 34th ACM Symp. on Theory of Computing (STOC 2002), pp. 721-730.

Bibliografie

( DE ) Johann Peter Gustav Lejeune Dirichlet (1850). Über die Reduktion der positiven quadratischen Formen mit drei unbestimmten ganzen Zahlen . Journal für die Reine und Angewandte Mathematik, 40 : 209-227.
( FR ) Georgy Voronoi (1907). Nouvelles applications des paramètres continus à la theorie des formes squareques . Journal für die Reine und Angewandte Mathematik, 133 : 97-178, 1907
Atsuyuki Okabe, Barry Boots, Kokichi Sugihara și Sung Nok Chiu (2000). Teselări spațiale - Concepte și aplicații ale diagramelor Voronoi . a doua editie. John Wiley, 2000, 671 pagini ISBN 0-471-98635-6
Franz Aurenhammer (1991). Diagrame Voronoi - Un sondaj al unei structuri de date geometrice fundamentale . ACM Computing Surveys, 23 (3): 345-405, 1991.
( EN ) Adrian Bowyer (1981). Computing Dirichlet tessellations , The Computer Journal 1981 24 (2): 162-166.
(EN) David F. Watson (1981). Calculul teselării n-dimensionale cu aplicarea pe politopii Voronoi , The Computer Journal, Heyden & Sons Ltd., Vol 2, Num 24, pp. 167–172.
Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Schwarzkopf, Capitolul 7: Diagrame Voronoi , în Computational Geometry , ediția a II-a, Springer-Verlag, 2000, pp. 147-163, ISBN 3-540-65620-0 . Include o descriere a algoritmului Fortune.

Elemente conexe

Algoritmul Fortune - un algoritm de complexitate O ( n log ( n )) pentru a genera diagrama Voronoi a unui set de puncte în plan
Algoritm Bowyer-Watson - un algoritm pentru generarea diagramelor Voronoi în orice dimensiune.
Triangularea Delaunay
Geometrie de calcul
Algoritmul lui Lloyd

Alte proiecte

Wikimedia Commons conține imagini sau alte fișiere pe diagrama Voronoi

linkuri externe

( RO ) Generator de diagrame Voronoi online , la alexbeutel.com .
( RO ) Demonstrație în diferite valori , pe nirobakun.com .
( EN ) Diagrame Voronoi pe Mathworld , la mathworld.wolfram.com .
( EN ) Componente arhitecturale parametrizate și programate folosind diagrame Voronoi , la m-any.org .
( EN ) Algoritmul rapid al carenei pentru calcularea diagramelor Voronoi în 2 sau mai multe dimensiuni , pe qhull.org .
( EN ) Applications of Voronoi Diagrams: from Archaeology to Zoology , on ics.uci.edu .
( EN ) Diagrame Voronoi în CGAL , Biblioteca de algoritmi pentru geometrie calculațională
( EN ) Website Voronoi: Utilizarea diagramelor Voronoi pentru analiza spațiului , la voronoi.com . Adus la 18 decembrie 2007 (arhivat din original la 5 septembrie 2008) .
( RO ) Discuții și galerie de imagini despre teselări centroidale Voronoi , pe math.psu.edu . Adus la 18 decembrie 2007 (arhivat din original la 16 iunie 2013) .
( EN ) Metoda lui Lloyd de a crea diagrame centroidale Voronoi dintr-un set de puncte generatoare , pe mrl.nyu.edu .
( EN ) Diagrame Voronoi în Python , acasă.scarlet.be . Adus la 18 decembrie 2007 (arhivat din original la 12 martie 2008) .
( EN ) Centrul de cercetare privind diagramele Voronoi , pe voronoi.hanyang.ac.kr .

Controlul autorității	Tezaur BNCF 54053 · LCCN (EN) sh88006450 · GND (DE) 4226013-9 · BNF (FR) cb12151119k (dată)

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică

[1] S. Arya, T. Malamatos și DM Mount, diagrame Voronoi eficiente în spațiu , Proc. 34th ACM Symp. on Theory of Computing (STOC 2002), pp. 721-730.

[1]