Polígons de Thiessen

Els polígons de Thiessen, nomenats en honor al meteoròlec nortamericà Alfred H. Thiessen, són una construcció geomètrica que permet construir una partició del pla euclídeo. Estos objectes també varen ser estudiats pel matemàtic ucranià Gueorgui Voronói en 1907, d'a on prenen el nom alternatiu de diagrames de Voronoi o teselació de Voronoi, i pel matemàtic alemà Gustav Lejeune Dirichlet en 1850, d'a on prenen el nom de teselación de Dirichlet.
Els diagrames de Voronoi són un dels métodos d'interpolació més simples, basats en la distància euclidiana, especialment apropiada quan les senyes són qualitatius. Es creen en unir els punts entre sí, traçant les mediatrices dels segments d'unió. Els segments determinats per les interseccions d'estes mediatrices determinen una série de polígons en un espai bidimensional al voltant d'un conjunt de punts de control, de manera que el perímetro dels polígons generats siga equidistant als punts veïns i designen la seua àrea d'influència.
Diagrames de Voronói en el pla euclidiano ℝ2
La forma més fàcil i intuïtiva de visualisar als diagrames de Voronói és a través de la seua representació en el pla euclídeo. En la lliteratura clàssica se supon el fet de contar en un conjunt d'establiments que es desigen colocar sobre una certa regió geogràfica de tal manera que les ubicacions siguen lo més rendables possible. Per tant, es deu trobar una configuració que permeta que el número de clients atrets siga el més factible. La suposició llògica indica que els clients anirien a l'establiment més propenc al seu domicili i no a aquells que siguen molt lluntans. En base en açò, els diagrames de Voronói otorguen la configuració desijada pels establiments. El diagrama de Voronói induïx una subdivisió del pla euclidiano (la regió geogràfica) en funció d'un conjunt de llocs (els establiments), a on a cada lloc se li associa una i solament una subdivisió. Ademés, cada subdivisió engloba tots els punts més propencs al lloc associat als llocs restants, a açò li'l denomina un model de asignamiento de Voronói.[1]
Definició formal
En primera instància, denotem a la distància euclidiana entre dos punts i per . En el pla llavors es té:

