Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.
-
Upload
arcelia-favela -
Category
Documents
-
view
217 -
download
0
Transcript of Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.
![Page 1: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/1.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3
![Page 2: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/2.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3
Aeronáutica
Entre muchos aviones en una pantalla encontrar los dos más cercanos
P1: Tráfico aéreoP1: Tráfico aéreo
![Page 3: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/3.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3Entre muchos linces en un terreno encontrar el más cercano a cada cual
P2: EcologíaP2: Ecología
![Page 4: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/4.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3Conectar n puntos de tal forma que la longitud de la red sea mínima
P3: Trazado de redesP3: Trazado de redes
![Page 5: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/5.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3
![Page 6: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/6.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3
P5: Clasificador de objetosP5: Clasificador de objetos
Dado un conjunto de modelos y un nuevo elemento q, encontrar el modelo más cercano a q.
![Page 7: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/7.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3
P6: Propiedades físicas de materiales
P6: Propiedades físicas de materiales
Dado una serie de compuestos tratar de determinar cuál serán las propiedades físicas de sus mezclas.
![Page 8: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/8.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3
P6: El círculo máximo vacío.P6: El círculo máximo vacío.
![Page 9: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/9.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3
Aeronáutica
Entre muchos aviones en una pantalla encontrar los dos más cercanos
P1: Tráfico aereoP1: Tráfico aereo
puntos en el planopuntos en el plano
El par más cercano
El par más cercano
![Page 10: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/10.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3Entre muchos linces en un terreno encontrar el más cercano a cada cual
P2: EcologíaP2: Ecología
puntos en el planopuntos en el plano
Todos los pares más cercanos
Todos los pares más cercanos
![Page 11: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/11.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3Conectar n puntos de tal forma que la longitud de la red sea mínima
P3: Trazado de redesP3: Trazado de redes
Árbol recubridor (generador) mínimo
Árbol recubridor (generador) mínimo
![Page 12: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/12.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3Conectar n puntos de tal forma que la longitud de la red sea mínima
P3: Trazado de redesP3: Trazado de redes
Árbol recubridor (generador) mínimo
Árbol recubridor (generador) mínimo
Árbol de Steiner
Algoritmos genéticos
![Page 13: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/13.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3
![Page 14: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/14.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3
![Page 15: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/15.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3
Entre todas las triangulaciones encontrar la más equilátera posible
Triangulación equiláteraTriangulación equilátera
![Page 16: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/16.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3
P5: Clasificador de objetosP5: Clasificador de objetos
Dado un conjunto de modelos y un nuevo elemento q, encontrar el modelo más cercano a q.
Dado un conjunto de puntos S y un nuevo punto q, encontrar el elemento de S más cercano a q.
Vecino más cercanoVecino más cercano
![Page 17: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/17.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3
P6: Propiedades físicas de materiales
P6: Propiedades físicas de materiales
Dado una serie de compuestos tratar de determinar cuál serán las propiedades físicas de sus mezclas.
![Page 18: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/18.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3
Envolvente convexaEnvolvente convexa
Dada una serie de puntos encontrar el menor convexo que los contiene
Dada una serie de puntos encontrar el menor convexo que los contiene
![Page 19: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/19.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3
P6: El círculo máximo vacío.P6: El círculo máximo vacío.
![Page 20: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/20.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3
Entre muchos aviones en una pantalla encontrar los dos más cercanospuntos en el planopuntos en el planoEl par más
cercano
El par más cercano
Entre muchos linces en un terreno encontrar el más cercano a cada cualpuntos en el planopuntos en el planoTodos los pares más cercanos
Todos los pares más cercanos
Conectar n puntos de tal forma que la longitud de la red sea mínimaÁrbol recubridor (generador) mínimo
Árbol recubridor (generador) mínimo
Vecino más cercanoVecino más cercanoDado un conjunto de puntos S y un nuevo punto q, encontrar el elemento de S más cercano a q.
Entre todas las triangulaciones encontrar la más equiláteraTriangulación equiláteraTriangulación equilátera
Envolvente convexaEnvolvente convexa
Dada una serie de puntos encontrar el menor convexo que los contieneDada una serie de puntos encontrar el menor convexo que los contiene
Dados N puntos en plano, hallar máximo círculo sin puntos en interiorDados N puntos en plano, hallar máximo círculo sin puntos en interior
O(n2)
Fuerza
bru
ta
O(n2)
O(2n)
?
O(n)
?
O(n3)
Círculo máximo vacío.Círculo máximo vacío.
![Page 21: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/21.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3
La soluciónLa solución
![Page 22: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/22.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3
El problema del par más El problema del par más cercanocercano (Closest pair)(Closest pair)
PlanteamientoPlanteamiento
Figura 2.-
Figura 2.-
El par de puntos más cercanosEl par de puntos más cercanos
![Page 23: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/23.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3
Solución inmediata: todos con todos algoritmo O(N2)
Solución inmediata: todos con todos algoritmo O(N2)
Para dimensión 1 sería O(NlogN).Para dimensión 1 sería O(NlogN).
Más cercanos=consecutivos
Ordenación previa O(NlogN) +Comparación consecutivos (lineal)
![Page 24: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/24.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3
Solución 1: (Usando el diagrama de Voronoi)Solución 1: (Usando el diagrama de Voronoi)
Teorema 1: El diagrama de Voronoi de una nube de N puntos en el plano puede construirse en tiempo óptimo O(NlogN).
Teorema 1: El diagrama de Voronoi de una nube de N puntos en el plano puede construirse en tiempo óptimo O(NlogN).
![Page 25: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/25.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3
Solución 2: (Usando técnica divide y vencerás) Solución 2: (Usando técnica divide y vencerás)
Buscamos algoritmo O(NlogN).
Se divide el problema en dos cuyas soluciones se combinen en tiempo lineal.
Si par más cercano uno S1 y otro S2 N2/2 comparaciones tiempo cuadrático.
Divide y vencerás O(NlogN)
Buscamos algoritmo O(NlogN).
Se divide el problema en dos cuyas soluciones se combinen en tiempo lineal.
Si par más cercano uno S1 y otro S2 N2/2 comparaciones tiempo cuadrático.
Divide y vencerás O(NlogN)
![Page 26: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/26.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3
función ClosestPair1 ( S : conjunto de [1...N] puntos en una dimensión) dev (l : distancia entre los dos más cercanos)
si ( numeroElementos(S) = 2 ): l := S(2) – S(1) | si ( numeroElementos(S) = 1 ): l := INFINITO | otras: m = mediaValores(S) Construye(S, S1, S2) // S1 = {p: m³ p}, S2 = {p: m<p} donde pÎ S l1 = ClosestPair1 ( S1 ) l2 = ClosestPair1 ( S2 ) p = max ( S1 ) q = min ( S2 ) l = min ( l1, l2, q-p ) fsi
![Page 27: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/27.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3
Algoritmo anterior: válido para dimensión 1
Buscamos algoritmo O(NlogN) para dimensión 2.
Se divide el problema en dos cuyas soluciones se combinen en tiempo lineal.
![Page 28: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/28.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3
procedure CPAIR2 (S: conjunto [1..N] de puntos)
1. Dividir S en dos subconjuntos S1 y S2 por una línea vertical l por la mediana.
2. Encontrar la separación entre el par más cercano en S1 y S2 recursivamente, 1, 2.
3. = min(1, 2)4. Sea P1 un subconjunto de puntos de S1 que no distan
más de de l y sea igualmente P2 para S2. Proyéctense los puntos de P1 y P2 en l y ordénense por la coordenada y. Sean P1* y P2* las dos secuencias anteriores después de la ordenación.
5. Para cada punto p de P1* examinar los puntos q de P2* a distancia menor que de p (nunca serán más de 6 para cada punto). Sea la distancia mínima encontrada entre estos pares de puntos.
6. s = min (,)7. Devolver s
![Page 29: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/29.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3
Coste del algoritmo: • Pasos 1 y 5 tiempo O(N). • Pasos 3 y 6 tiempo constante.• Paso 2 tiempo 2T(N/2), si T(N) tiempo
algoritmo N puntos. • Paso 4 es ordenación
– tiempo O(NlogN) si ordenásemos en cada iteración
– Si usamos preprocesamiento • T(N) = 2T(N/2) + O(N) = O(NlogN)
Teorema: La distancia más corta determinada por N puntos en el plano se puede encontrar en O(NlogN) y este tiempo es óptimo.
![Page 30: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/30.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3
Planteamiento
Dados N puntos en el plano, con preprocesamiento, encontrar el vecino más cercano de un nuevo punto dado q.
Planteamiento
Dados N puntos en el plano, con preprocesamiento, encontrar el vecino más cercano de un nuevo punto dado q.
NEAREST-NEIGHBOR SEARCH(Búsqueda del vecino más
cercano)
NEAREST-NEIGHBOR SEARCH(Búsqueda del vecino más
cercano)
![Page 31: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/31.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3
Método más importante para acelerar búsqueda:
problema de la clasificación
Método más importante para acelerar búsqueda:
problema de la clasificación
Todo objeto será clasificado como perteneciente a un sólo individuo de una población conocida: población al que pertenece su vecino más cercano.
Todo objeto será clasificado como perteneciente a un sólo individuo de una población conocida: población al que pertenece su vecino más cercano.
![Page 32: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/32.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3
. .
En la figura el punto U debe ser clasificado como "B".
En la figura el punto U debe ser clasificado como "B".
B
![Page 33: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/33.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3
Tratamiento La búsqueda del vecino más cercano se hará sobre una estructura ordenada. Así, encontrar el vecino más cercano se reduce a hacer una búsqueda binaria.
Tratamiento La búsqueda del vecino más cercano se hará sobre una estructura ordenada. Así, encontrar el vecino más cercano se reduce a hacer una búsqueda binaria.
Dados N números reales x1,x2,...xN la búsqueda binaria (con preprocesamiento) identifica a xi como el vecino más cercano al número q. Esto es válido para varias dimensiones.
Dados N números reales x1,x2,...xN la búsqueda binaria (con preprocesamiento) identifica a xi como el vecino más cercano al número q. Esto es válido para varias dimensiones.
![Page 34: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/34.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3
Teorema: En el peor caso se necesitan (log N) comparaciones para hallar al vecino más cercano a un punto en cualquier dimensión.
Teorema: En el peor caso se necesitan (log N) comparaciones para hallar al vecino más cercano a un punto en cualquier dimensión.
Teorema: El problema del vecino más cercano puede ser resuelto en tiempo (logN) con preprocesamiento (NlogN).
Teorema: El problema del vecino más cercano puede ser resuelto en tiempo (logN) con preprocesamiento (NlogN).
El preprocesamiento sobre nube de puntos es construir el diagrama de Voronoi. Este se construye en tiempo óptimo (NlogN).
El preprocesamiento sobre nube de puntos es construir el diagrama de Voronoi. Este se construye en tiempo óptimo (NlogN).
![Page 35: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/35.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3
El problema de los vecinos más cercanos El problema de los vecinos más cercanos (All Nearest-Neighbor Search)(All Nearest-Neighbor Search)
Planteamiento
• "Dados N puntos en el plano, encontrar el vecino más cercano a cada punto."
• B es el vecino más cercano de un punto A dentro de un conjunto de puntos S si y sólo si la distancia entre dichos puntos es la mínima distancia entre A y cualquier punto de S:
dist (A,B) = min dist(A,C). C S – A
![Page 36: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/36.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3
Representación plana: grafo dirigido donde si A y B son nodos
del grafo y B es el más cercano a A los unimos con un arco de A a B.
![Page 37: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/37.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3
• Si B es el vecino más cercano a A A NO tiene que ser vecino más cercano a B.
Si A es vecino más cercano a B y B es el vecino mas cercano a A el par (A, B) es un par recíproco.
• Un punto puede ser el vecino más cercano de varios puntos de la nube.
![Page 38: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/38.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3
PROPIEDAD: Cada vecino más cercano al punto define una arista de su región de Voronoi.
Construido Diagrama Voronoi Tiempo lineal: cada arista se visita como máximo dos veces
PROPIEDAD: Cada vecino más cercano al punto define una arista de su región de Voronoi.
Construido Diagrama Voronoi Tiempo lineal: cada arista se visita como máximo dos veces
SOLUCIÓN:Construir Diagrama de Voronoi de la nube de puntos.
![Page 39: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/39.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3
Lema 3. Dado una partición de S en dos subconjuntos disjuntos S1 y S2 la arista más corta que une un vértice de S1 con uno de S2 es entre dos vecinos de Vor(S).
Nota: El número de vecinos de Vor(S) es lineal.
![Page 40: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/40.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3
Lema 3. Dado una partición de S en dos subconjuntos disjuntos S1 y S2 la arista más corta que une un vértice de S1 con uno de S2 es entre dos vecinos de Vor(S).
Nota: El número de vecinos de Vor(S) es lineal.
Teorema. Todos los vecinos más cercanos de S puede ser resuelto en tiempo óptimo lineal conociendo Vor(S).
Corolario. El par más cercanos de S puede ser resuelto en tiempo óptimo lineal conociendo Vor(S).
![Page 41: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/41.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3
Árbol recubridor euclídeo mínimo(Euclidean Minimum Spanning Tree)
Planteamiento.
Dados N puntos en el plano, construir árbol de longitud total mínima y cuyos vértices sean los puntos dados.
Solución: lista de N-1 pares puntos (aristas árbol)
Planteamiento.
Dados N puntos en el plano, construir árbol de longitud total mínima y cuyos vértices sean los puntos dados.
Solución: lista de N-1 pares puntos (aristas árbol)
![Page 42: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/42.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3
Se presenta en aplicaciones relacionadas con trabajos de redes.
Ejemplo:Se quiere instalar un sistema de comunicaciones conectando los N nodos de la red con cables, utilizando el EMST (Euclidean Minimun Spanning Tree) el coste de la instalación será el mínimo.
Se presenta en aplicaciones relacionadas con trabajos de redes.
Ejemplo:Se quiere instalar un sistema de comunicaciones conectando los N nodos de la red con cables, utilizando el EMST (Euclidean Minimun Spanning Tree) el coste de la instalación será el mínimo.
![Page 43: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/43.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3
El problema del árbol recubridor (Minimum Spanning Tree)
es un problema clásico teoría de grafos
El problema del árbol recubridor (Minimum Spanning Tree)
es un problema clásico teoría de grafos
Dado grafo G: N nodos y E aristas ponderadas, hallar menor subárbol de G con todos los vértices de G.
Dado grafo G: N nodos y E aristas ponderadas, hallar menor subárbol de G con todos los vértices de G.
Soluciones independientes: Dijkstra (1959), Kruskal (1956), Prim
(1957)
Soluciones independientes: Dijkstra (1959), Kruskal (1956), Prim
(1957)
Algoritmos polinomialesUn grafo con N vértices puede llegar a tener hasta N^(N-2) subárboles.
Algoritmos polinomialesUn grafo con N vértices puede llegar a tener hasta N^(N-2) subárboles.
![Page 44: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/44.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3
Tratamiento Previa ordenación, el problema EMST es transformable a tiempo lineal. Luego (N log N), es límite inferior del problema para N puntos.
Tratamiento Previa ordenación, el problema EMST es transformable a tiempo lineal. Luego (N log N), es límite inferior del problema para N puntos.
Lema 1: [Prim (1957)] Sea G = (V,E) grafo ponderado y {V1,V2} partición de V. Existe árbol recubridor de G que contiene la arista más corta con extremos uno en V1 y el otro en V2.
Lema 1: [Prim (1957)] Sea G = (V,E) grafo ponderado y {V1,V2} partición de V. Existe árbol recubridor de G que contiene la arista más corta con extremos uno en V1 y el otro en V2.
![Page 45: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/45.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3
Vértices V, los puntos de la nube.
Peso aristas la distancia entre extremos.
El algoritmo EMST trata en cada paso un bosque de árboles.
Bosque inicial la nube de puntos.
Vértices V, los puntos de la nube.
Peso aristas la distancia entre extremos.
El algoritmo EMST trata en cada paso un bosque de árboles.
Bosque inicial la nube de puntos.
Algoritmo: Seleccionar un árbol T del bosque. Encontrar una arista (u’,v’) tal que d(u’,v’)=min{d(u,v): u T, v S-T} Si T’ es árbol que contiene a v’, combinar T y T’ enlazándolos por la arista (u’,v’). Algoritmo finaliza cuando bosque se convierte en un árbol, nos podemos apoyar en el diagrama de Voronoi basta examinar aristas triangulación Delaunay, es decir, basta hallar MST de un grafo plano.
Algoritmo: Seleccionar un árbol T del bosque. Encontrar una arista (u’,v’) tal que d(u’,v’)=min{d(u,v): u T, v S-T} Si T’ es árbol que contiene a v’, combinar T y T’ enlazándolos por la arista (u’,v’). Algoritmo finaliza cuando bosque se convierte en un árbol, nos podemos apoyar en el diagrama de Voronoi basta examinar aristas triangulación Delaunay, es decir, basta hallar MST de un grafo plano.
![Page 46: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/46.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3
proc EMST alg 1 F:= 2 desde i:=1 hasta N 3 etapa(pi):=0 encola(F,pi) fdesde (* cola inicializada *) 4 j:=1 (* valor de etapa se inicializa al valor siguiente *) 5 mientras ( F contenga más de un número) 6 T:= cabeza(F) si (etapa(T)=j) 7 clean-up 8 j=j+1 fsi 9 (u,v):=arista más corta incidente a T (con u en T) 10 T’:= árbol en F que contiene a v 11 T’’:= unir(T,T’) 12 borra T’ de F 13 etapa(T’’):= min(etapa(T),etapa(T’))+1 14 encola(F,T’’) fmientras fin
proc EMST alg 1 F:= 2 desde i:=1 hasta N 3 etapa(pi):=0 encola(F,pi) fdesde (* cola inicializada *) 4 j:=1 (* valor de etapa se inicializa al valor siguiente *) 5 mientras ( F contenga más de un número) 6 T:= cabeza(F) si (etapa(T)=j) 7 clean-up 8 j=j+1 fsi 9 (u,v):=arista más corta incidente a T (con u en T) 10 T’:= árbol en F que contiene a v 11 T’’:= unir(T,T’) 12 borra T’ de F 13 etapa(T’’):= min(etapa(T),etapa(T’))+1 14 encola(F,T’’) fmientras fin
![Page 47: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/47.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3
Teorema 1. EMST de nube S de N puntos en el plano puede ser computado en un tiempo óptimo O(N) a partir de la triangulación de Delaunay de S.
Como el cálculo de la triangulación de Delaunay es O(N log N) sigue:
Corolario. EMST de nube de N puntos en el plano computada en un tiempo óptimo O(N log N).
Teorema 1. EMST de nube S de N puntos en el plano puede ser computado en un tiempo óptimo O(N) a partir de la triangulación de Delaunay de S.
Como el cálculo de la triangulación de Delaunay es O(N log N) sigue:
Corolario. EMST de nube de N puntos en el plano computada en un tiempo óptimo O(N log N).
![Page 48: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/48.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3
MST
1. S1={p,q} donde pq es el par más cercano,
2. S2=S-S1
3. S1=S1v donde v es el vértice de S2 más cercano a S1
![Page 49: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/49.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3
Entre muchos aviones en una pantalla encontrar los dos más cercanospuntos en el planopuntos en el planoEl par más
cercano
El par más cercano
Entre muchos linces en un terreno encontrar el más cercano a cada cualpuntos en el planopuntos en el planoTodos los pares más cercanos
Todos los pares más cercanos
Conectar n puntos de tal forma que la longitud de la red sea mínimaÁrbol recubridor (generador) mínimo
Árbol recubridor (generador) mínimo
Vecino más cercanoVecino más cercanoDado un conjunto de puntos S y un nuevo punto q, encontrar el elemento de S más cercano a q.
Entre todas las triangulaciones encontrar la más equiláteraTriangulación equiláteraTriangulación equilátera
Envolvente convexaEnvolvente convexa
Dada una serie de puntos encontrar el menor convexo que los contieneDada una serie de puntos encontrar el menor convexo que los contiene
Dados N puntos en plano, hallar máximo círculo sin puntos en interiorDados N puntos en plano, hallar máximo círculo sin puntos en interior
O(n2)
Fuerza
bru
ta
O(n2)
O(2n)
?
O(n)
?
O(n3)
Círculo máximo vacío.Círculo máximo vacío.
O(n)D
iagra
ma d
e V
oro
noiO(n)
?
?
O(log n)
?
?
![Page 50: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/50.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3
MST
1. S1={p,q} donde pq es el par más cercano,
2. S2=S-S1
3. S1=S1v donde v es el vértice de S2 más cercano a S1
![Page 51: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/51.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3
MST
1. S1={p,q} donde pq es el par más cercano,
2. S2=S-S1
3. S1=S1v donde v es el vértice de S2 más cercano a S1
![Page 52: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/52.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3
MST
1. S1={p,q} donde pq es el par más cercano,
2. S2=S-S1
3. S1=S1v donde v es el vértice de S2 más cercano a S1
![Page 53: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/53.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3
MST
1. S1={p,q} donde pq es el par más cercano,
2. S2=S-S1
3. S1=S1v donde v es el vértice de S2 más cercano a S1
Lema 3. Dado una partición de S en dos subconjuntos disjuntos S1 y S2 la arista más corta que une un vértice de S1 con uno de S2 es entre dos vecinos de Vor(S).
Nota: El número de vecinos de Vor(S) es lineal.
Teorema. El MST puede construirse en tiempo lineal óptimo a partir de Vor(S).
![Page 54: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/54.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3
Entre muchos aviones en una pantalla encontrar los dos más cercanospuntos en el planopuntos en el planoEl par más
cercano
El par más cercano
Entre muchos linces en un terreno encontrar el más cercano a cada cualpuntos en el planopuntos en el planoTodos los pares más cercanos
Todos los pares más cercanos
Conectar n puntos de tal forma que la longitud de la red sea mínimaÁrbol recubridor (generador) mínimo
Árbol recubridor (generador) mínimo
Vecino más cercanoVecino más cercanoDado un conjunto de puntos S y un nuevo punto q, encontrar el elemento de S más cercano a q.
Entre todas las triangulaciones encontrar la más equiláteraTriangulación equiláteraTriangulación equilátera
Envolvente convexaEnvolvente convexa
Dada una serie de puntos encontrar el menor convexo que los contieneDada una serie de puntos encontrar el menor convexo que los contiene
Dados N puntos en plano, hallar máximo círculo sin puntos en interiorDados N puntos en plano, hallar máximo círculo sin puntos en interior
O(n2)
Fuerza
bru
ta
O(n2)
O(2n)
?
O(n)
?
O(n3)
Círculo máximo vacío.Círculo máximo vacío.
O(n)D
iagra
ma d
e V
oro
noiO(n)
O(n)
?
O(log n)
?
?
![Page 55: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/55.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3
Entre muchos aviones en una pantalla encontrar los dos más cercanospuntos en el planopuntos en el planoEl par más
cercano
El par más cercano
Entre muchos linces en un terreno encontrar el más cercano a cada cualpuntos en el planopuntos en el plano
Todos los pares más cercanos
Todos los pares más cercanos
Conectar n puntos de tal forma que la longitud de la red sea mínimaÁrbol recubridor (generador) mínimo
Árbol recubridor (generador) mínimo
Vecino más cercanoVecino más cercanoDado un conjunto de puntos S y un nuevo punto q, encontrar el elemento de S más cercano a q.
Entre todas las triangulaciones encontrar la más equilátera posible
Triangulación equiláteraTriangulación equilátera
Envolvente convexaEnvolvente convexa
Dada una serie de puntos encontrar el menor convexo que los contieneDada una serie de puntos encontrar el menor convexo que los contiene
O(n2)
Fuerza
bru
ta
O(n2)
O(2n)
?
O(n)
?
O(n)D
iagra
ma d
e V
oro
noi
O(n)
O(n)
?
O(log n)
?
![Page 56: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/56.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3
![Page 57: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/57.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3
![Page 58: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/58.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3
![Page 59: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/59.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3
![Page 60: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/60.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3
![Page 61: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/61.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3
Entre muchos aviones en una pantalla encontrar los dos más cercanospuntos en el planopuntos en el planoEl par más
cercano
El par más cercano
Entre muchos linces en un terreno encontrar el más cercano a cada cualpuntos en el planopuntos en el planoTodos los pares más cercanos
Todos los pares más cercanos
Conectar n puntos de tal forma que la longitud de la red sea mínimaÁrbol recubridor (generador) mínimo
Árbol recubridor (generador) mínimo
Vecino más cercanoVecino más cercanoDado un conjunto de puntos S y un nuevo punto q, encontrar el elemento de S más cercano a q.
Entre todas las triangulaciones encontrar la más equiláteraTriangulación equiláteraTriangulación equilátera
Envolvente convexaEnvolvente convexa
Dada una serie de puntos encontrar el menor convexo que los contieneDada una serie de puntos encontrar el menor convexo que los contiene
Dados N puntos en plano, hallar máximo círculo sin puntos en interiorDados N puntos en plano, hallar máximo círculo sin puntos en interior
O(n2)
Fuerza
bru
ta
O(n2)
O(2n)
?
O(n)
?
O(n3)
Círculo máximo vacío.Círculo máximo vacío.
O(n)D
iagra
ma d
e V
oro
noiO(n)
O(n)
?
O(log n)
?
?
![Page 62: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/62.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3
Planteamiento • "Dados N puntos en el plano, encontrar el
círculo más grande que no contenga ningún punto del conjunto cuyo centro está dentro del polígono convexo que engloba todos los puntos, es decir, dentro del cierre convexo"
LARGEST EMPTY CIRCLE(El círculo vacío mas
grande)Planteamiento
LARGEST EMPTY CIRCLE(El círculo vacío mas
grande)Planteamiento
![Page 63: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/63.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3
El punto p0 se halla a partir demax (min ( Xi – Xo )^2+(Yi – Yo )^2),
con p0 en la envolvente convexa de la nube
El punto p0 se halla a partir demax (min ( Xi – Xo )^2+(Yi – Yo )^2),
con p0 en la envolvente convexa de la nube
Problema círculo vacío es problema de localización que busca un punto lo más lejos posible de los N existentes.
Problema círculo vacío es problema de localización que busca un punto lo más lejos posible de los N existentes.
![Page 64: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/64.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3
![Page 65: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/65.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3
Teorema: El centro del círculo máximo vacío es vértice del diagrama de Voronoi correspondiente a la nube de puntos.
Teorema: El centro del círculo máximo vacío es vértice del diagrama de Voronoi correspondiente a la nube de puntos.
Teorema: El círculo vacío más grande de una nube de N puntos en el plano puede ser construido en tiempo O(NlogN).
Teorema: El círculo vacío más grande de una nube de N puntos en el plano puede ser construido en tiempo O(NlogN).
![Page 66: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/66.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3
Propiedad 1: Cada borde de Voronoi intersecta, máximo con dos lados de la envolvente convexa. Por la convexidad, la intersección de cualquier otra línea con la envolvente es un (posiblemente vacío) segmento.
Propiedad 1: Cada borde de Voronoi intersecta, máximo con dos lados de la envolvente convexa. Por la convexidad, la intersección de cualquier otra línea con la envolvente es un (posiblemente vacío) segmento.
Propiedad 2: Cada lado de la envolvente convexa intersecta, al menos, un borde de Voronoi. Cualquier lado de la envolvente convexa junta dos partes distintas de la nube que pertenecen a distintas regiones Voronoi.
Propiedad 2: Cada lado de la envolvente convexa intersecta, al menos, un borde de Voronoi. Cualquier lado de la envolvente convexa junta dos partes distintas de la nube que pertenecen a distintas regiones Voronoi.
![Page 67: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/67.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3
Entre muchos aviones en una pantalla encontrar los dos más cercanospuntos en el planopuntos en el planoEl par más
cercano
El par más cercano
Entre muchos linces en un terreno encontrar el más cercano a cada cualpuntos en el planopuntos en el planoTodos los pares más cercanos
Todos los pares más cercanos
Conectar n puntos de tal forma que la longitud de la red sea mínimaÁrbol recubridor (generador) mínimo
Árbol recubridor (generador) mínimo
Vecino más cercanoVecino más cercanoDado un conjunto de puntos S y un nuevo punto q, encontrar el elemento de S más cercano a q.
Entre todas las triangulaciones encontrar la más equiláteraTriangulación equiláteraTriangulación equilátera
Envolvente convexaEnvolvente convexa
Dada una serie de puntos encontrar el menor convexo que los contieneDada una serie de puntos encontrar el menor convexo que los contiene
Dados N puntos en plano, hallar máximo círculo sin puntos en interiorDados N puntos en plano, hallar máximo círculo sin puntos en interior
O(n2)
Fuerza
bru
ta
O(n2)
O(2n)
?
O(n)
?
O(n3)
Círculo máximo vacío.Círculo máximo vacío.
O(n)D
iagra
ma d
e V
oro
noiO(n)
O(n)
O(n)
O(log n)
O(n)
?
![Page 68: Matemática Aplicada I José Ramón Gómez Problemas de proximidad Tema 3.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b49d1a28abb57c92a977/html5/thumbnails/68.jpg)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/
jrgomez
Pro
ble
mas
de
pro
xim
idad
Pro
ble
mas
de
pro
xim
idad
Tema 3Tema 3
Entre muchos aviones en una pantalla encontrar los dos más cercanospuntos en el planopuntos en el planoEl par más
cercano
El par más cercano
Entre muchos linces en un terreno encontrar el más cercano a cada cualpuntos en el planopuntos en el planoTodos los pares más cercanos
Todos los pares más cercanos
Conectar n puntos de tal forma que la longitud de la red sea mínimaÁrbol recubridor (generador) mínimo
Árbol recubridor (generador) mínimo
Vecino más cercanoVecino más cercanoDado un conjunto de puntos S y un nuevo punto q, encontrar el elemento de S más cercano a q.
Entre todas las triangulaciones encontrar la más equiláteraTriangulación equiláteraTriangulación equilátera
Envolvente convexaEnvolvente convexa
Dada una serie de puntos encontrar el menor convexo que los contieneDada una serie de puntos encontrar el menor convexo que los contiene
Dados N puntos en plano, hallar máximo círculo sin puntos en interiorDados N puntos en plano, hallar máximo círculo sin puntos en interior
O(n2)
Fuerza
bru
ta
O(n2)
O(2n)
?
O(n)
?
O(n3)
Círculo máximo vacío.Círculo máximo vacío.
O(n)D
iagra
ma d
e V
oro
noiO(n)
O(n)
O(n)
O(log n)
O(n)
O(n)