Voronoi

Solo disponible en BuenasTareas
  • Páginas : 6 (1275 palabras )
  • Descarga(s) : 0
  • Publicado : 11 de diciembre de 2011
Leer documento completo
Vista previa del texto
Tema 5

El Diagrama de Voronoi
Geometr

Curso:  Profesora: Departamento: Curso académico: Ubicación: Actualizado: 

1º de Ingeniería Informática, Plan 2004 Lidia Ortega Alvarado Informática 2009/10
http://wwwdi.ujaen.es/asignaturas/gc/tema5.odp

16/11/2009

Índice
 Introducción ● Definición ● Propiedades ● Algoritmos de construcción ➔ Método Incremental ➔ Divide y Vencerás● Aplicaciones inmediatas ● Bibliografía


El diagrama de Voronoi

Introducción
Teléfono de emergencias: ¿dónde se encuentra?.....le envío la ambulancia más cercana,  ¿Dónde y cuantos postes de telefonía móvil habría que colocar  para que la recepción de la señal sea completa en una región? ¿Dónde colocamos un nuevo comercio para que sea  competente?¿Cual será el grado de pureza de los minerales de una  determinada zona? 

El diagrama de Voronoi

Introducción
Georgy Feodosevich Voronoi (1868­1908)

El diagrama de Voronoi

Descartes Dirichlet Voronoi Boldyrev Thiessen Niggli Wigner & Seitz Frank & Casper Brown Mead Hoofd et al. Icke

Astronomia Matemáticas  Matemáticas Geologia Meteorología Cristalografía Física Física Ecología Ecología Anatomía Astronomía

1644 1850 1908 1909 1911 1927 19331958 1965 1966 1985 1987

“Heavens” Tesselation de Dirichlet Voronoi diagram area de influencia de polígonos polígonos de Theissen dominio de acción regiones de Wigner­Seitz  dominio de los átomos

dominios capilares Voronoi diagram

Definición 
¿Cuál es el punto más cercano al punto x?

El diagrama de Voronoi

x

Definición El punto x está dentro de la región de puntos más cercanos al punto pi  V(pi)

El diagrama de Voronoi

p
i

La región de Voronoi del punto pi la denominamos V(pi)

Definición 
La unión de todas las regiones de Voronoi es el  diagrama de Voronoi

El diagrama de Voronoi

V(P)={V(p0),V(p1),...,V(p0)} punto generador vértice

arista

Propiedades 
1.­  Dos puntos pi y pj son vecinos si comparten una arista. Una aristaes la bisectriz perpendicular del segmento pipj 2.­  Un vértice es un punto  equidistante a tres generadores (si lo es a más de tres hablamos de casos degenerados) y es  la intersección de tres aristas 3.­  Una región de Voronoi es un polígono convexo o es una región no acotada 4.­  Una región de Voronoi es no acotada si su punto generador  pertenece a la envolvente convexa de la nube de puntos 5.­  Dentro del círculo con centro en un vértice de Voronoi y que pasa por 3 puntos generadores no puede existir ningún otro punto generador pi pj

El diagrama de Voronoi

Algoritmos de construcción
Método Incremental
PASO i+1  Partiendo del diagrama de Voronoi para los i puntos, V(P0P1,...,Pi), se  añade el punto i+1,  del siguiente  modo: 1.­ Se localiza en punto pi+1 en V(p0,p1,...,pi) en tiempo O(logn).   Sea V(pk) la región en la que  se encuentra.

El diagrama de Voronoi

pk

pi+1

2.­Encontrar las bisectrices entre pi+1   y pk ,y entre pk  y el resto de puntos cuya frontera es intersectada por las sucesivas bisectrices 3.­ Eliminar las porciones de arista y los vértices que queden dentro de la  nueva región de Voronoi

Algoritmos de construcción
Método Incremental
Tiempo de ejecución:  Insertar el punto pi+1 localización: O(logn)   ● crear la nueva región O(1) ● eliminar vértices y porciones de aristas O(1)


El diagrama de Voronoi

O(nlogn)

Algoritmos de construcción
Método Divide y Vencerás
Partimos del conjunto de puntos S 1.­ Dividir S en dos  subconjuntos S1 y S2 de  aproximadamente el  mismo tamaño. 2.­ Calcular recursivamente  Vor(S1) y Vor(S2). 3.­ Unir Vor(S1) y Vor(S2) para obtener Vor(S). S1 S2

El diagrama de Voronoi

Algoritmos de construcción
Método Divide y Vencerás
Partimos del conjunto de puntos S 1.­ Dividir S en dos  subconjuntos S1 y S2 de  aproximadamente el  mismo tamaño. 2.­ Calcular recursivamente  Vor(S1) y Vor(S2). 3.­ Unir Vor(S1) y Vor(S2)  para obtener Vor(S).

El diagrama de Voronoi

Vor(S1)...
tracking img