![Page 1: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/1.jpg)
VISIBILIDAD E ILUMINACIÓN
Gregorio Hernández Peñalver
Octubre 2002
Facultad de InformáticaUPM
CACIC 2002
![Page 2: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/2.jpg)
2
Planificación de movimientos
![Page 3: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/3.jpg)
3
Rutas de vigilancia
![Page 4: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/4.jpg)
4
¿Cuántas luces? ¿Cuántos guardias?
PROBLEMA DE LAS GALERÍAS DE ARTE
GALERÍAS DE ARTE
![Page 5: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/5.jpg)
5
Colocar el menor nº de guardias PROB. ALGORÍTMICO
Dado n, hallar el nº de guardias suficientes para vigilar cualquier polígono de n lados PROB. COMBINATORIO
Colocar ese nº de guardias PROB. ALGORÍTMICO
GALERÍAS DE ARTE
NP-completo
![Page 6: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/6.jpg)
6
PROB. COMBINATORIO
1. TRIANGULAR
2. COLOREAR CON 3 COLORES
GALERÍAS DE ARTE
![Page 7: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/7.jpg)
7
PROB. COMBINATORIO
1. TRIANGULAR
2. COLOREAR CON 3 COLORES
3. PONER GUARDIAS EN EL COLOR MENOS FRECUENTE
n/3 guardias siempre son suficientes
GALERÍAS DE ARTE
![Page 8: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/8.jpg)
8
Teorema (Chvátal, 1978)n/3 guardias siempre son suficientes y a veces necesarios para vigilar cualquier polígono de n lados
GALERÍAS DE ARTE
![Page 9: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/9.jpg)
9
Variantes del Problema de las Galerías de Arte
• Diferentes recintos• Diferentes formas de mirar o iluminar
Guardias lado Reflectores
![Page 10: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/10.jpg)
10
Problemas abiertos
Conjetura (Toussaint, 1983)n/4 guardias lado siempre son suficientes y a veces necesarios para vigilar cualquier polígono de n lados (salvo para dos polígonos)
![Page 11: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/11.jpg)
11
REFLECTORES IGUALES
Se dispone de n reflectores de igual amplitud , uno por cadavértice. ¿Cuál es la menor amplitud necesaria para iluminar todoel polígono?
Si colocamos n reflectores de amplitud , uno por vértice, el polígono queda iluminado
![Page 12: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/12.jpg)
12
REFLECTORES IGUALES
Conjetura (Urrutia) 2
Teorema (O’Rourke, Xu, 1994)
Existen polígonos que no se iluminan con reflectores de amplitud/2 colocados uno en cada vértice
Teorema (ECOUX, 1995)
Para todo > 0 existen polígonos simples que NO puedeniluminarse con reflectores de amplitud - , colocadosuno en cada vértice
![Page 13: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/13.jpg)
13
Existen polígonos que no se iluminan con reflectores de amplitud/2 colocados uno en cada vértice
![Page 14: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/14.jpg)
14
REFLECTORES DE AMPLITUD
Teorema (C. Tóth, 2000, 2002)
Cualquier polígono de n lados puede iluminarse con, a lo más, los siguientes reflectores de amplitud n / 3 situados en puntos, n / 2 situados en vértices y2n k / 3 situados en vértices y alineados
![Page 15: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/15.jpg)
15
PSEUDOTRIANGULACIÓN
Pseudotriángulos
![Page 16: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/16.jpg)
16
POLÍGONO DE VISIBILIDAD
Dado P polígono, x punto de P, Vis(x,P)
![Page 17: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/17.jpg)
17
POLÍGONO DE VISIBILIDAD
Se recorren los vértices del polígono en orden
x
vi-1
vivi+1
vk
“En espera”
s
x
vi-1
“Adelante”
vivi+1
![Page 18: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/18.jpg)
18
POLÍGONO DE VISIBILIDAD
Se recorren los vértices del polígono en orden
x
vi-1
“Atrás”
vi
vi+1
s
x
vi+1
vi
s
Complejidad O(n)
![Page 19: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/19.jpg)
19
POLÍGONO DE VISIBILIDAD
Hallar x tal que:Vis(x,P) área máximaVis(x,P) área mínima
MaxVis Problem Vértices y lados, Ntafos, Tsoukalas (1991)Puntos ¿?
MinVis Problem Polígonos ortogonales, Gewali (1996)
![Page 20: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/20.jpg)
20
CAMINOS GEODÉSICOS EN UN POLÍGONO
![Page 21: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/21.jpg)
21
CAMINOS GEODÉSICOS EN UN POLÍGONO
s
t
![Page 22: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/22.jpg)
22
CAMINOS GEODÉSICOS EN UN POLÍGONO
a
x
u
vEmbudo
Camino mínimo desde s hasta cada vértice del polígono(árbol de caminos mínimos)uv diagonal o lado, a antecesor común
C(a,u)
C(a,v)
x
![Page 23: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/23.jpg)
23
CAMINOS GEODÉSICOS EN UN POLÍGONO
![Page 24: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/24.jpg)
24
CAMINOS GEODÉSICOS EN UN POLÍGONO
e
Camino de s a t
t
Embudo con tapa el lado e que contiene al punto t
Complejidad O(n)tras triangulación
![Page 25: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/25.jpg)
25
CAMINOS GEODÉSICOS EN UN POLÍGONO
¿Y si repetimos la pregunta?• Con el mismo origen sÁrbol de caminos desde s, descompone el polígono en regiones con “casi” el mismo camino
Estructura O(n) Tiempo de consulta O(logn)
![Page 26: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/26.jpg)
26
POLÍGONO DE VISIBILIDAD DESDE UN LADO
e
Vis(e,P)
![Page 27: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/27.jpg)
27
POLÍGONO DE VISIBILIDAD DESDE UN LADO
Vértices de Vis(e,P)
- vértices de P- sombras de rayos que emanan de A ó B- sombras de puntos interiores de e
A Be
![Page 28: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/28.jpg)
28
POLÍGONO DE VISIBILIDAD DESDE UN LADO
CD
A Be
e'Si e’ es visible“reloj de arena”Cam(A,C), Cam(B,D)
X
Z Y
W
![Page 29: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/29.jpg)
29
POLÍGONO DE VISIBILIDAD DESDE UN LADO
CD
A Be
e'Si e’ es visible“reloj de arena”Cam(A,C), Cam(B,D)
X
Z Y
W Árbol de caminos mínimos desde A
![Page 30: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/30.jpg)
30
POLÍGONO DE VISIBILIDAD DESDE UN LADO
CD
A Be
e'Si e’ es visible“reloj de arena”Cam(A,C), Cam(B,D)
X
Z Y
W Árbol de caminos mínimos desde B
X, W ápices de los embudos del lado e’Y, Z vértices comunes de los embudos
Complejidad O(n)
![Page 31: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/31.jpg)
31
CAMINOS “LINK” EN UN POLÍGONO
O(n) si P triangulado
distL( , )=3
![Page 32: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/32.jpg)
32
DISTANCIA “LINK” EN UN POLÍGONO
x
12
3
34
2
3
3
Partición por ventanas
• Construcción de polígonos de visibilidad O(n)• Detección de la región O(n)
![Page 33: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/33.jpg)
33
DISTANCIA “LINK” EN UN POLÍGONO
x
12
3
34
2
3
3
Distancias desde x fijoÁrbol de ventanas (Suri, 90)
• Tamaño de la estructura O(n)• Tiempo de consulta O(logn)
e1
e2
e4
e3
e5
e7
e6x
e1 e2
e6 e7e3e4
e5
Si x desconocido
• Tamaño de la estructura O(n3)• Tiempo de consulta O(logn)
![Page 34: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/34.jpg)
34
CAMINOS “LINK” EN UN POLÍGONO
Centro-link del polígonoO(nlogn)
![Page 35: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/35.jpg)
35
CAMINO MÍNIMO ENTRE OBSTÁCULOS
Un robot en una fábrica,¿qué camino debe seguir?
- robot puntual- obstáculos poligonales
El espacio libre es “continuo”,hay que discretizar
![Page 36: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/36.jpg)
36
CAMINO MÍNIMO ENTRE OBSTÁCULOS
Discretizando el espacio libre
Descomposición en trapecios
Mapa de carreteras
Algoritmo aleatorizadoO(nlogn)
![Page 37: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/37.jpg)
37
CAMINO MÍNIMO ENTRE OBSTÁCULOS
Mapa de carreteras (grafo geométrico)
1. Detectar trapecio2. Búsqueda BFS
en el mapa
Tiempo O(n)
¿Podemos mejorar?
![Page 38: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/38.jpg)
38
CAMINO SEGURO ENTRE OBSTÁCULOS
¿Y si buscamos el camino “más seguro”?
Mapa de carreteras=
Diagrama de Voronoi
![Page 39: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/39.jpg)
39
CAMINO MÍNIMO ENTRE OBSTÁCULOS
• El camino mínimo de s a t es una poligonal• Los vértices del camino son vértices de los obstáculos• Los segmentos del camino son aristas de visibilidad
s t
![Page 40: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/40.jpg)
40
GRAFO DE VISIBILIDAD
El camino mínimo de s a t es un camino en el grafo de visibilidad
st
Nuevo mapa de carreteras
![Page 41: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/41.jpg)
41
CAMINO MÍNIMO ENTRE OBSTÁCULOS
s t
1) Construcción del grafo de visibilidad G2) Construcción del camino mínimo en G de s a t
Algoritmo de Dijkstra
![Page 42: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/42.jpg)
42
Construcción del GRAFO DE VISIBILIDAD
Algoritmo fuerza brutaPara cada par de vértices a, b comprobar si la arista ab es válidaComplejidad O(n3)
Cota inferiorEl número de aristas puede ser cuadrático. Cota inferior (n2)
Algoritmo óptimo (Wezl) O(n2)Arreglo de rectas dual de los vértices. Ordenación topológica
Algoritmo Ghosh y Mount (1991)O(nlogn + E)
Construcción del camino mínimo
Algoritmo de Dijkstra O(nlogn+E)
![Page 43: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/43.jpg)
43
GRAFO DE VISIBILIDAD de un polígono
1
2
3
4
5
67
8
P 1 2
3
4
56
7
8
VisG(P)
- Caracterización o reconocimiento
• No hay caracterización• Condiciones necesarias (Ghosh, Everett)• Subgrafos prohibidos (Grötzsch sí, árboles no)• Si P es espiral entonces VisG(P) es grafo de intervalos
![Page 44: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/44.jpg)
44
GRAFO DE VISIBILIDAD de un polígono
Dado un grafo G, construir, si existe, un polígono P cuyo grafo de visibilidad sea isomorfo a G?
- Reconstrucción
• Grafos de visibilidad de espirales(Everett, Corneil)
• Cierre convexo de P a partir deVisG(P) y VisExG(P) (O’Rourke)
• Si se conocen las distancias entrevértices visibles, Coullard y Lubiwalgoritmo para el problema de reconstrucción en O(E)
![Page 45: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/45.jpg)
45
GRAFO DE VISIBILIDAD de un polígono
• Si G es el grafo de la triangulación de un polígono (grafo periplanomaximal) existe P monótono tal que GVisG(P)ElGindy O(nlogn)
- Reconstrucción
![Page 46: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/46.jpg)
46
GRAFO DE VISIBILIDAD de un polígono
Problemas abiertos• Encontrar una caracterización de los grafos de visibilidad que pueda comprobarse en tiempo polinómico
• Dado un grafo de visibilidad G y un ciclo hamiltoniano H determinar en tiempo polinómico si existe un polígono Pde borde H y tal que G=VisG(P)(No se sabe si este problema es NP)
![Page 47: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/47.jpg)
47
GRAFO DE VISIBILIDAD de un anillo poligonal
El grafo de visibilidad de un anillo poligonal con n vérticesinteriores y m exteriores se construye en tiempo O(n+m)(Cay, Everett)
![Page 48: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/48.jpg)
48
GRAFO DE VISIBILIDAD de un anillo poligonal
Representación con modelo de arcos circulares O(n+m)
![Page 49: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/49.jpg)
49
CAMINO MÍNIMO EN 3 D
En 2D se discretiza el problema porque los puntos de inflexióndel camino están restringidos a un conjunto finito
En 3D todos los puntos de las aristas de los obstáculos poliédricos pueden ser inflexiones
NP-duroalgoritmos aproximados con puntos adicionales
![Page 50: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/50.jpg)
50
PLANIFICACIÓN DE MOVIMIENTOS DE UN ROBOT
R robot, S = {P1, P2, ... , Pt} obstáculos poligonales
5 10
---
------R(0,0)
5
10
Traslación: 2 grados de libertad
R(6,4)
R(9,9,45)
Traslación + Rotación: 3 grados delibertad
![Page 51: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/51.jpg)
51
PLANIFICACIÓN DE MOVIMIENTOS DE UN ROBOT
Espacio de trabajo R2 ó R3 (donde el robot se mueve)
Espacio de parámetros o espacio de configuración C(R)Un punto p en C(R) es una ubicación R(p) del robot
• Si sólo traslaciones C(R) es el espacio de trabajo• Si además permitimos rotaciones en el plano
p=(x,y,) corresponde a la ubicación R(x,y,) C(R) es R2 [0,360) (un cilindro)
¿Todos los puntos p en C(R) corresponden a posiciones posibles del robot?
![Page 52: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/52.jpg)
52
PLANIFICACIÓN DE MOVIMIENTOS DE UN ROBOT
R(p) puede intersecar a los obstáculosHay puntos en C(R) prohibidos para los obstáculos S
Espacio prohibido Cproh(R,S)
Espacio libre Clib(R,S)
El camino del robot es una curva enel espacio libre
![Page 53: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/53.jpg)
53
Espacio de trabajo Espacio de configuración
Espacio prohibido Cproh(R,S)
![Page 54: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/54.jpg)
54
PLANIFICACIÓN DE MOVIMIENTOS DE UN ROBOT
1) Construcción del espacio libre Clib(R,S)
2) Construcción del camino mínimo para un robot puntualen el espacio libre
SUMA DE MINKOWSKI
GRAFO DE VISIBILIDADALGORITMO DE DIJKSTRA
![Page 55: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/55.jpg)
55
P Q
SUMA DE MINKOWSKI
P, Q conjuntos de R2
P Q = { p + q / p P, q Q}
(9,10)
(7,4)
(2,6)
P
Q
![Page 56: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/56.jpg)
56
SUMA DE MINKOWSKI
C(P)
Si R es un robot convexo, P obstáculo poligonal, el espacioprohibido (o C-obstáculo de P) es
C(P)={(x,y) / R(x,y) P}
P
C(P) = P ( R(0,0))
Teorema
![Page 57: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/57.jpg)
57
SUMA DE MINKOWSKIp+q
En P Q, un punto extremo en una dirección d debe ser sumade puntos extremos de P y de Q
p
P
Q
P Q
d
q
p
Teorema
Si P y Q son polígonos convexos de m y n vértices entoncesP Q es un polígono convexo de, a lo más, m+n lados
![Page 58: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/58.jpg)
58
SUMA DE MINKOWSKI
Algoritmo 1 (Suma de P y Q convexos)
1) Para cada par de vértices p, q de P y Q, respectivamente, se calcula p q
2) Cierre convexo de los puntos así obtenidosComplejidad O(nm)
Algoritmo 2 (Suma de P y Q convexos)
La observación sobre direcciones permite utilizar el método de los calibres para obtener un algoritmo lineal O(n+m)
![Page 59: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/59.jpg)
59
SUMA DE MINKOWSKI
¿Y si los polígonos no son convexos?
Clave: P (QR) = (P Q) (P R)
Si P es convexo y Q no convexo
1) Se triangula Q en m-2 triángulos T1, T2, ... , Tm-22) Se calculan las sumas P Tk
Cada una es un polígono de a lo más n+3 vértices3)
2m
1kkTPQP
Complejidad O(nm)
![Page 60: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/60.jpg)
60
SUMA DE MINKOWSKI
P
QPQ
Si P polígono de n lados,Q polígono de m lados, la complejidad de P Q es:
O(n+m) si P y Q convexosO(nm) si uno es convexo y el otro noO(n2m2) si ambos son no convexos
![Page 61: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/61.jpg)
61
PLANIFICACIÓN DE MOVIMIENTOS DE UN ROBOT
Espacio de configuraciónEspacio de trabajo
![Page 62: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/62.jpg)
62
PLANIFICACIÓN DE MOVIMIENTOS DE UN ROBOT
Grafo de visibilidad Camino mínimo
![Page 63: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/63.jpg)
63
PLANIFICACIÓN DE MOVIMIENTOS DE UN ROBOT
Complejidad
1) Si el robot R es convexo y de complejidad constante, el espacio libre entre polígonos con n lados en total se calcula en O(nlog2n) y tiene complejidad O(n)
2) El grafo de visibilidad del espacio libre se calcula en O(n2logn)
3) El camino mínimo para R entre dos lugares puede calcularse enO(n2logn)
![Page 64: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/64.jpg)
64
Rutas de vigilancia
Chin, Ntafos, 1992 O(n4)
![Page 65: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/65.jpg)
65
Rutas de vigilancia
• El Problema del viajante es NP-completo• El Problema de vigilancia en un polígono es NP-completo
Determinar la ruta del vigilante en polígonos con agujeroses NP-completo
![Page 66: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/66.jpg)
66
Rutas de vigilancia
Carlsson y otros, 1999 O(n6)
![Page 67: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/67.jpg)
67
PROBLEMA DEL ZOO
NP-duro si las jaulas no están en el borde Chin, NtafosO(nlogn) Bespamyatnikh, 99
![Page 68: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/68.jpg)
68
PROBLEMA DEL SAFARI
NP-duro si las zonas no están en el borde Chin, NtafosO(n3) Ntafos, 92
![Page 69: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/69.jpg)
69
REFERENCIAS BÁSICAS
• M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf, Computational Geometry, Springer, 1997
• J. O’Rourke, Computational Geometry in C, Cambridge, 1994• J. Urrutia, Art gallery and illumination problems, Handbook on
Computational Geometry, (J.-R. Sack, J. Urrutia, ed.) Elsevier, 2000• J. Mitchell, Shortest paths and networks, Handbook of Discrete and
Computational Geometry, (J. Goodman, J. O’Rourke, ed.) CRC, 1997
![Page 70: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/70.jpg)
70
Problemas abiertos
• J. O´Rourke, Open Problems in the Combinatorics ofVisibility and Illumination, Contemporary Mathematics, 2000
• Página web de J. Urrutiahttp://www.matem.unam.mx/~urrutia/
• Página web de J. O’Rourkehttp://cs.smith.edu/~orourke/Welcome.html
![Page 71: VISIBILIDAD E ILUMINACIÓN · polígono de n lados PROB. COMBINATORIO Colocar ese nº de guardias PROB. ALGORÍTMICO GALERÍAS DE ARTE N P - c om pl e t o . 6 PROB. COMBINATORIO 1](https://reader033.vdocumento.com/reader033/viewer/2022041701/5e418e42a1e21a1f236bf011/html5/thumbnails/71.jpg)
71
http://www.dma.fi.upm.es/docencia/trabajosfindecarrera/programas/geometriacomputacional/
Software en la red
Robot en un polígonohttp://wwwpi6.fernuni-hagen.de/Geometrie-Labor/apps/stip/Calibreshttp://cgm.cs.mcgill.ca/~orm/rotcal.html
Planificación de movimientoshttp://www.cs.uu.nl/~markov/kids/motion/