localización de puntos en una subdivisión del plano
Post on 12-Jan-2016
34 Views
Preview:
DESCRIPTION
TRANSCRIPT
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/jrgomez
Geometría Computacional
Localización
Planteamiento del problema
Casos simples
Método de la banda
Localización
Planteamiento del problema
Casos simples
Método de la banda
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/jrgomez
Geometría Computacional
Localización
Planteamiento del problema
Casos simples
Método de la banda
Localización
Planteamiento del problema
Casos simples
Método de la banda
PSLG
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/jrgomez
Geometría Computacional
Localización
Planteamiento del problema
Casos simples
Método de la banda
Localización
Planteamiento del problema
Casos simples
Método de la banda
PSLG
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/jrgomez
Geometría Computacional
Localización
Planteamiento del problema
Casos simples
Método de la banda
Localización
Planteamiento del problema
Casos simples
Método de la banda
PSLG
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/jrgomez
Geometría Computacional
Localización
Planteamiento del problema
Casos simples
Método de la banda
Localización
Planteamiento del problema
Casos simples
Método de la banda
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/jrgomez
Geometría Computacional
Localización
Planteamiento del problema
Casos simples
Método de la banda
Localización
Planteamiento del problema
Casos simples
Método de la banda
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/jrgomez
Geometría Computacional
Localización
Planteamiento del problema
Casos simples
Método de la banda
Localización
Planteamiento del problema
Casos simples
Método de la banda
Teorema 2.1: Toda línea poligonal cerrada C divide el plano en dos regiones, una acotada y la otra no. Además, se puede determinar si un punto p está en la región acotada contando el número de veces que cualquier semirrecta que comienza en p atraviesa a C; p estará en dicha región si y sólo si dicho número es impar.
Teorema 2.1: Toda línea poligonal cerrada C divide el plano en dos regiones, una acotada y la otra no. Además, se puede determinar si un punto p está en la región acotada contando el número de veces que cualquier semirrecta que comienza en p atraviesa a C; p estará en dicha región si y sólo si dicho número es impar.
Corolario 2.1: Es posible determinar si un punto está en el interior de una región acotada por una línea poligonal simple cerrada en tiempo O(n).
Corolario 2.1: Es posible determinar si un punto está en el interior de una región acotada por una línea poligonal simple cerrada en tiempo O(n).
¿Es óptimo?¿Es óptimo?
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/jrgomez
Geometría Computacional
Localización
Planteamiento del problema
Casos simples
Método de la banda
Localización
Planteamiento del problema
Casos simples
Método de la banda
¿La repetición k veces de un algoritmo óptimo es la estrategia óptima?
¿La repetición k veces de un algoritmo óptimo es la estrategia óptima?
preprocesamiento
procesamiento
K veces
Algoritmo 1
0 O(n) O(kn)
Algoritmo 2
O(n log n) O(log n) O(klog n + nlog n)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/jrgomez
Geometría Computacional
Localización
Planteamiento del problema
Casos simples
Método de la banda
Localización
Planteamiento del problema
Casos simples
Método de la banda
1 2 5 6 8 9 10 11 13
Insertar un número en una lista ordenada
(Búsqueda binaria)
44
1 2 5 6 8 9 10 11 13
1 2 5 6
1 2
¿4 < 5?NOSI
¿4 < 2?NOSI
NOSI¿4 < 8?
4 está inmediatamente a la derecha de 2
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/jrgomez
Geometría Computacional
Localización
Planteamiento del problema
Casos simples
Método de la banda
Localización
Planteamiento del problema
Casos simples
Método de la banda
Ordenar n números O(nlog n)
Insertar un número en una lista
ordenada (Búsqueda binaria)
O(log n)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/jrgomez
Geometría Computacional
Localización
Planteamiento del problema
Casos simples
Método de la banda
Localización
Planteamiento del problema
Casos simples
Método de la banda
¿La repetición n veces de un algoritmo óptimo es la estrategia óptima?
¿La repetición n veces de un algoritmo óptimo es la estrategia óptima?
preprocesamiento
procesamiento
K veces
Algoritmo 1
0 O(n) O(kn)
Algoritmo 2
O(n log n) O(log n) O(klog n + nlog n)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/jrgomez
Geometría Computacional
Localización
Planteamiento del problema
Casos simples
Método de la banda
Localización
Planteamiento del problema
Casos simples
Método de la banda
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/jrgomez
Geometría Computacional
Localización
Planteamiento del problema
Casos simples
Método de la banda
Localización
Planteamiento del problema
Casos simples
Método de la banda
1.- Localizar un punto en el interior del polígono1.- Localizar un punto en el interior del polígono
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/jrgomez
Geometría Computacional
Localización
Planteamiento del problema
Casos simples
Método de la banda
Localización
Planteamiento del problema
Casos simples
Método de la banda
1.- Localizar un punto en el interior del polígono
2.- Trazar semirrectas desde ese punto pasando por los vértices del polígono.
3.- Ordenar dichas semirrectas según su pendiente.
1.- Localizar un punto en el interior del polígono
2.- Trazar semirrectas desde ese punto pasando por los vértices del polígono.
3.- Ordenar dichas semirrectas según su pendiente.
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/jrgomez
Geometría Computacional
Localización
Planteamiento del problema
Casos simples
Método de la banda
Localización
Planteamiento del problema
Casos simples
Método de la banda
1.- Localizar un punto en el interior del polígono
2.- Trazar semirrectas desde ese punto pasando por los vértices del polígono.
3.- Ordenar dichas semirrectas según su pendiente.
1.- Localizar un punto en el interior del polígono
2.- Trazar semirrectas desde ese punto pasando por los vértices del polígono.
3.- Ordenar dichas semirrectas según su pendiente.
O(n log n)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/jrgomez
Geometría Computacional
Localización
Planteamiento del problema
Casos simples
Método de la banda
Localización
Planteamiento del problema
Casos simples
Método de la banda
4.- Localizamos en qué región angular estamos.
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/jrgomez
Geometría Computacional
Localización
Planteamiento del problema
Casos simples
Método de la banda
Localización
Planteamiento del problema
Casos simples
Método de la banda
4.- Localizamos en qué región angular estamos.
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/jrgomez
Geometría Computacional
Localización
Planteamiento del problema
Casos simples
Método de la banda
Localización
Planteamiento del problema
Casos simples
Método de la banda
4.- Localizamos en qué región angular estamos.
5.- En dicha región determinamos si estamos dentro o fuera del polígono.
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/jrgomez
Geometría Computacional
Localización
Planteamiento del problema
Casos simples
Método de la banda
Localización
Planteamiento del problema
Casos simples
Método de la banda
4.- Localizamos en qué región angular estamos.
5.- En dicha región determinamos si estamos dentro o fuera del polígono.
O(log n)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/jrgomez
Geometría Computacional
Localización
Planteamiento del problema
Casos simples
Método de la banda
Localización
Planteamiento del problema
Casos simples
Método de la banda
4.- Localizamos en qué región angular estamos.
5.- En dicha región determinamos si estamos dentro o fuera del polígono.
O(log n)
1.- Localizar un punto en el interior del polígono
2.- Trazar semirrectas desde ese punto pasando por los vértices del polígono.
3.- Ordenar dichas semirrectas según su pendiente.
1.- Localizar un punto en el interior del polígono
2.- Trazar semirrectas desde ese punto pasando por los vértices del polígono.
3.- Ordenar dichas semirrectas según su pendiente.
O(n log n)
Teorema 2.2: Es posible determinar si un punto está en el interior de una región acotada por un poligono convexo en tiempo O(log n), con O(n log n) de preprocesamiento.
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/jrgomez
Geometría Computacional
Localización
Planteamiento del problema
Casos simples
Método de la banda
Localización
Planteamiento del problema
Casos simples
Método de la banda
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/jrgomez
Geometría Computacional
Localización
Planteamiento del problema
Casos simples
Método de la banda
Localización
Planteamiento del problema
Casos simples
Método de la banda
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/jrgomez
Geometría Computacional
Localización
Planteamiento del problema
Casos simples
Método de la banda
Localización
Planteamiento del problema
Casos simples
Método de la banda
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/jrgomez
Geometría Computacional
Localización
Planteamiento del problema
Casos simples
Método de la banda
Localización
Planteamiento del problema
Casos simples
Método de la banda
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/jrgomez
Geometría Computacional
Localización
Planteamiento del problema
Casos simples
Método de la banda
Localización
Planteamiento del problema
Casos simples
Método de la banda
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/jrgomez
Geometría Computacional
Localización
Planteamiento del problema
Casos simples
Método de la banda
Localización
Planteamiento del problema
Casos simples
Método de la banda
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/jrgomez
Geometría Computacional
Localización
Planteamiento del problema
Casos simples
Método de la banda
Localización
Planteamiento del problema
Casos simples
Método de la banda
Decimos que p está en el núcleo de P (p ker P), si para todo q P se verifica que el segmento pq está incluido en el interior de P.
Lema: El núcleo de un polígono puede calcularse en tiempo O(n log n)
4.- Localizamos en qué región angular estamos.
5.- En dicha región determinamos si estamos dentro o fuera del polígono.
O(log n)
1.- Localizar un punto en el interior del polígono
2.- Trazar semirrectas desde ese punto pasando por los vértices del polígono.
3.- Ordenar dichas semirrectas según su pendiente.
1.- Localizar un punto en el interior del polígono
2.- Trazar semirrectas desde ese punto pasando por los vértices del polígono.
3.- Ordenar dichas semirrectas según su pendiente.
O(n log n)
núcleo
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/jrgomez
Geometría Computacional
Localización
Planteamiento del problema
Casos simples
Método de la banda
Localización
Planteamiento del problema
Casos simples
Método de la banda
Teorema: La intersección de n semiplanos puede calcularse en tiempo O(n log n)
Lema: El núcleo de un polígono puede calcularse en tiempo O(n log n)
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/jrgomez
Geometría Computacional
Localización
Planteamiento del problema
Casos simples
Método de la banda
Localización
Planteamiento del problema
Casos simples
Método de la banda
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/jrgomez
Geometría Computacional
Localización
Planteamiento del problema
Casos simples
Método de la banda
Localización
Planteamiento del problema
Casos simples
Método de la banda
Problema de la Galería de Arte
En 1973, Víctor Klee planteó el problema de determinar el mínimo número de guardias suficientes para cubrir el interior de una galería de arte con un número n de paredes.
En 1975, Chvatal dio la respuesta a dicha pregunta y en 1978 Fisk dio otra demostración.
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/jrgomez
Geometría Computacional
Localización
Planteamiento del problema
Casos simples
Método de la banda
Localización
Planteamiento del problema
Casos simples
Método de la banda
Teorema: n/3 guardianes son siempre suficientes y ocasionalmente necesarios para vigilar un polígono de n lados.
G(P), el menor número de puntos necesarios para vigilar todo P.
g(n), el mayor valor de G(P) para cada polígono, P, de n vértices.
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/jrgomez
Geometría Computacional
Localización
Planteamiento del problema
Casos simples
Método de la banda
Localización
Planteamiento del problema
Casos simples
Método de la banda
Demostración:
Suficiencia
1.Triangular el polígono, añadiendo diagonales internas hasta que no se puedan añadir más.2.El grafo es 3-coloreable.3.Ubicar a los guardias en los vértices del color menos repetido.
En la triangulación de P cada punto está dentro de algún triángulo, como los triángulos son polígonos convexos, cada punto de P queda vigilado al menos por uno de estos guardias. Así, g(n)≤ n/3.
Necesidad
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/jrgomez
Geometría Computacional
Localización
Planteamiento del problema
Casos simples
Método de la banda
Localización
Planteamiento del problema
Casos simples
Método de la banda
PSLG
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/jrgomez
Geometría Computacional
Localización
Planteamiento del problema
Casos simples
Método de la banda
Localización
Planteamiento del problema
Casos simples
Método de la banda
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/jrgomez
Geometría Computacional
Localización
Planteamiento del problema
Casos simples
Método de la banda
Localización
Planteamiento del problema
Casos simples
Método de la banda
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/jrgomez
Geometría Computacional
Localización
Planteamiento del problema
Casos simples
Método de la banda
Localización
Planteamiento del problema
Casos simples
Método de la banda
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/jrgomez
Geometría Computacional
Localización
Planteamiento del problema
Casos simples
Método de la banda
Localización
Planteamiento del problema
Casos simples
Método de la banda
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/jrgomez
Geometría Computacional
Localización
Planteamiento del problema
Casos simples
Método de la banda
Localización
Planteamiento del problema
Casos simples
Método de la banda
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/jrgomez
Geometría Computacional
Localización
Planteamiento del problema
Casos simples
Método de la banda
Localización
Planteamiento del problema
Casos simples
Método de la banda
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/jrgomez
Geometría Computacional
Localización
Planteamiento del problema
Casos simples
Método de la banda
Localización
Planteamiento del problema
Casos simples
Método de la banda
• Rectas horizontales por los puntos.
• Ordenar las rectas por ordenada.
• Localizar la banda en la que está el punto.
• Localizar los dos segmentos entre los que se
encuentra el punto.
• Ordenar los segmentos en cada banda. Pre
pro
ces
amie
nto
El método de las bandas
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/jrgomez
Geometría Computacional
Localización
Planteamiento del problema
Casos simples
Método de la banda
Localización
Planteamiento del problema
Casos simples
Método de la banda
• Rectas horizontales por los puntos.
• Ordenar las rectas por ordenada.
• Localizar la banda en la que está el punto.
• Localizar los dos segmentos entre los que se
encuentra el punto.
• Ordenar los segmentos en cada banda. Pre
pro
ces
amie
nto
El método de las bandas
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/jrgomez
Geometría Computacional
Localización
Planteamiento del problema
Casos simples
Método de la banda
Localización
Planteamiento del problema
Casos simples
Método de la banda
• Rectas horizontales por los puntos.
• Ordenar las rectas por ordenada.
• Localizar la banda en la que está el punto.
• Localizar los dos segmentos entre los que
se encuentra el punto.
• Ordenar los segmentos en cada banda. Pre
pro
ces
amie
nto
n2log (n)
log (n)
El método de las bandas
Matemática Aplicada I
José Ramón Gómezhttp://www.personal.us.es/jrgomez
Geometría Computacional
Localización
Planteamiento del problema
Casos simples
Método de la banda
Localización
Planteamiento del problema
Casos simples
Método de la banda
Bibliografía
Computational Geometry: an introduction.F. P. Preparata y M. I. Shamos. Springer-Verlag, 1985.
Computational Geometry in C.J. O’Rourke. Cambridge University Press, 1998.
top related