Voronoi
Páginas: 6 (1275 palabras)
Publicado: 11 de diciembre de 2011
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 (18681908)
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 WignerSeitz 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)...
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 (18681908)
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 WignerSeitz 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)...
Leer documento completo
Regístrate para leer el documento completo.