Siga el conjunt de punts distints en el pla que són denominats com a llocs. Es definix el diagrama de Voronói de com la subdivisió del pla en regions, una per a cada , complint la propietat de proximitat en la que un punt pertany a la regió d'un lloc si i només si per a cada . Es denotarà al diagrama de Voronói de per mig de . Cada regió que correspon a un lloc es denotarà com i serà cridada regió de Voronói de .
La regió de Voronói per a un lloc està construïda a partir de les interseccions dels semiplanos formats en traçar els bisectores de cap als llocs . Prenent el cas a on únicament hi ha dos llocs i , es traça el segment de recta i posteriorment es traça el bisector de . Este bisector partix el pla en dos semiplanos, a on el semiplano que conté a (representat com ) representa el lloc geomètric de tots els punts més propencs a que a ; i el semiplano que conté a () alberga a tots els punts més pròxims a que a . D'acort en açò, llavors es pot establir de forma general cóm es definix la regió de Voronói per a un lloc .
està composta per l'intersecció de semiplanos que conformen una regió poligonal convexa que pot ser oberta o tancada. La regió està acotada per un màxim de vèrtiços i un màxim de arestes. Es tenen estes cantitats de vèrtiços i arestes degut a que els llocs més lluntans solen tindre associats regions de Voronói no acotades conformades per arestes i semi-arestes (arestes que tenen un vèrtiç d'inici pero no un de final).
Propietats
A continuació s'enunciaran un conjunt de propietats[1][2] del Diagrama de Voronói a on s'assumix que no pot haver quatre punts del conjunt original en posició cocircular. En cas que esta situació no siga contemplada, llavors es deuen considerar una gran cantitat de detalls que deuen ser agregats a les diferents propietats.
- Teorema 1. Siga un conjunt de llocs en el pla. Si tots els llocs són colineales, llavors consistix de llínees paraleles. D'una atra forma, és conexo i les seues arestes podrien ser segments o semi-llínees.
- Teorema 2. Per a , el número de vèrtiços en el diagrama de Voronói d'un conjunt de llocs en el pla és a lo més i el número d'arestes és a lo més .
La següent propietat ajuda a caracterisar els vèrtiços i arestes que componen el diagrama de Voronói. No obstant, és necessari definir qué significa el círcul buit més gran de , denotat com . Per a un punt , es definix com el círcul més gran que té a com el seu centre i no conté cap atre lloc de en el seu interior.
- Teorema 3. Per a un diagrama de Voronói d'un conjunt de llocs lo següent es complix:
- Un punt és un vèrtiç de si i solament si el seu més gran círcul buit conté tres o més llocs en el seu contorn.
- El bisector entre els llocs i definix una aresta de si i solament si hi ha un punt sobre el bisector tal que conté tant a i a en el seu contorn pero no un atre lloc.
- Teorema 4. Cada veí més propenc del lloc en definix una aresta de .
- Teorema 5. La regió de Voronói és oberta si i solament si és un punt en l'envolvente convexa del conjunt .
- Teorema 6. La gràfica dual del diagrama de Voronói definix la triangulació de Delaunay.
Algoritmes per a la construcció del Diagrama de Voronói
Algoritme per força bruta
Una primera aproximació per a la construcció del diagrama de Voronói consistix en explotar la geometria de cada regió de Voronói. Per cada lloc es construirà la seua regió de Voronói per mig del càlcul explícit dels semiplanos originats pels bisectores traçats sobre els demés llocs. Posteriorment, es computarà l'intersecció d'estos semiplanos para, finalment, donar orige a .
Este algoritme té moltes desventages d'entre les quals es tenen les que a continuació es descriuen. En primera instància, el càlcul explícit dels semi-plans i la seua intersecció pot provocar problemes de precisió en la computadora generat, evidentment, una versió incorrecta de . El segon inconvenient involucra que no es produïx informació immediata i que es puga aprofitar sobre el veïnat de cada lloc. Finalment, ya que es tracta de l'algoritme d'un algoritme ineficiente, no resulta estrany descobrir que la seua complexitat computacional siga alta. L'algoritme està en l'orde de
Algoritme dividix i venceràs
Este algoritme està fonamentat sobre el paradigma de disseny d'algoritmes dividix i venceràs. Donat el problema de construir el diagrama de Voronói per al conjunt de llocs, ara es dividirà a este últim en dos subconjunts i , en aproximadament el mateix tamany, dels que es deu trobar el seu diagrama de Voronoi independentment. Finalment, i deuen ser units per a poder obtindre . No obstant, ¿quina raó existix per a que es crea que i tinguen alguna relació en ?
Per a que es puga contestar l'última pregunta, és necessari definir construccions geomètriques que seran de vital importància.
Definició 1. Donat una petició de , siga el conjunt d'arestes de Voronoi que són compartides per parells de regions de Voronoi i .
La colecció d'arestes té les següents propietats.
Teorema 7 és el conjunt d'arestes d'una subgráfica de en les següents propietats:
- consta de cicles i cadenes d'arestes disjuntas. Si una cadena té una sola aresta, esta és una llínea recta; d'una atra forma les seues dos arestes extremes són rajos seminfinitos.
- Si i són linealmente separats (si més d'un punt pertany a la llínea de separació, tots estos punts són assignats a un mateix conjunt de la partició), llavors consistix d'una sola cadena monotónica.
En la finalitat de separar a en dos subconjunts se li deurà ordenar sobre les abcisas i prendre la recta que passe per la mijana, de tal sòrt que es tinguen dos subconjunts d'aproximadament el mateix tamany. Adicionalment, donada esta elecció de recta de separació, es pot dir que part al pla en una porció esquerra i una porció dreta . En base en açò, es té la següent propietat:
Teorema 8. Si i són linealmente separats per una llínea vertical en a l'esquerra i a la dreta, llavors el diagrama de Voronoi és l'unió de i .
A partir de l'última teorema és que es pot respondre la pregunta inicial sobre cóm es vinculen dos diagrames de Voronoi de dos particions per a generar el diagrama de Voronoi de tot el conjunt de llocs. El següent algoritme[2] establix la forma de calcular el diagrama de Voronoi per mig de la tècnica dividix i venceràs.
- Procediment DIAGRAMA DE VORONOI
Pas 1. Partir a en dos subconjunt i , d'aproximadament el mateix tamany, per mig de la mijana en les coordenades x.
Pas 2. Construir i recursivament.
Pas 3. Construir la cadena polígona , separant a i .
Pas 4. Descartar totes les arestes de que estiguen a l'esquerra de . El resultat és , el diagrama de Voronoi del diagrama sancer.
Algoritme de Fortune (agranada de recta)
Inspiració
L'algoritme de força bruta prèviament revisat té una complexitat , no obstant, per la teorema 2, es pot supondre que hi ha una forma molt més eficient de trobar el diagrama de Voronoi puix els seus elements constituents tenen complexitat .[1] En efecte, existix este algoritme i és cridat Algoritme de Fortune[3] en honor a Steven Fortune qui ho va inventar en 1986 i la complexitat del qual és .[1]

L'algoritme de Fortune està basat en una de les tècniques clau dins de la geometria computacional denominada agranada de recta. L'essència d'esta tècnica yacer en supondre que existix una recta que recorre el pla de dalt cap a avall (o d'esquerra a dreta, inclús en direccions opostes) i que a lo llarc del seu recorregut es interseca en les estructures que desigem processar. Quan es dona esta intersecció, es guarda certa informació de tal forma que ajude en els càlculs. És necessari que l'informació que s'haja obtingut en regions ya visitades per la recta siga invariante. És molt comú que està tècnica utilise dos tipos d'estructures de senyes: coa de prioritats a on es guarden events que no són més que punts a on la recta deu detindre's i un arbre binari de busca a on s'almagasenen els elements geomètrics que s'han intersecado en la recta i es necessita recordar per al processament futur. cal resaltar que degut a que en la computadora no es pot emular tal com el moviment continu de la recta d'agranada, es requerix idear una forma de discretisació del moviment de la recta que siga procesable en la computadora, d'ahí que els events siguen tal discretisació.
Propietats combinatòries
Per a aplicar l'agranada de recta al diagrama de Voronoi, intuitivament, es podria prendre al conjunt de llocs com els events i d'esta manera dur l'intersecció de la recta d'agranada en el diagrama de Voronoi. No obstant, degut a que el càlcul de depén de l'intersecció de plans, llavors no es podria mantindre el invariante de la tècnica ya que aun cuando ya haja processat un lloc, l'informació sobre la seua regió de Voronoi seguirà canviant pels llocs restants per processar. En base en açò, és imperatiu canviar la perspectiva i en lloc de mantindre l'intersecció de en es necessita mantindre l'informació sobre aquells llocs sobre que ya no podrà canviar pels llocs baix de .

