localización de puntos en una subdivisión del plano

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


Casos simples

Método de la banda




Localización


Casos simples

Método de la banda

Localización


Casos simples

Método de la banda

PSLG




Localización


Casos simples

Método de la banda

Localización


Casos simples

Método de la banda




Localización


Casos simples

Método de la banda

Localización


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?




Localización


Casos simples

Método de la banda

Localización


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)




Localización


Casos simples

Método de la banda

Localización


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




Localización


Casos simples

Método de la banda

Localización


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)




Localización


Casos simples

Método de la banda

Localización


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)




Localización


Casos simples

Método de la banda

Localización


Casos simples

Método de la banda




Localización


Casos simples

Método de la banda

Localización


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




Localización


Casos simples

Método de la banda

Localización


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.







Localización


Casos simples

Método de la banda

Localización


Casos simples

Método de la banda







O(n log n)




Localización


Casos simples

Método de la banda

Localización


Casos simples

Método de la banda

4.- Localizamos en qué región angular estamos.




Localización


Casos simples

Método de la banda

Localización


Casos simples

Método de la banda


5.- En dicha región determinamos si estamos dentro o fuera del polígono.




Localización


Casos simples

Método de la banda

Localización


Casos simples

Método de la banda



O(log n)




Localización


Casos simples

Método de la banda

Localización


Casos simples

Método de la banda



O(log n)







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.




Localización


Casos simples

Método de la banda

Localización


Casos simples

Método de la banda




Localización


Casos simples

Método de la banda

Localización


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)



O(log n)







O(n log n)

núcleo




Localización


Casos simples

Método de la banda

Localización


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)




Localización


Casos simples

Método de la banda

Localización


Casos simples

Método de la banda




Localización


Casos simples

Método de la banda

Localización


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.




Localización


Casos simples

Método de la banda

Localización


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.




Localización


Casos simples

Método de la banda

Localización


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




Localización


Casos simples

Método de la banda

Localización


Casos simples

Método de la banda

PSLG




Localización


Casos simples

Método de la banda

Localización


Casos simples

Método de la banda




Localización


Casos simples

Método de la banda

Localización


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




Localización


Casos simples

Método de la banda

Localización


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




Localización


Casos simples

Método de la banda

Localización


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.

localización de puntos en una subdivisión del plano

Documents