Localización de puntos en una subdivisión del plano
description
Transcript of Localización de puntos en una subdivisión del plano
![Page 1: Localización de puntos en una subdivisión del plano](https://reader036.fdocumento.com/reader036/viewer/2022062723/56813e89550346895da8c952/html5/thumbnails/1.jpg)
Matemática Aplicada I
Clara I. Grimahttp://www.personal.us.es/grima
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
![Page 2: Localización de puntos en una subdivisión del plano](https://reader036.fdocumento.com/reader036/viewer/2022062723/56813e89550346895da8c952/html5/thumbnails/2.jpg)
Matemática Aplicada I
Clara I. Grimahttp://www.personal.us.es/grima
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
Elija su pais de destino:
![Page 3: Localización de puntos en una subdivisión del plano](https://reader036.fdocumento.com/reader036/viewer/2022062723/56813e89550346895da8c952/html5/thumbnails/3.jpg)
Matemática Aplicada I
Clara I. Grimahttp://www.personal.us.es/grima
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
Atlas cerebrales
![Page 4: Localización de puntos en una subdivisión del plano](https://reader036.fdocumento.com/reader036/viewer/2022062723/56813e89550346895da8c952/html5/thumbnails/4.jpg)
Matemática Aplicada I
Clara I. Grimahttp://www.personal.us.es/grima
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
![Page 5: Localización de puntos en una subdivisión del plano](https://reader036.fdocumento.com/reader036/viewer/2022062723/56813e89550346895da8c952/html5/thumbnails/5.jpg)
Matemática Aplicada I
Clara I. Grimahttp://www.personal.us.es/grima
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
Y como la multitud de leyes sirve muy a menudo de disculpa a los vicios, siendo un Estado mucho mejor regido cuando hay pocas, pero muy estrictamente observadas, así también, en lugar del gran número de preceptos que encierra la lógica, creí que me bastarían los cuatro siguientes, supuesto que tomase una firme y constante resolución de no dejar de observarlos una vez siquiera:
Fue el primero, no admitir como verdadera cosa alguna, como no supiese con evidencia que lo es; es decir, evitar cuidadosamente la precipitación y la prevención, y no comprender en mis juicios nada más que lo que se presentase tan clara y distintamente a mí espíritu, que no hubiese ninguna ocasión de ponerlo en duda.
El segundo, dividir cada una de las dificultades, que examinare, en cuantas partes fuere posible y en cuantas requiriese su mejor solución.
El tercero, conducir ordenadamente mis pensamientos, empezando por los objetos más simples y más fáciles de conocer, para ir ascendiendo poco a poco, gradualmente, hasta el conocimiento de los más compuestos, e incluso suponiendo un orden entre los que no se preceden naturalmente.
Y el último, hacer en todo unos recuentos tan integrales y unas revisiones tan generales, que llegase a estar seguro de no omitir nada.
Y como la multitud de leyes sirve muy a menudo de disculpa a los vicios, siendo un Estado mucho mejor regido cuando hay pocas, pero muy estrictamente observadas, así también, en lugar del gran número de preceptos que encierra la lógica, creí que me bastarían los cuatro siguientes, supuesto que tomase una firme y constante resolución de no dejar de observarlos una vez siquiera:
Fue el primero, no admitir como verdadera cosa alguna, como no supiese con evidencia que lo es; es decir, evitar cuidadosamente la precipitación y la prevención, y no comprender en mis juicios nada más que lo que se presentase tan clara y distintamente a mí espíritu, que no hubiese ninguna ocasión de ponerlo en duda.
El segundo, dividir cada una de las dificultades, que examinare, en cuantas partes fuere posible y en cuantas requiriese su mejor solución.
El tercero, conducir ordenadamente mis pensamientos, empezando por los objetos más simples y más fáciles de conocer, para ir ascendiendo poco a poco, gradualmente, hasta el conocimiento de los más compuestos, e incluso suponiendo un orden entre los que no se preceden naturalmente.
Y el último, hacer en todo unos recuentos tan integrales y unas revisiones tan generales, que llegase a estar seguro de no omitir nada.
(31 de marzo, 1596 - 11 de febrero, 1650) (31 de marzo, 1596 - 11 de febrero, 1650)
René DescarteRené Descarte
Discurso del métodoDiscurso del método
![Page 6: Localización de puntos en una subdivisión del plano](https://reader036.fdocumento.com/reader036/viewer/2022062723/56813e89550346895da8c952/html5/thumbnails/6.jpg)
Matemática Aplicada I
Clara I. Grimahttp://www.personal.us.es/grima
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
Y como la multitud de leyes sirve muy a menudo de disculpa a los vicios, siendo un Estado mucho mejor regido cuando hay pocas, pero muy estrictamente observadas, así también, en lugar del gran número de preceptos que encierra la lógica, creí que me bastarían los cuatro siguientes, supuesto que tomase una firme y constante resolución de no dejar de observarlos una vez siquiera:
Fue el primero, no admitir como verdadera cosa alguna, como no supiese con evidencia que lo es; es decir, evitar cuidadosamente la precipitación y la prevención, y no comprender en mis juicios nada más que lo que se presentase tan clara y distintamente a mí espíritu, que no hubiese ninguna ocasión de ponerlo en duda.
El segundo, dividir cada una de las dificultades, que examinare, en cuantas partes fuere posible y en cuantas requiriese su mejor solución.
El tercero, conducir ordenadamente mis pensamientos, empezando por los objetos más simples y más fáciles de conocer, para ir ascendiendo poco a poco, gradualmente, hasta el conocimiento de los más compuestos, e incluso suponiendo un orden entre los que no se preceden naturalmente.
Y el último, hacer en todo unos recuentos tan integrales y unas revisiones tan generales, que llegase a estar seguro de no omitir nada.
Y como la multitud de leyes sirve muy a menudo de disculpa a los vicios, siendo un Estado mucho mejor regido cuando hay pocas, pero muy estrictamente observadas, así también, en lugar del gran número de preceptos que encierra la lógica, creí que me bastarían los cuatro siguientes, supuesto que tomase una firme y constante resolución de no dejar de observarlos una vez siquiera:
Fue el primero, no admitir como verdadera cosa alguna, como no supiese con evidencia que lo es; es decir, evitar cuidadosamente la precipitación y la prevención, y no comprender en mis juicios nada más que lo que se presentase tan clara y distintamente a mí espíritu, que no hubiese ninguna ocasión de ponerlo en duda.
El segundo, dividir cada una de las dificultades, que examinare, en cuantas partes fuere posible y en cuantas requiriese su mejor solución.
El tercero, conducir ordenadamente mis pensamientos, empezando por los objetos más simples y más fáciles de conocer, para ir ascendiendo poco a poco, gradualmente, hasta el conocimiento de los más compuestos, e incluso suponiendo un orden entre los que no se preceden naturalmente.
Y el último, hacer en todo unos recuentos tan integrales y unas revisiones tan generales, que llegase a estar seguro de no omitir nada.
(31 de marzo, 1596 - 11 de febrero, 1650) (31 de marzo, 1596 - 11 de febrero, 1650)
René DescarteRené Descarte
Discurso del métodoDiscurso del método
![Page 7: Localización de puntos en una subdivisión del plano](https://reader036.fdocumento.com/reader036/viewer/2022062723/56813e89550346895da8c952/html5/thumbnails/7.jpg)
Matemática Aplicada I
Clara I. Grimahttp://www.personal.us.es/grima
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
![Page 8: Localización de puntos en una subdivisión del plano](https://reader036.fdocumento.com/reader036/viewer/2022062723/56813e89550346895da8c952/html5/thumbnails/8.jpg)
Matemática Aplicada I
Clara I. Grimahttp://www.personal.us.es/grima
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
![Page 9: Localización de puntos en una subdivisión del plano](https://reader036.fdocumento.com/reader036/viewer/2022062723/56813e89550346895da8c952/html5/thumbnails/9.jpg)
Matemática Aplicada I
Clara I. Grimahttp://www.personal.us.es/grima
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
![Page 10: Localización de puntos en una subdivisión del plano](https://reader036.fdocumento.com/reader036/viewer/2022062723/56813e89550346895da8c952/html5/thumbnails/10.jpg)
Matemática Aplicada I
Clara I. Grimahttp://www.personal.us.es/grima
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
![Page 11: Localización de puntos en una subdivisión del plano](https://reader036.fdocumento.com/reader036/viewer/2022062723/56813e89550346895da8c952/html5/thumbnails/11.jpg)
Matemática Aplicada I
Clara I. Grimahttp://www.personal.us.es/grima
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?
![Page 12: Localización de puntos en una subdivisión del plano](https://reader036.fdocumento.com/reader036/viewer/2022062723/56813e89550346895da8c952/html5/thumbnails/12.jpg)
Matemática Aplicada I
Clara I. Grimahttp://www.personal.us.es/grima
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
procesmiento
K veces
Algoritmo 1 0 O(n) O(kn)
Algoritmo 2 O(n log n) O(log n) O(klog n + nlog n)
![Page 13: Localización de puntos en una subdivisión del plano](https://reader036.fdocumento.com/reader036/viewer/2022062723/56813e89550346895da8c952/html5/thumbnails/13.jpg)
Matemática Aplicada I
Clara I. Grimahttp://www.personal.us.es/grima
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
![Page 14: Localización de puntos en una subdivisión del plano](https://reader036.fdocumento.com/reader036/viewer/2022062723/56813e89550346895da8c952/html5/thumbnails/14.jpg)
Matemática Aplicada I
Clara I. Grimahttp://www.personal.us.es/grima
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)
![Page 15: Localización de puntos en una subdivisión del plano](https://reader036.fdocumento.com/reader036/viewer/2022062723/56813e89550346895da8c952/html5/thumbnails/15.jpg)
Matemática Aplicada I
Clara I. Grimahttp://www.personal.us.es/grima
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
procesmiento
K veces
Algoritmo 1 0 O(n) O(kn)
Algoritmo 2 O(n log n) O(log n) O(klog n + nlog n)
![Page 16: Localización de puntos en una subdivisión del plano](https://reader036.fdocumento.com/reader036/viewer/2022062723/56813e89550346895da8c952/html5/thumbnails/16.jpg)
Matemática Aplicada I
Clara I. Grimahttp://www.personal.us.es/grima
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
![Page 17: Localización de puntos en una subdivisión del plano](https://reader036.fdocumento.com/reader036/viewer/2022062723/56813e89550346895da8c952/html5/thumbnails/17.jpg)
Matemática Aplicada I
Clara I. Grimahttp://www.personal.us.es/grima
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 1.- Localizar un punto en el interior del polígono
![Page 18: Localización de puntos en una subdivisión del plano](https://reader036.fdocumento.com/reader036/viewer/2022062723/56813e89550346895da8c952/html5/thumbnails/18.jpg)
Matemática Aplicada I
Clara I. Grimahttp://www.personal.us.es/grima
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.
![Page 19: Localización de puntos en una subdivisión del plano](https://reader036.fdocumento.com/reader036/viewer/2022062723/56813e89550346895da8c952/html5/thumbnails/19.jpg)
Matemática Aplicada I
Clara I. Grimahttp://www.personal.us.es/grima
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)
![Page 20: Localización de puntos en una subdivisión del plano](https://reader036.fdocumento.com/reader036/viewer/2022062723/56813e89550346895da8c952/html5/thumbnails/20.jpg)
Matemática Aplicada I
Clara I. Grimahttp://www.personal.us.es/grima
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.
![Page 21: Localización de puntos en una subdivisión del plano](https://reader036.fdocumento.com/reader036/viewer/2022062723/56813e89550346895da8c952/html5/thumbnails/21.jpg)
Matemática Aplicada I
Clara I. Grimahttp://www.personal.us.es/grima
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.
![Page 22: Localización de puntos en una subdivisión del plano](https://reader036.fdocumento.com/reader036/viewer/2022062723/56813e89550346895da8c952/html5/thumbnails/22.jpg)
Matemática Aplicada I
Clara I. Grimahttp://www.personal.us.es/grima
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.
![Page 23: Localización de puntos en una subdivisión del plano](https://reader036.fdocumento.com/reader036/viewer/2022062723/56813e89550346895da8c952/html5/thumbnails/23.jpg)
Matemática Aplicada I
Clara I. Grimahttp://www.personal.us.es/grima
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)
![Page 24: Localización de puntos en una subdivisión del plano](https://reader036.fdocumento.com/reader036/viewer/2022062723/56813e89550346895da8c952/html5/thumbnails/24.jpg)
Matemática Aplicada I
Clara I. Grimahttp://www.personal.us.es/grima
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.
![Page 25: Localización de puntos en una subdivisión del plano](https://reader036.fdocumento.com/reader036/viewer/2022062723/56813e89550346895da8c952/html5/thumbnails/25.jpg)
Matemática Aplicada I
Clara I. Grimahttp://www.personal.us.es/grima
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
![Page 26: Localización de puntos en una subdivisión del plano](https://reader036.fdocumento.com/reader036/viewer/2022062723/56813e89550346895da8c952/html5/thumbnails/26.jpg)
Matemática Aplicada I
Clara I. Grimahttp://www.personal.us.es/grima
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
![Page 27: Localización de puntos en una subdivisión del plano](https://reader036.fdocumento.com/reader036/viewer/2022062723/56813e89550346895da8c952/html5/thumbnails/27.jpg)
Matemática Aplicada I
Clara I. Grimahttp://www.personal.us.es/grima
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
![Page 28: Localización de puntos en una subdivisión del plano](https://reader036.fdocumento.com/reader036/viewer/2022062723/56813e89550346895da8c952/html5/thumbnails/28.jpg)
Matemática Aplicada I
Clara I. Grimahttp://www.personal.us.es/grima
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
![Page 29: Localización de puntos en una subdivisión del plano](https://reader036.fdocumento.com/reader036/viewer/2022062723/56813e89550346895da8c952/html5/thumbnails/29.jpg)
Matemática Aplicada I
Clara I. Grimahttp://www.personal.us.es/grima
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
![Page 30: Localización de puntos en una subdivisión del plano](https://reader036.fdocumento.com/reader036/viewer/2022062723/56813e89550346895da8c952/html5/thumbnails/30.jpg)
Matemática Aplicada I
Clara I. Grimahttp://www.personal.us.es/grima
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
![Page 31: Localización de puntos en una subdivisión del plano](https://reader036.fdocumento.com/reader036/viewer/2022062723/56813e89550346895da8c952/html5/thumbnails/31.jpg)
Matemática Aplicada I
Clara I. Grimahttp://www.personal.us.es/grima
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
![Page 32: Localización de puntos en una subdivisión del plano](https://reader036.fdocumento.com/reader036/viewer/2022062723/56813e89550346895da8c952/html5/thumbnails/32.jpg)
Matemática Aplicada I
Clara I. Grimahttp://www.personal.us.es/grima
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)
![Page 33: Localización de puntos en una subdivisión del plano](https://reader036.fdocumento.com/reader036/viewer/2022062723/56813e89550346895da8c952/html5/thumbnails/33.jpg)
Matemática Aplicada I
Clara I. Grimahttp://www.personal.us.es/grima
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 banda4.- 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
![Page 34: Localización de puntos en una subdivisión del plano](https://reader036.fdocumento.com/reader036/viewer/2022062723/56813e89550346895da8c952/html5/thumbnails/34.jpg)
Matemática Aplicada I
Clara I. Grimahttp://www.personal.us.es/grima
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
![Page 35: Localización de puntos en una subdivisión del plano](https://reader036.fdocumento.com/reader036/viewer/2022062723/56813e89550346895da8c952/html5/thumbnails/35.jpg)
Matemática Aplicada I
Clara I. Grimahttp://www.personal.us.es/grima
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.
![Page 36: Localización de puntos en una subdivisión del plano](https://reader036.fdocumento.com/reader036/viewer/2022062723/56813e89550346895da8c952/html5/thumbnails/36.jpg)
Matemática Aplicada I
Clara I. Grimahttp://www.personal.us.es/grima
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.
![Page 37: Localización de puntos en una subdivisión del plano](https://reader036.fdocumento.com/reader036/viewer/2022062723/56813e89550346895da8c952/html5/thumbnails/37.jpg)
Matemática Aplicada I
Clara I. Grimahttp://www.personal.us.es/grima
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
http://www.ual.es/~jcaceres/ArtGallery/portada.htm
http://www.cs.mcgill.ca/~thierry/artgallery.html
![Page 38: Localización de puntos en una subdivisión del plano](https://reader036.fdocumento.com/reader036/viewer/2022062723/56813e89550346895da8c952/html5/thumbnails/38.jpg)
Matemática Aplicada I
Clara I. Grimahttp://www.personal.us.es/grima
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
![Page 39: Localización de puntos en una subdivisión del plano](https://reader036.fdocumento.com/reader036/viewer/2022062723/56813e89550346895da8c952/html5/thumbnails/39.jpg)
Matemática Aplicada I
Clara I. Grimahttp://www.personal.us.es/grima
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
![Page 40: Localización de puntos en una subdivisión del plano](https://reader036.fdocumento.com/reader036/viewer/2022062723/56813e89550346895da8c952/html5/thumbnails/40.jpg)
Matemática Aplicada I
Clara I. Grimahttp://www.personal.us.es/grima
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
![Page 41: Localización de puntos en una subdivisión del plano](https://reader036.fdocumento.com/reader036/viewer/2022062723/56813e89550346895da8c952/html5/thumbnails/41.jpg)
Matemática Aplicada I
Clara I. Grimahttp://www.personal.us.es/grima
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
![Page 42: Localización de puntos en una subdivisión del plano](https://reader036.fdocumento.com/reader036/viewer/2022062723/56813e89550346895da8c952/html5/thumbnails/42.jpg)
Matemática Aplicada I
Clara I. Grimahttp://www.personal.us.es/grima
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
![Page 43: Localización de puntos en una subdivisión del plano](https://reader036.fdocumento.com/reader036/viewer/2022062723/56813e89550346895da8c952/html5/thumbnails/43.jpg)
Matemática Aplicada I
Clara I. Grimahttp://www.personal.us.es/grima
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
![Page 44: Localización de puntos en una subdivisión del plano](https://reader036.fdocumento.com/reader036/viewer/2022062723/56813e89550346895da8c952/html5/thumbnails/44.jpg)
Matemática Aplicada I
Clara I. Grimahttp://www.personal.us.es/grima
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
![Page 45: Localización de puntos en una subdivisión del plano](https://reader036.fdocumento.com/reader036/viewer/2022062723/56813e89550346895da8c952/html5/thumbnails/45.jpg)
Matemática Aplicada I
Clara I. Grimahttp://www.personal.us.es/grima
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
![Page 46: Localización de puntos en una subdivisión del plano](https://reader036.fdocumento.com/reader036/viewer/2022062723/56813e89550346895da8c952/html5/thumbnails/46.jpg)
Matemática Aplicada I
Clara I. Grimahttp://www.personal.us.es/grima
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
![Page 47: Localización de puntos en una subdivisión del plano](https://reader036.fdocumento.com/reader036/viewer/2022062723/56813e89550346895da8c952/html5/thumbnails/47.jpg)
Matemática Aplicada I
Clara I. Grimahttp://www.personal.us.es/grima
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
![Page 48: Localización de puntos en una subdivisión del plano](https://reader036.fdocumento.com/reader036/viewer/2022062723/56813e89550346895da8c952/html5/thumbnails/48.jpg)
Matemática Aplicada I
Clara I. Grimahttp://www.personal.us.es/grima
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
![Page 49: Localización de puntos en una subdivisión del plano](https://reader036.fdocumento.com/reader036/viewer/2022062723/56813e89550346895da8c952/html5/thumbnails/49.jpg)
Matemática Aplicada I
Clara I. Grimahttp://www.personal.us.es/grima
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
Tiempo de ejecución del método de las bandas: O(logn)
Carga de datos:O(n2) (normalmente, O(n3/2)
Mejora en la carga de datos:
Mapas trapezoidales
Método de la cadena
![Page 50: Localización de puntos en una subdivisión del plano](https://reader036.fdocumento.com/reader036/viewer/2022062723/56813e89550346895da8c952/html5/thumbnails/50.jpg)
Matemática Aplicada I
Clara I. Grimahttp://www.personal.us.es/grima
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.
![Page 51: Localización de puntos en una subdivisión del plano](https://reader036.fdocumento.com/reader036/viewer/2022062723/56813e89550346895da8c952/html5/thumbnails/51.jpg)
Matemática Aplicada I
Clara I. Grimahttp://www.personal.us.es/grima
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
EJERCICIOS
![Page 52: Localización de puntos en una subdivisión del plano](https://reader036.fdocumento.com/reader036/viewer/2022062723/56813e89550346895da8c952/html5/thumbnails/52.jpg)
Matemática Aplicada I
Clara I. Grimahttp://www.personal.us.es/grima
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
Ejercicios1.Dar un ejemplo de un pslg en el que el método de la banda requiera un
preprocesamiento O(n2). 2.Dar un ejemplo en el que el método de la banda requiera un
preprocesamiento O(n). 3.Diseñar un algoritmo que resuelva el siguiente problema:
Dada una colección P de n puntos en el plano, encontrar un valor l>0 tal que si transformamos cada punto (x,y) de P en el (x+ly,y), el orden de los puntos de P no cambia en la dirección del eje de las X.
4.Un corte en un rectángulo es en guillotina si es paralelo a uno de los lados y es maximal en el subrectángulo en el que es dado. Esto es: el primer corte ha de ir de lado a lado y divide el rectángulo en dos subrectángulos, el siguiente corte también ha de ir de lado a lado en alguno de los subrectángulos obtenidos en el paso anterior y así sucesivamente.
• Diseñar un algoritmo que determine si un rectángulo está dividido por cortes en guillotina.
• Diseñar un algoritmo que determine, dado un rectángulo dividido por cortes en guillotina, el orden en el que se han producido dichos cortes.
• Diseñar un algoritmo que localice un punto en un rectángulo dividido por cortes en guillotina.
![Page 53: Localización de puntos en una subdivisión del plano](https://reader036.fdocumento.com/reader036/viewer/2022062723/56813e89550346895da8c952/html5/thumbnails/53.jpg)
Matemática Aplicada I
Clara I. Grimahttp://www.personal.us.es/grima
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
EJERCICIO 1Dar un ejemplo de un pslg en el que el método de la banda requiera un preprocesamiento O(n2).
EJERCICIO 3Diseñar un algoritmo que resuelva el siguiente problema:Dada una colección P de n puntos en el plano, encontrar un valor l>0 tal que si transformamos cada punto (x,y) de P en el (x+ly,y), el orden de los puntos de P no cambia en la dirección del eje de las X.