Es denotarà al semi-pla tancat sobre com . Es busca quin és la part del diagrama de Voronoi sobre que ya no podrà canviar jamai, per ad açò es té lo següent. Donat un punt , la distància d'este a qualsevol punt baix de és més gran que la distància de a pròpiament. Ademés, el lloc més propenc no pot estar baix de si és a lo manco tan propenc a algun lloc com lo és a . Per tant, el lloc geomètric de punts més propencs d'algun lloc que a està llimitat per una paràbola. Seguint esta llínea, el lloc geomètric de tots els punts més propencs a algun lloc sobre que a en sí mateixa està acotat per un conjunt de lo més [1] arcs parabòlics. Este conjunt d'arcs es denomina llínea de plaja. Cada lloc sobre la llínea d'agranada definix una paràbola completament. La llínea de plaja conta en la propietat de monotonicidad ya que si es fa passar qualsevol recta vertical per ella, esta la interseca en exactament un punt.[1]
Llavors, en lloc de mantindre l'intersecció de en , es mantindrà la llínea de plaja conforme la llínea d'agranada es moga. Evidentment, no es pot representar explícitament la llínea de plaja ya que és contínua i es transforma cada que canvia de posició.

Un arc pot aparéixer en la llínea de plaja quan processa un nou lloc, d'ahí que açò prenga el nom de event de lloc. En este moment una nova paràbola (en forma de llínea vertical puix el costat recte és infinitesimalmente menut) trenca sobre la llínea de plaja. Conforme la llínea de plaja comença a baixar, la recentment creada paràbola comença a fer-se més amplia. Ademés, conforme va creixent la paràbola es generen interseccions en atres paràboles en la llínea de plaja, lo que comença a traçar les arestes[1] del diagrama de Voronoi.
Un segon event de la llínea d'agranada sorgix quan un arc es fa tan chicotet que es convertix en un punt. Quan es presenta açò, les interseccions que tenia en els atres arcs ( a l'esquerra i a la dreta) es junten. Esta trobada dels punts d'intersecció implica que dos arestes del diagrama s'estan trobat. En conseqüència, s'ha format un vèrtiç del diagrama de Voronoi. Gràficament, és el centre d'un círcul que passa pels llocs i corresponents a i , respectivament. Quan alcança el punt més baix d'este círcul, s'ostenta un event de círcul.
Estructures de senyes i algoritme
L'algoritme de Fortune necessita de tres tipos d'estructures de senyes:
- Estructura de senyes que ajude a guardar la porció del diagrama calculada fins al moment. Per a açò s'ampra una llista doblement conectada d'arestes DCEL.[1] Es referirà a este com .
- Coa de prioritats que permeta guardar els events de lloc i de círcul que deu processar la llínea d'agranada.
- Arbre de busca binari balancejat que guarde la llínea de plaja. Ya que no es pot guardar directament la llínea de plaja per la seua naturalea contínua, es fa lo següent. En els fulls , es guarden els arcs de la llínea de plaja, caracterisats pel lloc que els definix, mantenint l'orde com el que s'apreciaria en la llínea de plaja realment. Per la seua banda els nodos intermijos representen els punts de quebre (a on un arc trenca en la llínea de plaja) com túpalas , a on denota la paràbola a l'esquerra i la corresponent a la dreta.
El següent pseudocódigo es basa en el que es presenta en l'obra de Mark de Berg et al.[1]
Algoritme
Entrada. Conjunt de llocs en el pla.
Eixida dins d'una caixa de restricció en .
- Inicializar en tots els llocs; inicializar com a buit i una DCEL buida.
- while no estiga buida
- Remoure l'event en la coordenadana més gran de .
- if l'event és un event de lloc en then
- else , a on representa el full de representant l'arc que desapareixerà.
- Computar caixa de restricció que continga tots els vèrtiços de dins i una les semi-arestes cap a la caixa.
- Si està buit, insertar . De lo contrari fer els següents passos.
- Buscar en l'arc verticalment sobre . Si el full té una busca cap a , llavors és una falsa alarma i deu ser eliminat de .
- Reemplaçar el full de que representa a en un subárbol en tres fulls. El full en el centre guarda el lloc i atres dos guarden a que originalment estava en . Guardar les túplas i representant els nous punts de quebre.
- Crear nous registres de semi-arestes en per a l'aresta que separa a i , que serà traçada pels punts de quebre.
- Checar les tripleta d'arcs consecutius a on el nou arc de és l'arc esquerre per a vore si els punts de quebre convergixen.
- Borrar el full que representa l'arc a desaparéixer de . Actualisar túplas que representen els punts de quebre. Reebalancear . Eliminar de tots els events que involucren a .
- Afegir el centre del círcul causant de l'event com un registre de vèrtiç en . Crear dos semi-arestes corresponents als nous punts de quebre de la llínea de plaja.
- Checar la nova triplet d'arcs consecutius que tenia a en el mig si els dos punts de quebre convergixen. De ser aixina, insertar-ho l'event corresponent en . Fer lo mateix per a la triplet a on estava a la dreta.
Complexitat
L'algoritme s'eixecuta en i usa almagasenament. Açò es deu a que les operacions sobre i en prenen .[4] Les operacions en la DCEL prenen temps constant.[1] Quan es processa un event s'eixecuta un número constant d'operacions de tals operacions. I ya que es té events (per la teorema 2), llavors la complexitat és . Per la seua banda, l'almagasenament és llineal novament per la teorema 2.
Generalisació a ℝn

Per a cada conjunt topològic discret S de punts en un espai euclídeo i para casi tot punt x, existix un punt de S que és el més propenc a x. (Ací, el terme casi s'usa per a indicar que existixen excepcions en les quals x pot equidistar de dos o més punts de S.)
Si S conté només dos punts, a i b, llavors el conjunt de tots els punts que equidistan d'abdós és un hiperplano de codimensión 1. Eixe hiperplano és la frontera entre els punts més propencs a a que a b, i els punts més propencs a b que a a. De fet, eixe hiperplano és el pla bisector del segment que unix a i b. Més en general, el conjunt de punts més propencs a un punt c de S que a cap atre punt de S (conca d'atracció de c) és l'interior d'un politopo convexo (possiblement no acotat) cridat domini de Dirichlet o cela de Voronói de c. El conjunt de tots eixos politopos constituïx una teselació completa de l'espai euclídeo, cridada teselació de Voronói associada a S.
Si la dimensió de l'espai euclídeo és només 2, com en el pla euclídeo, llavors resulta molt senzill dibuixar teselaciones de Voronoi, com les de la figura adjunta.
Referències
- ↑ 1,00 1,01 1,02 1,03 1,04 1,05 1,06 1,07 1,08 1,09 de Berg, Mark; Cheong, Otfried; van Kreveld, Marc; Overmars, Mark (2008). «7», Computational Geometry: Algorithms and Applications, tercera edició (en anglés), Springer-Verlag Berlín Heidelberg, pp. 147-171. ISBN 978-3-540-77973-5.
- ↑ 2,0 2,1 Preparata, Franco P.; Shamos, Michael Ian (1985). «5», David Gries (ed.). Computational Geometry: an introduction (en anglés), Springer-Verlag, pp. 204-223. ISBN 0-387-96131-3.
- ↑ Steven Fortune. A sweepline algorithm for Voronoi diagrams. Proceedings of the second annual symposium on Computational geometry. Yorktown Heights, New York, United States, pp.313–322. 1986. ISBN 0-89791-194-6. ACM Digital LibrarySpringerLink
- ↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Clifford, Stein (2009). Introduction to Algorithms, tercera edició (en anglés), MIT Press. ISBN 978-0-262-03384-8.
- Este artícul conté una traducció derivada de «Polígonos de Thiessen» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.