tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/tema 1-envolvente convexa(1... ·...
TRANSCRIPT
![Page 1: Tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/Tema 1-Envolvente convexa(1... · puntos de S y dejan a todo el ... Algoritmos: • Quickhull • Ptos. extremos](https://reader031.vdocumento.com/reader031/viewer/2022012405/5bacedb009d3f29b4f8ca086/html5/thumbnails/1.jpg)
Fundamentos de Geometría
Computacional I.T.I. Gestión
Envolvente convexa
Tema 1
![Page 2: Tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/Tema 1-Envolvente convexa(1... · puntos de S y dejan a todo el ... Algoritmos: • Quickhull • Ptos. extremos](https://reader031.vdocumento.com/reader031/viewer/2022012405/5bacedb009d3f29b4f8ca086/html5/thumbnails/2.jpg)
Algoritmos:
• Quickhull • Ptos. extremos
Definiciones
Tema 1 Envolvente convexa
• Scan de Graham • Marcha de Jarvis
Aplicaciones:
• Otros • Cota inferior
Fundamentos de Geometría
Computacional I.T.I. Gestión
• Anchura • Diámetro
Definiciones
Un conjunto es convexo si el segmento uniendo cualesquiera dos de sus puntos está contenido en él.
La intersección de convexos es un convexo.
![Page 3: Tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/Tema 1-Envolvente convexa(1... · puntos de S y dejan a todo el ... Algoritmos: • Quickhull • Ptos. extremos](https://reader031.vdocumento.com/reader031/viewer/2022012405/5bacedb009d3f29b4f8ca086/html5/thumbnails/3.jpg)
Algoritmos:
• Quickhull • Ptos. extremos
Definiciones
Tema 1 Envolvente convexa
• Scan de Graham • Marcha de Jarvis
Aplicaciones:
• Otros • Cota inferior
Fundamentos de Geometría
Computacional I.T.I. Gestión
• Anchura • Diámetro
Definiciones
Envolvente convexa de un conjunto: menor convexo que lo contiene.
O, equivalentemente, la intersección de todos los convexos que contienen al conjunto.
![Page 4: Tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/Tema 1-Envolvente convexa(1... · puntos de S y dejan a todo el ... Algoritmos: • Quickhull • Ptos. extremos](https://reader031.vdocumento.com/reader031/viewer/2022012405/5bacedb009d3f29b4f8ca086/html5/thumbnails/4.jpg)
Algoritmos:
• Quickhull • Ptos. extremos
Definiciones
Tema 1 Envolvente convexa
• Scan de Graham • Marcha de Jarvis
Aplicaciones:
• Otros • Cota inferior
Fundamentos de Geometría
Computacional I.T.I. Gestión
• Anchura • Diámetro
Definiciones
Aplicaciones: • Lo interesante suele ocurrir dentro de la
envolvente.
• Es más fácil (rápido) mover un convexo.
![Page 5: Tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/Tema 1-Envolvente convexa(1... · puntos de S y dejan a todo el ... Algoritmos: • Quickhull • Ptos. extremos](https://reader031.vdocumento.com/reader031/viewer/2022012405/5bacedb009d3f29b4f8ca086/html5/thumbnails/5.jpg)
Algoritmos:
• Quickhull • Ptos. extremos
Definiciones
Tema 1 Envolvente convexa
• Scan de Graham • Marcha de Jarvis
Aplicaciones:
• Otros • Cota inferior
Fundamentos de Geometría
Computacional I.T.I. Gestión
• Anchura • Diámetro
Definiciones
S una nube de puntos, S=p1,p2,…,pn
CH(S) es un polígono
arista extrema
punto extremo
![Page 6: Tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/Tema 1-Envolvente convexa(1... · puntos de S y dejan a todo el ... Algoritmos: • Quickhull • Ptos. extremos](https://reader031.vdocumento.com/reader031/viewer/2022012405/5bacedb009d3f29b4f8ca086/html5/thumbnails/6.jpg)
Algoritmos:
• Quickhull • Ptos. extremos
Tema 1 Envolvente convexa
Definiciones
• Scan de Graham • Marcha de Jarvis
Aplicaciones:
• Otros • Cota inferior
Fundamentos de Geometría
Computacional I.T.I. Gestión
• Anchura • Diámetro
Algoritmos: Puntos extremos
Punto extremo de S: no está contenido en ningún triángulo con vértices en puntos de S.
Sea S un conjunto de n puntos.
![Page 7: Tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/Tema 1-Envolvente convexa(1... · puntos de S y dejan a todo el ... Algoritmos: • Quickhull • Ptos. extremos](https://reader031.vdocumento.com/reader031/viewer/2022012405/5bacedb009d3f29b4f8ca086/html5/thumbnails/7.jpg)
Algoritmos:
• Quickhull • Ptos. extremos
Tema 1 Envolvente convexa
Definiciones
• Scan de Graham • Marcha de Jarvis
Aplicaciones:
• Otros • Cota inferior
Fundamentos de Geometría
Computacional I.T.I. Gestión
• Anchura • Diámetro
Algoritmos: Puntos extremos
Punto extremo de S: no está contenido en ningún triángulo con vértices en puntos de S.
Sea S un conjunto de n puntos.
![Page 8: Tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/Tema 1-Envolvente convexa(1... · puntos de S y dejan a todo el ... Algoritmos: • Quickhull • Ptos. extremos](https://reader031.vdocumento.com/reader031/viewer/2022012405/5bacedb009d3f29b4f8ca086/html5/thumbnails/8.jpg)
Algoritmos:
• Quickhull • Ptos. extremos
Tema 1 Envolvente convexa
Definiciones
• Scan de Graham • Marcha de Jarvis
Aplicaciones:
• Otros • Cota inferior
Fundamentos de Geometría
Computacional I.T.I. Gestión
• Anchura • Diámetro
Algoritmos: Puntos extremos
Los puntos extremos son los vértices de la envolvente convexa.
¿Cuánto nos cuesta encontrar todos los puntos extremos?
![Page 9: Tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/Tema 1-Envolvente convexa(1... · puntos de S y dejan a todo el ... Algoritmos: • Quickhull • Ptos. extremos](https://reader031.vdocumento.com/reader031/viewer/2022012405/5bacedb009d3f29b4f8ca086/html5/thumbnails/9.jpg)
Algoritmos:
• Quickhull • Ptos. extremos
Tema 1 Envolvente convexa
Definiciones
• Scan de Graham • Marcha de Jarvis
Aplicaciones:
• Otros • Cota inferior
Fundamentos de Geometría
Computacional I.T.I. Gestión
• Anchura • Diámetro
Algoritmos: Puntos extremos
Para cada punto de S, comprobar si está dentro de algún triángulo con vértices puntos de S:
• SÍ: No es vértice de la envolvente.
• NO: Es vértice de la envolvente convexa.
Para cada punto de S comprobar si está dentro de algún triángulo.
n puntos, O(n3) triángulos, O(n4) operaciones.
![Page 10: Tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/Tema 1-Envolvente convexa(1... · puntos de S y dejan a todo el ... Algoritmos: • Quickhull • Ptos. extremos](https://reader031.vdocumento.com/reader031/viewer/2022012405/5bacedb009d3f29b4f8ca086/html5/thumbnails/10.jpg)
Algoritmos:
• Quickhull • Ptos. extremos
Tema 1 Envolvente convexa
Definiciones
• Scan de Graham • Marcha de Jarvis
Aplicaciones:
• Otros • Cota inferior
Fundamentos de Geometría
Computacional I.T.I. Gestión
• Anchura • Diámetro
Algoritmos: Puntos extremos
También podemos buscar las aristas extremas (unen dos puntos de S y dejan a todo el conjunto a un mismo lado de la recta que definen).
Para cada par de puntos de S ver si la arista es extrema.
O(n2) pares, O(n) por comprobación O(n3) operaciones.
![Page 11: Tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/Tema 1-Envolvente convexa(1... · puntos de S y dejan a todo el ... Algoritmos: • Quickhull • Ptos. extremos](https://reader031.vdocumento.com/reader031/viewer/2022012405/5bacedb009d3f29b4f8ca086/html5/thumbnails/11.jpg)
Algoritmos:
• Quickhull • Ptos. extremos
Tema 1 Envolvente convexa
Definiciones
• Scan de Graham • Marcha de Jarvis
Aplicaciones:
• Otros • Cota inferior
Fundamentos de Geometría
Computacional I.T.I. Gestión
• Anchura • Diámetro
Algoritmos: Puntos extremos
Inciso: ¿Cómo sabemos si • un punto está dentro de un triángulo, o si • un punto está a un lado u otro de una recta?
Mediante un determinante
![Page 12: Tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/Tema 1-Envolvente convexa(1... · puntos de S y dejan a todo el ... Algoritmos: • Quickhull • Ptos. extremos](https://reader031.vdocumento.com/reader031/viewer/2022012405/5bacedb009d3f29b4f8ca086/html5/thumbnails/12.jpg)
Algoritmos:
• Quickhull • Ptos. extremos
Tema 1 Envolvente convexa
Definiciones
• Scan de Graham • Marcha de Jarvis
Aplicaciones:
• Otros • Cota inferior
Fundamentos de Geometría
Computacional I.T.I. Gestión
• Anchura • Diámetro
Algoritmos: Puntos extremos
¿A qué lado de la recta PQ está R?
P R
Q A partir de sus coordenadas construimos el determinante p1 p2 1
|A|= q1 q2 1
r1 r2 1
Interpretación geométrica: Vamos de P a Q, y luego de Q a R. Si:
• |A|>0: Giro a la izquierda. • |A|<0: Giro a la derecha.
![Page 13: Tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/Tema 1-Envolvente convexa(1... · puntos de S y dejan a todo el ... Algoritmos: • Quickhull • Ptos. extremos](https://reader031.vdocumento.com/reader031/viewer/2022012405/5bacedb009d3f29b4f8ca086/html5/thumbnails/13.jpg)
Algoritmos:
• Quickhull • Ptos. extremos
Tema 1 Envolvente convexa
Definiciones
• Scan de Graham • Marcha de Jarvis
Aplicaciones:
• Otros • Cota inferior
Fundamentos de Geometría
Computacional I.T.I. Gestión
• Anchura • Diámetro
R
Algoritmos: Puntos extremos
¿M está dentro o fuera del triángulo?
P
Q
¡Ojo! esto sólo vale para convexos .
M Si al recorrer el triángulo (en el sentido de las agujas del reloj) hacemos 3 giros a la derecha, entonces M está en el interior.
![Page 14: Tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/Tema 1-Envolvente convexa(1... · puntos de S y dejan a todo el ... Algoritmos: • Quickhull • Ptos. extremos](https://reader031.vdocumento.com/reader031/viewer/2022012405/5bacedb009d3f29b4f8ca086/html5/thumbnails/14.jpg)
Algoritmos:
• Quickhull • Ptos. extremos
Tema 1 Envolvente convexa
Definiciones
• Scan de Graham • Marcha de Jarvis
Aplicaciones:
• Otros • Cota inferior
Fundamentos de Geometría
Computacional I.T.I. Gestión
• Anchura • Diámetro
Algoritmos: Quickhull
Este (menor x)
Oeste (mayor x)
c c
c
![Page 15: Tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/Tema 1-Envolvente convexa(1... · puntos de S y dejan a todo el ... Algoritmos: • Quickhull • Ptos. extremos](https://reader031.vdocumento.com/reader031/viewer/2022012405/5bacedb009d3f29b4f8ca086/html5/thumbnails/15.jpg)
Algoritmos:
• Quickhull • Ptos. extremos
Tema 1 Envolvente convexa
Definiciones
• Scan de Graham • Marcha de Jarvis
Aplicaciones:
• Otros • Cota inferior
Fundamentos de Geometría
Computacional I.T.I. Gestión
• Anchura • Diámetro
???
O(n)
Algoritmos: Quickhull
Function QuickHull(a,b,C) if C es vacío then return() else c punto de C más alejado de ab A puntos a la derecha de ac B puntos a la derecha de cb return QuickHull(a,c,A)+( c )+QuickHull(c,b,B) b
a
(1) Encontrar dos puntos extremos iniciales x,y
Dividir S en S1 (puntos por encima de xy) y S2 (puntos por debajo de xy)
(2)
(3) CH(S)=(x)+QuickHull(x,y,S1)+(y)+QuickHull(y,x,S2)
c
![Page 16: Tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/Tema 1-Envolvente convexa(1... · puntos de S y dejan a todo el ... Algoritmos: • Quickhull • Ptos. extremos](https://reader031.vdocumento.com/reader031/viewer/2022012405/5bacedb009d3f29b4f8ca086/html5/thumbnails/16.jpg)
Algoritmos:
• Quickhull • Ptos. extremos
Tema 1 Envolvente convexa
Definiciones
• Scan de Graham • Marcha de Jarvis
Aplicaciones:
• Otros • Cota inferior
Fundamentos de Geometría
Computacional I.T.I. Gestión
• Anchura • Diámetro
Algoritmos: Quickhull
b
a
T(m) es el tiempo de ejecución de QuickHull(a,b,C), con |C|=m
Function QuickHull(a,b,C) if C es vacío then return() else c punto de C más alejado de ab A puntos a la derecha de ac B puntos a la derecha de cb return QuickHull(a,c,A)+( c )+QuickHull(c,b,B)
T(n)=O(n)+T(α)+T(β), siendo α=|A| y β=|B|, α+β≤n-1
Caso más desfavorable: α=0, β=n-1
T(n)=T(n-1)+O(n) T(n)=O(n2)
c
![Page 17: Tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/Tema 1-Envolvente convexa(1... · puntos de S y dejan a todo el ... Algoritmos: • Quickhull • Ptos. extremos](https://reader031.vdocumento.com/reader031/viewer/2022012405/5bacedb009d3f29b4f8ca086/html5/thumbnails/17.jpg)
Algoritmos:
• Quickhull • Ptos. extremos
Tema 1 Envolvente convexa
Definiciones
• Scan de Graham • Marcha de Jarvis
Aplicaciones:
• Otros • Cota inferior
Fundamentos de Geometría
Computacional I.T.I. Gestión
• Anchura • Diámetro
O(n2)
O(n)
Algoritmos: Quickhull
Function QuickHull(a,b,C) if C es vacío then return() else c punto de C más alejado de ab A puntos a la derecha de ac B puntos a la derecha de cb return QuickHull(a,c,A)+( c )+QuickHull(c,b,B) b
a
(1) Encontrar dos puntos extremos iniciales x,y
Dividir S en S1 (puntos por encima de xy) y S2 (puntos por debajo de xy)
(2)
(3) CH(S)=(x)+QuickHull(x,y,S1)+(y)+QuickHull(y,x,S2)
c
![Page 18: Tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/Tema 1-Envolvente convexa(1... · puntos de S y dejan a todo el ... Algoritmos: • Quickhull • Ptos. extremos](https://reader031.vdocumento.com/reader031/viewer/2022012405/5bacedb009d3f29b4f8ca086/html5/thumbnails/18.jpg)
Algoritmos:
• Quickhull
• Scan de Graham • Marcha de Jarvis
• Ptos. extremos
Tema 1 Envolvente convexa
Definiciones
Aplicaciones:
• Otros • Cota inferior
Fundamentos de Geometría
Computacional I.T.I. Gestión
• Anchura • Diámetro
Algoritmos: Marcha de Jarvis
Buscamos el punto Sur y a partir de él giramos una semirrecta
![Page 19: Tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/Tema 1-Envolvente convexa(1... · puntos de S y dejan a todo el ... Algoritmos: • Quickhull • Ptos. extremos](https://reader031.vdocumento.com/reader031/viewer/2022012405/5bacedb009d3f29b4f8ca086/html5/thumbnails/19.jpg)
Algoritmos:
• Quickhull
• Scan de Graham • Marcha de Jarvis
• Ptos. extremos
Tema 1 Envolvente convexa
Definiciones
Aplicaciones:
• Otros • Cota inferior
Fundamentos de Geometría
Computacional I.T.I. Gestión
• Anchura • Diámetro
Algoritmos: Marcha de Jarvis
Buscamos el punto Sur y a partir de él giramos una semirrecta hasta encontrar el siguiente punto de la envolvente.
![Page 20: Tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/Tema 1-Envolvente convexa(1... · puntos de S y dejan a todo el ... Algoritmos: • Quickhull • Ptos. extremos](https://reader031.vdocumento.com/reader031/viewer/2022012405/5bacedb009d3f29b4f8ca086/html5/thumbnails/20.jpg)
Algoritmos:
• Quickhull
• Scan de Graham • Marcha de Jarvis
• Ptos. extremos
Tema 1 Envolvente convexa
Definiciones
Aplicaciones:
• Otros • Cota inferior
Fundamentos de Geometría
Computacional I.T.I. Gestión
• Anchura • Diámetro
Algoritmos: Marcha de Jarvis
Repetimos el proceso hasta volver al punto de partida.
![Page 21: Tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/Tema 1-Envolvente convexa(1... · puntos de S y dejan a todo el ... Algoritmos: • Quickhull • Ptos. extremos](https://reader031.vdocumento.com/reader031/viewer/2022012405/5bacedb009d3f29b4f8ca086/html5/thumbnails/21.jpg)
Algoritmos:
• Quickhull
• Scan de Graham • Marcha de Jarvis
• Ptos. extremos
Tema 1 Envolvente convexa
Definiciones
Aplicaciones:
• Otros • Cota inferior
Fundamentos de Geometría
Computacional I.T.I. Gestión
• Anchura • Diámetro
Algoritmos: Marcha de Jarvis
Repetimos el proceso hasta volver al punto de partida.
![Page 22: Tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/Tema 1-Envolvente convexa(1... · puntos de S y dejan a todo el ... Algoritmos: • Quickhull • Ptos. extremos](https://reader031.vdocumento.com/reader031/viewer/2022012405/5bacedb009d3f29b4f8ca086/html5/thumbnails/22.jpg)
Algoritmos:
• Quickhull
• Scan de Graham • Marcha de Jarvis
• Ptos. extremos
Tema 1 Envolvente convexa
Definiciones
Aplicaciones:
• Otros • Cota inferior
Fundamentos de Geometría
Computacional I.T.I. Gestión
• Anchura • Diámetro
Algoritmos: Marcha de Jarvis
Coste: Buscar el siguiente punto: O(n) Hay que repetirlo n veces en el peor de los casos.
Número de operaciones: O(n2)
![Page 23: Tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/Tema 1-Envolvente convexa(1... · puntos de S y dejan a todo el ... Algoritmos: • Quickhull • Ptos. extremos](https://reader031.vdocumento.com/reader031/viewer/2022012405/5bacedb009d3f29b4f8ca086/html5/thumbnails/23.jpg)
Algoritmos:
• Quickhull
• Scan de Graham • Marcha de Jarvis
• Ptos. extremos
Tema 1 Envolvente convexa
Definiciones
Aplicaciones:
• Otros • Cota inferior
Fundamentos de Geometría
Computacional I.T.I. Gestión
• Anchura • Diámetro
Algoritmos: Marcha de Jarvis
En realidad el tiempo de ejecución es: O(nh), siendo h el número de puntos de la envolvente. Es un algoritmo output sensitive.
![Page 24: Tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/Tema 1-Envolvente convexa(1... · puntos de S y dejan a todo el ... Algoritmos: • Quickhull • Ptos. extremos](https://reader031.vdocumento.com/reader031/viewer/2022012405/5bacedb009d3f29b4f8ca086/html5/thumbnails/24.jpg)
Algoritmos:
• Quickhull
• Scan de Graham • Marcha de Jarvis
• Ptos. extremos
Tema 1 Envolvente convexa
Definiciones
Aplicaciones:
• Otros • Cota inferior
Fundamentos de Geometría
Computacional I.T.I. Gestión
• Anchura • Diámetro
Algoritmos: Scan de Graham
Encontrar p0 el mas abajo-derecha
0
Ordenar el resto por sus ángulos con el vértice p0 (si hay empates eliminar los más cercanos a p0)
![Page 25: Tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/Tema 1-Envolvente convexa(1... · puntos de S y dejan a todo el ... Algoritmos: • Quickhull • Ptos. extremos](https://reader031.vdocumento.com/reader031/viewer/2022012405/5bacedb009d3f29b4f8ca086/html5/thumbnails/25.jpg)
Algoritmos:
• Quickhull
• Scan de Graham • Marcha de Jarvis
• Ptos. extremos
Tema 1 Envolvente convexa
Definiciones
Aplicaciones:
• Otros • Cota inferior
Fundamentos de Geometría
Computacional I.T.I. Gestión
• Anchura • Diámetro
Algoritmos: Scan de Graham
Encontrar p0 el mas abajo-derecha
0
Ordenar el resto por sus ángulos con el vértice p0 (si hay empates eliminar los más cercanos a p0)
1
2
3
4 5
6 7 8
9
10
11
12
![Page 26: Tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/Tema 1-Envolvente convexa(1... · puntos de S y dejan a todo el ... Algoritmos: • Quickhull • Ptos. extremos](https://reader031.vdocumento.com/reader031/viewer/2022012405/5bacedb009d3f29b4f8ca086/html5/thumbnails/26.jpg)
Algoritmos:
• Quickhull
• Scan de Graham • Marcha de Jarvis
• Ptos. extremos
Tema 1 Envolvente convexa
Definiciones
Aplicaciones:
• Otros • Cota inferior
Fundamentos de Geometría
Computacional I.T.I. Gestión
• Anchura • Diámetro
Algoritmos: Scan de Graham
0
Encontrar p0 el mas abajo-derecha
Ordenar el resto por sus ángulos con el vértice p0 (si hay empates eliminar los más cercanos a p0)
Iniciar la pila S=(0,1); i=2; while i<n do s=penúltimo de la pila; t=último de la pila; if pi está a la izquierda de pspt then añade i a la pila; i=i+1; else quita t de la pila;
1
2
3
4 5
6 7 8
9
11
12
10
![Page 27: Tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/Tema 1-Envolvente convexa(1... · puntos de S y dejan a todo el ... Algoritmos: • Quickhull • Ptos. extremos](https://reader031.vdocumento.com/reader031/viewer/2022012405/5bacedb009d3f29b4f8ca086/html5/thumbnails/27.jpg)
Algoritmos:
• Quickhull
• Scan de Graham • Marcha de Jarvis
• Ptos. extremos
Tema 1 Envolvente convexa
Definiciones
Aplicaciones:
• Otros • Cota inferior
Fundamentos de Geometría
Computacional I.T.I. Gestión
• Anchura • Diámetro
Algoritmos: Scan de Graham
0
1
2
3
4 5
6 7 8
9
11
12
10
Encontrar p0 el mas abajo-derecha
Ordenar el resto por sus ángulos con el vértice p0 (si hay empates eliminar los más cercanos a p0)
Iniciar la pila S=(0,1); i=2; while i<n do s=penúltimo de la pila; t=último de la pila; if pi está a la izquierda de pspt then añade i a la pila; i=i+1; else quita t de la pila;
![Page 28: Tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/Tema 1-Envolvente convexa(1... · puntos de S y dejan a todo el ... Algoritmos: • Quickhull • Ptos. extremos](https://reader031.vdocumento.com/reader031/viewer/2022012405/5bacedb009d3f29b4f8ca086/html5/thumbnails/28.jpg)
Algoritmos:
• Quickhull
• Scan de Graham • Marcha de Jarvis
• Ptos. extremos
Tema 1 Envolvente convexa
Definiciones
Aplicaciones:
• Otros • Cota inferior
Fundamentos de Geometría
Computacional I.T.I. Gestión
• Anchura • Diámetro
Algoritmos: Scan de Graham
0
1
2
3
4 5
6 7 8
9
11
12
10
Encontrar p0 el mas abajo-derecha
Ordenar el resto por sus ángulos con el vértice p0 (si hay empates eliminar los más cercanos a p0)
Iniciar la pila S=(0,1); i=2; while i<n do s=penúltimo de la pila; t=último de la pila; if pi está a la izquierda de pspt then añade i a la pila; i=i+1; else quita t de la pila;
![Page 29: Tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/Tema 1-Envolvente convexa(1... · puntos de S y dejan a todo el ... Algoritmos: • Quickhull • Ptos. extremos](https://reader031.vdocumento.com/reader031/viewer/2022012405/5bacedb009d3f29b4f8ca086/html5/thumbnails/29.jpg)
Algoritmos:
• Quickhull
• Scan de Graham • Marcha de Jarvis
• Ptos. extremos
Tema 1 Envolvente convexa
Definiciones
Aplicaciones:
• Otros • Cota inferior
Fundamentos de Geometría
Computacional I.T.I. Gestión
• Anchura • Diámetro
Algoritmos: Scan de Graham
0
1
2
3
4 5
6 7 8
9
11
12
10
Encontrar p0 el mas abajo-derecha
Ordenar el resto por sus ángulos con el vértice p0 (si hay empates eliminar los más cercanos a p0)
Iniciar la pila S=(0,1); i=2; while i<n do s=penúltimo de la pila; t=último de la pila; if pi está a la izquierda de pspt then añade i a la pila; i=i+1; else quita t de la pila;
![Page 30: Tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/Tema 1-Envolvente convexa(1... · puntos de S y dejan a todo el ... Algoritmos: • Quickhull • Ptos. extremos](https://reader031.vdocumento.com/reader031/viewer/2022012405/5bacedb009d3f29b4f8ca086/html5/thumbnails/30.jpg)
Algoritmos:
• Quickhull
• Scan de Graham • Marcha de Jarvis
• Ptos. extremos
Tema 1 Envolvente convexa
Definiciones
Aplicaciones:
• Otros • Cota inferior
Fundamentos de Geometría
Computacional I.T.I. Gestión
• Anchura • Diámetro
Algoritmos: Scan de Graham
0
1
2
3
4 5
6 7 8
9
11
12
10
Encontrar p0 el mas abajo-derecha
Ordenar el resto por sus ángulos con el vértice p0 (si hay empates eliminar los más cercanos a p0)
Iniciar la pila S=(0,1); i=2; while i<n do s=penúltimo de la pila; t=último de la pila; if pi está a la izquierda de pspt then añade i a la pila; i=i+1; else quita t de la pila;
![Page 31: Tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/Tema 1-Envolvente convexa(1... · puntos de S y dejan a todo el ... Algoritmos: • Quickhull • Ptos. extremos](https://reader031.vdocumento.com/reader031/viewer/2022012405/5bacedb009d3f29b4f8ca086/html5/thumbnails/31.jpg)
Algoritmos:
• Quickhull
• Scan de Graham • Marcha de Jarvis
• Ptos. extremos
Tema 1 Envolvente convexa
Definiciones
Aplicaciones:
• Otros • Cota inferior
Fundamentos de Geometría
Computacional I.T.I. Gestión
• Anchura • Diámetro
Algoritmos: Scan de Graham
0
1
2
3
4 5
6 7 8
9
11
12
10
Encontrar p0 el mas abajo-derecha
Ordenar el resto por sus ángulos con el vértice p0 (si hay empates eliminar los más cercanos a p0)
Iniciar la pila S=(0,1); i=2; while i<n do s=penúltimo de la pila; t=último de la pila; if pi está a la izquierda de pspt then añade i a la pila; i=i+1; else quita t de la pila;
![Page 32: Tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/Tema 1-Envolvente convexa(1... · puntos de S y dejan a todo el ... Algoritmos: • Quickhull • Ptos. extremos](https://reader031.vdocumento.com/reader031/viewer/2022012405/5bacedb009d3f29b4f8ca086/html5/thumbnails/32.jpg)
Algoritmos:
• Quickhull
• Scan de Graham • Marcha de Jarvis
• Ptos. extremos
Tema 1 Envolvente convexa
Definiciones
Aplicaciones:
• Otros • Cota inferior
Fundamentos de Geometría
Computacional I.T.I. Gestión
• Anchura • Diámetro
Algoritmos: Scan de Graham
0
1
2
3
4 5
6 7 8
9
11
12
10
Encontrar p0 el mas abajo-derecha
Ordenar el resto por sus ángulos con el vértice p0 (si hay empates eliminar los más cercanos a p0)
Iniciar la pila S=(0,1); i=2; while i<n do s=penúltimo de la pila; t=último de la pila; if pi está a la izquierda de pspt then añade i a la pila; i=i+1; else quita t de la pila;
![Page 33: Tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/Tema 1-Envolvente convexa(1... · puntos de S y dejan a todo el ... Algoritmos: • Quickhull • Ptos. extremos](https://reader031.vdocumento.com/reader031/viewer/2022012405/5bacedb009d3f29b4f8ca086/html5/thumbnails/33.jpg)
Algoritmos:
• Quickhull
• Scan de Graham • Marcha de Jarvis
• Ptos. extremos
Tema 1 Envolvente convexa
Definiciones
Aplicaciones:
• Otros • Cota inferior
Fundamentos de Geometría
Computacional I.T.I. Gestión
• Anchura • Diámetro
Algoritmos: Scan de Graham
0
1
2
3
4 5
6 7 8
9
11
12
10
Encontrar p0 el mas abajo-derecha
Ordenar el resto por sus ángulos con el vértice p0 (si hay empates eliminar los más cercanos a p0)
Iniciar la pila S=(0,1); i=2; while i<n do s=penúltimo de la pila; t=último de la pila; if pi está a la izquierda de pspt then añade i a la pila; i=i+1; else quita t de la pila;
![Page 34: Tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/Tema 1-Envolvente convexa(1... · puntos de S y dejan a todo el ... Algoritmos: • Quickhull • Ptos. extremos](https://reader031.vdocumento.com/reader031/viewer/2022012405/5bacedb009d3f29b4f8ca086/html5/thumbnails/34.jpg)
Algoritmos:
• Quickhull
• Scan de Graham • Marcha de Jarvis
• Ptos. extremos
Tema 1 Envolvente convexa
Definiciones
Aplicaciones:
• Otros • Cota inferior
Fundamentos de Geometría
Computacional I.T.I. Gestión
• Anchura • Diámetro
Algoritmos: Scan de Graham
0
1
2
3
4 5
6 7 8
9
11
12
10
Encontrar p0 el mas abajo-derecha
Ordenar el resto por sus ángulos con el vértice p0 (si hay empates eliminar los más cercanos a p0)
Iniciar la pila S=(0,1); i=2; while i<n do s=penúltimo de la pila; t=último de la pila; if pi está a la izquierda de pspt then añade i a la pila; i=i+1; else quita t de la pila;
![Page 35: Tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/Tema 1-Envolvente convexa(1... · puntos de S y dejan a todo el ... Algoritmos: • Quickhull • Ptos. extremos](https://reader031.vdocumento.com/reader031/viewer/2022012405/5bacedb009d3f29b4f8ca086/html5/thumbnails/35.jpg)
Algoritmos:
• Quickhull
• Scan de Graham • Marcha de Jarvis
• Ptos. extremos
Tema 1 Envolvente convexa
Definiciones
Aplicaciones:
• Otros • Cota inferior
Fundamentos de Geometría
Computacional I.T.I. Gestión
• Anchura • Diámetro
Algoritmos: Scan de Graham
Encontrar p0 el mas abajo-derecha
0
1
2
3
4 5
6 7 8
9
11
12
10
Encontrar p0 el mas abajo-derecha
Ordenar el resto por sus ángulos con el vértice p0 (si hay empates eliminar los más cercanos a p0)
Iniciar la pila S=(0,1); i=2; while i<n do s=penúltimo de la pila; t=último de la pila; if pi está a la izquierda de pspt then añade i a la pila; i=i+1; else quita t de la pila;
![Page 36: Tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/Tema 1-Envolvente convexa(1... · puntos de S y dejan a todo el ... Algoritmos: • Quickhull • Ptos. extremos](https://reader031.vdocumento.com/reader031/viewer/2022012405/5bacedb009d3f29b4f8ca086/html5/thumbnails/36.jpg)
Algoritmos:
• Quickhull
• Scan de Graham • Marcha de Jarvis
• Ptos. extremos
Tema 1 Envolvente convexa
Definiciones
Aplicaciones:
• Otros • Cota inferior
Fundamentos de Geometría
Computacional I.T.I. Gestión
• Anchura • Diámetro
Algoritmos: Scan de Graham
0
1
2
3
4 5
6 7 8
9
11
12
10
Encontrar p0 el mas abajo-derecha
Ordenar el resto por sus ángulos con el vértice p0 (si hay empates eliminar los más cercanos a p0)
Iniciar la pila S=(0,1); i=2; while i<n do s=penúltimo de la pila; t=último de la pila; if pi está a la izquierda de pspt then añade i a la pila; i=i+1; else quita t de la pila;
![Page 37: Tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/Tema 1-Envolvente convexa(1... · puntos de S y dejan a todo el ... Algoritmos: • Quickhull • Ptos. extremos](https://reader031.vdocumento.com/reader031/viewer/2022012405/5bacedb009d3f29b4f8ca086/html5/thumbnails/37.jpg)
Algoritmos:
• Quickhull
• Scan de Graham • Marcha de Jarvis
• Ptos. extremos
Tema 1 Envolvente convexa
Definiciones
Aplicaciones:
• Otros • Cota inferior
Fundamentos de Geometría
Computacional I.T.I. Gestión
• Anchura • Diámetro
Algoritmos: Scan de Graham
0
1
2
3
4 5
6 7 8
9
11
12
10
Encontrar p0 el mas abajo-derecha
Ordenar el resto por sus ángulos con el vértice p0 (si hay empates eliminar los más cercanos a p0)
Iniciar la pila S=(0,1); i=2; while i<n do s=penúltimo de la pila; t=último de la pila; if pi está a la izquierda de pspt then añade i a la pila; i=i+1; else quita t de la pila;
![Page 38: Tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/Tema 1-Envolvente convexa(1... · puntos de S y dejan a todo el ... Algoritmos: • Quickhull • Ptos. extremos](https://reader031.vdocumento.com/reader031/viewer/2022012405/5bacedb009d3f29b4f8ca086/html5/thumbnails/38.jpg)
Algoritmos:
• Quickhull
• Scan de Graham • Marcha de Jarvis
• Ptos. extremos
Tema 1 Envolvente convexa
Definiciones
Aplicaciones:
• Otros • Cota inferior
Fundamentos de Geometría
Computacional I.T.I. Gestión
• Anchura • Diámetro
Algoritmos: Scan de Graham
0
1
2
3
4 5
6 7 8
9
11
12
10
Encontrar p0 el mas abajo-derecha
Ordenar el resto por sus ángulos con el vértice p0 (si hay empates eliminar los más cercanos a p0)
Iniciar la pila S=(0,1); i=2; while i<n do s=penúltimo de la pila; t=último de la pila; if pi está a la izquierda de pspt then añade i a la pila; i=i+1; else quita t de la pila;
![Page 39: Tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/Tema 1-Envolvente convexa(1... · puntos de S y dejan a todo el ... Algoritmos: • Quickhull • Ptos. extremos](https://reader031.vdocumento.com/reader031/viewer/2022012405/5bacedb009d3f29b4f8ca086/html5/thumbnails/39.jpg)
Algoritmos:
• Quickhull
• Scan de Graham • Marcha de Jarvis
• Ptos. extremos
Tema 1 Envolvente convexa
Definiciones
Aplicaciones:
• Otros • Cota inferior
Fundamentos de Geometría
Computacional I.T.I. Gestión
• Anchura • Diámetro
Algoritmos: Scan de Graham
0
1
2
3
4 5
6 7 8
9
11
12
10
Encontrar p0 el mas abajo-derecha
Ordenar el resto por sus ángulos con el vértice p0 (si hay empates eliminar los más cercanos a p0)
Iniciar la pila S=(0,1); i=2; while i<n do s=penúltimo de la pila; t=último de la pila; if pi está a la izquierda de pspt then añade i a la pila; i=i+1; else quita t de la pila;
![Page 40: Tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/Tema 1-Envolvente convexa(1... · puntos de S y dejan a todo el ... Algoritmos: • Quickhull • Ptos. extremos](https://reader031.vdocumento.com/reader031/viewer/2022012405/5bacedb009d3f29b4f8ca086/html5/thumbnails/40.jpg)
Algoritmos:
• Quickhull
• Scan de Graham • Marcha de Jarvis
• Ptos. extremos
Tema 1 Envolvente convexa
Definiciones
Aplicaciones:
• Otros • Cota inferior
Fundamentos de Geometría
Computacional I.T.I. Gestión
• Anchura • Diámetro
Algoritmos: Scan de Graham
0
1
2
3
4 5
6 7 8
9
11
12
10
Encontrar p0 el mas abajo-derecha
Ordenar el resto por sus ángulos con el vértice p0 (si hay empates eliminar los más cercanos a p0)
Iniciar la pila S=(0,1); i=2; while i<n do s=penúltimo de la pila; t=último de la pila; if pi está a la izquierda de pspt then añade i a la pila; i=i+1; else quita t de la pila;
![Page 41: Tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/Tema 1-Envolvente convexa(1... · puntos de S y dejan a todo el ... Algoritmos: • Quickhull • Ptos. extremos](https://reader031.vdocumento.com/reader031/viewer/2022012405/5bacedb009d3f29b4f8ca086/html5/thumbnails/41.jpg)
Algoritmos:
• Quickhull
• Scan de Graham • Marcha de Jarvis
• Ptos. extremos
Tema 1 Envolvente convexa
Definiciones
Aplicaciones:
• Otros • Cota inferior
Fundamentos de Geometría
Computacional I.T.I. Gestión
• Anchura • Diámetro
Algoritmos: Scan de Graham
0
1
2
3
4 5
6 7 8
9
11
12
10
Encontrar p0 el mas abajo-derecha
Ordenar el resto por sus ángulos con el vértice p0 (si hay empates eliminar los más cercanos a p0)
Iniciar la pila S=(0,1); i=2; while i<n do s=penúltimo de la pila; t=último de la pila; if pi está a la izquierda de pspt then añade i a la pila; i=i+1; else quita t de la pila;
![Page 42: Tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/Tema 1-Envolvente convexa(1... · puntos de S y dejan a todo el ... Algoritmos: • Quickhull • Ptos. extremos](https://reader031.vdocumento.com/reader031/viewer/2022012405/5bacedb009d3f29b4f8ca086/html5/thumbnails/42.jpg)
Algoritmos:
• Quickhull
• Scan de Graham • Marcha de Jarvis
• Ptos. extremos
Tema 1 Envolvente convexa
Definiciones
Aplicaciones:
• Otros • Cota inferior
Fundamentos de Geometría
Computacional I.T.I. Gestión
• Anchura • Diámetro
Algoritmos: Scan de Graham
0
1
2
3
4 5
6 7 8
9
11
12
10
Encontrar p0 el mas abajo-derecha
Ordenar el resto por sus ángulos con el vértice p0 (si hay empates eliminar los más cercanos a p0)
Iniciar la pila S=(0,1); i=2; while i<n do s=penúltimo de la pila; t=último de la pila; if pi está a la izquierda de pspt then añade i a la pila; i=i+1; else quita t de la pila;
![Page 43: Tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/Tema 1-Envolvente convexa(1... · puntos de S y dejan a todo el ... Algoritmos: • Quickhull • Ptos. extremos](https://reader031.vdocumento.com/reader031/viewer/2022012405/5bacedb009d3f29b4f8ca086/html5/thumbnails/43.jpg)
Algoritmos:
• Quickhull
• Scan de Graham • Marcha de Jarvis
• Ptos. extremos
Tema 1 Envolvente convexa
Definiciones
Aplicaciones:
• Otros • Cota inferior
Fundamentos de Geometría
Computacional I.T.I. Gestión
• Anchura • Diámetro
Algoritmos: Scan de Graham
0
1
2
3
4 5
6 7 8
9
11
12
10
O(n log n)
O(n)
O(n)
Teorema: El Scan de Graham computa la envolvente convexa de n puntos en un tiempo O(n log n).
Encontrar p0 el mas abajo-derecha
Ordenar el resto por sus ángulos con el vértice p0 (si hay empates eliminar los más cercanos a p0)
Iniciar la pila S=(0,1); i=2; while i<n do s=penúltimo de la pila; t=último de la pila; if pi está a la izquierda de pspt then añade i a la pila; i=i+1; else quita t de la pila;
![Page 44: Tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/Tema 1-Envolvente convexa(1... · puntos de S y dejan a todo el ... Algoritmos: • Quickhull • Ptos. extremos](https://reader031.vdocumento.com/reader031/viewer/2022012405/5bacedb009d3f29b4f8ca086/html5/thumbnails/44.jpg)
Algoritmos:
• Quickhull • Marcha de Jarvis
• Ptos. extremos
Tema 1 Envolvente convexa
Definiciones
Aplicaciones:
• Otros • Cota inferior
• Scan de Graham
Fundamentos de Geometría
Computacional I.T.I. Gestión
• Anchura • Diámetro
Algoritmos: Divide y Vencerás
1) Ordenar los puntos por abscisa
![Page 45: Tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/Tema 1-Envolvente convexa(1... · puntos de S y dejan a todo el ... Algoritmos: • Quickhull • Ptos. extremos](https://reader031.vdocumento.com/reader031/viewer/2022012405/5bacedb009d3f29b4f8ca086/html5/thumbnails/45.jpg)
Algoritmos:
• Quickhull • Marcha de Jarvis
• Ptos. extremos
Tema 1 Envolvente convexa
Definiciones
Aplicaciones:
• Otros • Cota inferior
• Scan de Graham
Fundamentos de Geometría
Computacional I.T.I. Gestión
• Anchura • Diámetro
Algoritmos: Divide y Vencerás
1) Ordenar los puntos por abscisa
2) Dividir los puntos de S en dos subconjuntos: S1 con los n/2 puntos más a la izquierda y S2 con n/2 puntos más a la derecha
3) Calcular, recursivamente CH(A) y CH(B)
4) Unir CH(A) y CH(B) para obtener CH(S).
![Page 46: Tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/Tema 1-Envolvente convexa(1... · puntos de S y dejan a todo el ... Algoritmos: • Quickhull • Ptos. extremos](https://reader031.vdocumento.com/reader031/viewer/2022012405/5bacedb009d3f29b4f8ca086/html5/thumbnails/46.jpg)
Algoritmos:
• Quickhull • Marcha de Jarvis
• Ptos. extremos
Tema 1 Envolvente convexa
Definiciones
Aplicaciones:
• Otros • Cota inferior
• Scan de Graham
Fundamentos de Geometría
Computacional I.T.I. Gestión
• Anchura • Diámetro
Algoritmos: Divide y Vencerás
1) Ordenar los puntos por abscisa
2) Dividir los puntos de S en dos subconjuntos: S1 con los n/2 puntos más a la izquierda y S2 con n/2 puntos más a la derecha
3) Calcular, recursivamente CH(A) y CH(B)
4) Unir CH(A) y CH(B) para obtener CH(S).
![Page 47: Tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/Tema 1-Envolvente convexa(1... · puntos de S y dejan a todo el ... Algoritmos: • Quickhull • Ptos. extremos](https://reader031.vdocumento.com/reader031/viewer/2022012405/5bacedb009d3f29b4f8ca086/html5/thumbnails/47.jpg)
Algoritmos:
• Quickhull • Marcha de Jarvis
• Ptos. extremos
Tema 1 Envolvente convexa
Definiciones
Aplicaciones:
• Otros • Cota inferior
• Scan de Graham
Fundamentos de Geometría
Computacional I.T.I. Gestión
• Anchura • Diámetro
Algoritmos: Divide y Vencerás
1) Ordenar los puntos por abscisa
2) Dividir los puntos de S en dos subconjuntos: S1 con los n/2 puntos más a la izquierda y S2 con n/2 puntos más a la derecha
3) Calcular, recursivamente CH(A) y CH(B)
4) Unir CH(A) y CH(B) para obtener CH(S).
![Page 48: Tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/Tema 1-Envolvente convexa(1... · puntos de S y dejan a todo el ... Algoritmos: • Quickhull • Ptos. extremos](https://reader031.vdocumento.com/reader031/viewer/2022012405/5bacedb009d3f29b4f8ca086/html5/thumbnails/48.jpg)
Algoritmos:
• Quickhull • Marcha de Jarvis
• Ptos. extremos
Tema 1 Envolvente convexa
Definiciones
Aplicaciones:
• Otros • Cota inferior
• Scan de Graham
Fundamentos de Geometría
Computacional I.T.I. Gestión
• Anchura • Diámetro
Algoritmos: Divide y Vencerás
1) Ordenar los puntos por abscisa
2) Dividir los puntos de S en dos subconjuntos: S1 con los n/2 puntos más a la izquierda y S2 con n/2 puntos más a la derecha
3) Calcular, recursivamente CH(A) y CH(B)
4) Unir CH(A) y CH(B) para obtener CH(S).
![Page 49: Tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/Tema 1-Envolvente convexa(1... · puntos de S y dejan a todo el ... Algoritmos: • Quickhull • Ptos. extremos](https://reader031.vdocumento.com/reader031/viewer/2022012405/5bacedb009d3f29b4f8ca086/html5/thumbnails/49.jpg)
Algoritmos:
• Quickhull • Marcha de Jarvis
• Ptos. extremos
Tema 1 Envolvente convexa
Definiciones
Aplicaciones:
• Otros • Cota inferior
• Scan de Graham
Fundamentos de Geometría
Computacional I.T.I. Gestión
• Anchura • Diámetro
Algoritmos: Divide y Vencerás
1) Ordenar los puntos por abscisa
2) Dividir los puntos de S en dos subconjuntos: S1 con los n/2 puntos más a la izquierda y S2 con n/2 puntos más a la derecha
3) Calcular, recursivamente CH(A) y CH(B)
4) Unir CH(A) y CH(B) para obtener CH(S).
![Page 50: Tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/Tema 1-Envolvente convexa(1... · puntos de S y dejan a todo el ... Algoritmos: • Quickhull • Ptos. extremos](https://reader031.vdocumento.com/reader031/viewer/2022012405/5bacedb009d3f29b4f8ca086/html5/thumbnails/50.jpg)
Algoritmos:
• Quickhull • Marcha de Jarvis
• Ptos. extremos
Tema 1 Envolvente convexa
Definiciones
Aplicaciones:
• Otros • Cota inferior
• Scan de Graham
Fundamentos de Geometría
Computacional I.T.I. Gestión
• Anchura • Diámetro
Algoritmos: Divide y Vencerás
1) Ordenar los puntos por abscisa
2) Dividir los puntos de S en dos subconjuntos: S1 con los n/2 puntos más a la izquierda y S2 con n/2 puntos más a la derecha
3) Calcular, recursivamente CH(A) y CH(B)
4) Unir CH(A) y CH(B) para obtener CH(S).
![Page 51: Tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/Tema 1-Envolvente convexa(1... · puntos de S y dejan a todo el ... Algoritmos: • Quickhull • Ptos. extremos](https://reader031.vdocumento.com/reader031/viewer/2022012405/5bacedb009d3f29b4f8ca086/html5/thumbnails/51.jpg)
Algoritmos:
• Quickhull • Marcha de Jarvis
• Ptos. extremos
Tema 1 Envolvente convexa
Definiciones
Aplicaciones:
• Otros • Cota inferior
• Scan de Graham
Fundamentos de Geometría
Computacional I.T.I. Gestión
• Anchura • Diámetro
Algoritmos: Divide y Vencerás
1) Ordenar los puntos por abscisa
2) Dividir los puntos de S en dos subconjuntos: S1 con los n/2 puntos más a la izquierda y S2 con n/2 puntos más a la derecha
3) Calcular, recursivamente CH(A) y CH(B)
4) Unir CH(A) y CH(B) para obtener CH(S).
![Page 52: Tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/Tema 1-Envolvente convexa(1... · puntos de S y dejan a todo el ... Algoritmos: • Quickhull • Ptos. extremos](https://reader031.vdocumento.com/reader031/viewer/2022012405/5bacedb009d3f29b4f8ca086/html5/thumbnails/52.jpg)
Algoritmos:
• Quickhull • Marcha de Jarvis
• Ptos. extremos
Tema 1 Envolvente convexa
Definiciones
Aplicaciones:
• Otros • Cota inferior
• Scan de Graham
Fundamentos de Geometría
Computacional I.T.I. Gestión
• Anchura • Diámetro
Algoritmos: Divide y Vencerás
1) Ordenar los puntos por abscisa
2) Dividir los puntos de S en dos subconjuntos: S1 con los n/2 puntos más a la izquierda y S2 con n/2 puntos más a la derecha
3) Calcular, recursivamente CH(A) y CH(B)
4) Unir CH(A) y CH(B) para obtener CH(S).
![Page 53: Tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/Tema 1-Envolvente convexa(1... · puntos de S y dejan a todo el ... Algoritmos: • Quickhull • Ptos. extremos](https://reader031.vdocumento.com/reader031/viewer/2022012405/5bacedb009d3f29b4f8ca086/html5/thumbnails/53.jpg)
Algoritmos:
• Quickhull • Marcha de Jarvis
• Ptos. extremos
Tema 1 Envolvente convexa
Definiciones
Aplicaciones:
• Otros • Cota inferior
• Scan de Graham
Fundamentos de Geometría
Computacional I.T.I. Gestión
• Anchura • Diámetro
Algoritmos: Divide y Vencerás
1) Ordenar los puntos por abscisa
2) Dividir los puntos de S en dos subconjuntos: S1 con los n/2 puntos más a la izquierda y S2 con n/2 puntos más a la derecha
3) Calcular, recursivamente CH(A) y CH(B)
4) Unir CH(A) y CH(B) para obtener CH(S).
![Page 54: Tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/Tema 1-Envolvente convexa(1... · puntos de S y dejan a todo el ... Algoritmos: • Quickhull • Ptos. extremos](https://reader031.vdocumento.com/reader031/viewer/2022012405/5bacedb009d3f29b4f8ca086/html5/thumbnails/54.jpg)
Algoritmos:
• Quickhull • Marcha de Jarvis
• Ptos. extremos
Tema 1 Envolvente convexa
Definiciones
Aplicaciones:
• Otros • Cota inferior
• Scan de Graham
Fundamentos de Geometría
Computacional I.T.I. Gestión
• Anchura • Diámetro
Algoritmos: Divide y vencerás
B
4) Unir CH(A) y CH(B) para obtener CH(S).
Tangente inferior
Tangente superior
A
![Page 55: Tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/Tema 1-Envolvente convexa(1... · puntos de S y dejan a todo el ... Algoritmos: • Quickhull • Ptos. extremos](https://reader031.vdocumento.com/reader031/viewer/2022012405/5bacedb009d3f29b4f8ca086/html5/thumbnails/55.jpg)
Algoritmos:
• Quickhull • Marcha de Jarvis
• Ptos. extremos
Tema 1 Envolvente convexa
Definiciones
Aplicaciones:
• Otros • Cota inferior
• Scan de Graham
Fundamentos de Geometría
Computacional I.T.I. Gestión
• Anchura • Diámetro
Algoritmos: Divide y vencerás
B A
4) Unir CH(A) y CH(B) para obtener CH(S).
Tangente inferior
Tangente superior
0
1 2
3
4
5
6 7
8
0
1 2
3
4
5
6
7 8
9
10
![Page 56: Tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/Tema 1-Envolvente convexa(1... · puntos de S y dejan a todo el ... Algoritmos: • Quickhull • Ptos. extremos](https://reader031.vdocumento.com/reader031/viewer/2022012405/5bacedb009d3f29b4f8ca086/html5/thumbnails/56.jpg)
Algoritmos:
• Quickhull • Marcha de Jarvis
• Ptos. extremos
Tema 1 Envolvente convexa
Definiciones
Aplicaciones:
• Otros • Cota inferior
• Scan de Graham
Fundamentos de Geometría
Computacional I.T.I. Gestión
• Anchura • Diámetro
Algoritmos: Divide y vencerás
B
4) Unir CH(A) y CH(B) para obtener CH(S).
0
1 2
3
4
5
6
7 8
9
10
TANGENTE INFERIOR
a=punto de A más a la dcha
b=punto de B más a la izda
While T=ab no sea tangente a A y a B do
While T=ab no sea tangente a A do a=a-1; (mód |A|)
While T=ab no sea tangente a B do b=b+1; (mód |B|)
A
0
1 2
3
4
5
6 7
8
a b
![Page 57: Tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/Tema 1-Envolvente convexa(1... · puntos de S y dejan a todo el ... Algoritmos: • Quickhull • Ptos. extremos](https://reader031.vdocumento.com/reader031/viewer/2022012405/5bacedb009d3f29b4f8ca086/html5/thumbnails/57.jpg)
Algoritmos:
• Quickhull • Marcha de Jarvis
• Ptos. extremos
Tema 1 Envolvente convexa
Definiciones
Aplicaciones:
• Otros • Cota inferior
• Scan de Graham
Fundamentos de Geometría
Computacional I.T.I. Gestión
• Anchura • Diámetro
Algoritmos: Divide y vencerás
B
4) Unir CH(A) y CH(B) para obtener CH(S).
0
1 2
3
4
5
6
7 8
9
10
TANGENTE INFERIOR
a=punto de A más a la dcha
b=punto de B más a la izda
While T=ab no sea tangente a A y a B do
While T=ab no sea tangente a A do a=a-1; (mód |A|)
While T=ab no sea tangente a B do b=b+1; (mód |B|)
A
0
1 2
3
4
5
6 7
8
![Page 58: Tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/Tema 1-Envolvente convexa(1... · puntos de S y dejan a todo el ... Algoritmos: • Quickhull • Ptos. extremos](https://reader031.vdocumento.com/reader031/viewer/2022012405/5bacedb009d3f29b4f8ca086/html5/thumbnails/58.jpg)
Algoritmos:
• Quickhull • Marcha de Jarvis
• Ptos. extremos
Tema 1 Envolvente convexa
Definiciones
Aplicaciones:
• Otros • Cota inferior
• Scan de Graham
Fundamentos de Geometría
Computacional I.T.I. Gestión
• Anchura • Diámetro
Algoritmos: Divide y vencerás
B
4) Unir CH(A) y CH(B) para obtener CH(S).
0
1 2
3
4
5
6
7 8
9
10
TANGENTE SUPERIOR
a=punto de A más a la dcha
b=punto de B más a la izda
While T=ab no sea tangente a A y a B do
While T=ab no sea tangente a A do a=a+1; (mód |A|)
While T=ab no sea tangente a B do b=b-1; (mód |B|)
A
0
1 2
3
4
5
6 7
8
![Page 59: Tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/Tema 1-Envolvente convexa(1... · puntos de S y dejan a todo el ... Algoritmos: • Quickhull • Ptos. extremos](https://reader031.vdocumento.com/reader031/viewer/2022012405/5bacedb009d3f29b4f8ca086/html5/thumbnails/59.jpg)
Algoritmos:
• Quickhull • Marcha de Jarvis
• Ptos. extremos
Tema 1 Envolvente convexa
Definiciones
Aplicaciones:
• Otros • Cota inferior
• Scan de Graham
Fundamentos de Geometría
Computacional I.T.I. Gestión
• Anchura • Diámetro
Algoritmos: Divide y vencerás
1) Ordenar los puntos por abscisa
2) Dividir los puntos de S en dos subconjuntos: S1 con los n/2 puntos más a la izquierda y S2 con n/2 puntos más a la derecha
3) Calcular, recursivamente CH(A) y CH(B)
4) Unir CH(A) y CH(B) para obtener CH(S).
O(n lg n) (preprocesamiento)
=
2 T(n/2)
T(n)
+
O(n)
T(n) = 2 T(n/2)+O(n) T(n) ∈ O(n lg n)
![Page 60: Tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/Tema 1-Envolvente convexa(1... · puntos de S y dejan a todo el ... Algoritmos: • Quickhull • Ptos. extremos](https://reader031.vdocumento.com/reader031/viewer/2022012405/5bacedb009d3f29b4f8ca086/html5/thumbnails/60.jpg)
Algoritmos:
• Quickhull • Marcha de Jarvis
• Ptos. extremos
Tema 1 Envolvente convexa
Definiciones
Aplicaciones:
• Otros • Cota inferior
• Scan de Graham
Fundamentos de Geometría
Computacional I.T.I. Gestión
• Anchura • Diámetro
Algoritmos: Incremental
Añadimos los puntos uno a uno.
En cada paso comprobamos si el nuevo punto está en el interior de la envolvente:
• SÍ: Lo ignoramos.
• NO: Lo incorporamos a la envolvente.
![Page 61: Tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/Tema 1-Envolvente convexa(1... · puntos de S y dejan a todo el ... Algoritmos: • Quickhull • Ptos. extremos](https://reader031.vdocumento.com/reader031/viewer/2022012405/5bacedb009d3f29b4f8ca086/html5/thumbnails/61.jpg)
Algoritmos:
• Quickhull • Marcha de Jarvis
• Ptos. extremos
Tema 1 Envolvente convexa
Definiciones
Aplicaciones:
• Otros • Cota inferior
• Scan de Graham
Fundamentos de Geometría
Computacional I.T.I. Gestión
• Anchura • Diámetro
Algoritmos: Incremental
Añadimos los puntos uno a uno.
En cada paso comprobamos si el nuevo punto está en el interior de la envolvente:
• SÍ: Lo ignoramos.
• NO: Lo incorporamos a la envolvente.
![Page 62: Tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/Tema 1-Envolvente convexa(1... · puntos de S y dejan a todo el ... Algoritmos: • Quickhull • Ptos. extremos](https://reader031.vdocumento.com/reader031/viewer/2022012405/5bacedb009d3f29b4f8ca086/html5/thumbnails/62.jpg)
Algoritmos:
• Quickhull • Marcha de Jarvis
• Ptos. extremos
Tema 1 Envolvente convexa
Definiciones
Aplicaciones:
• Otros • Cota inferior
• Scan de Graham
Fundamentos de Geometría
Computacional I.T.I. Gestión
• Anchura • Diámetro
Algoritmos: Incremental
Añadimos los puntos uno a uno.
En cada paso comprobamos si el nuevo punto está en el interior de la envolvente:
• SÍ: Lo ignoramos.
• NO: Lo incorporamos a la envolvente.
![Page 63: Tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/Tema 1-Envolvente convexa(1... · puntos de S y dejan a todo el ... Algoritmos: • Quickhull • Ptos. extremos](https://reader031.vdocumento.com/reader031/viewer/2022012405/5bacedb009d3f29b4f8ca086/html5/thumbnails/63.jpg)
Algoritmos:
• Quickhull • Marcha de Jarvis
• Ptos. extremos
Tema 1 Envolvente convexa
Definiciones
Aplicaciones:
• Otros • Cota inferior
• Scan de Graham
Fundamentos de Geometría
Computacional I.T.I. Gestión
• Anchura • Diámetro
Algoritmos: Incremental
Añadimos los puntos uno a uno.
En cada paso comprobamos si el nuevo punto está en el interior de la envolvente:
• SÍ: Lo ignoramos.
• NO: Lo incorporamos a la envolvente.
Al añadir un nuevo punto puede que tengamos que eliminar alguno de la envolvente.
![Page 64: Tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/Tema 1-Envolvente convexa(1... · puntos de S y dejan a todo el ... Algoritmos: • Quickhull • Ptos. extremos](https://reader031.vdocumento.com/reader031/viewer/2022012405/5bacedb009d3f29b4f8ca086/html5/thumbnails/64.jpg)
Algoritmos:
• Quickhull • Marcha de Jarvis
• Ptos. extremos
Tema 1 Envolvente convexa
Definiciones
Aplicaciones:
• Otros • Cota inferior
• Scan de Graham
Fundamentos de Geometría
Computacional I.T.I. Gestión
• Anchura • Diámetro
Algoritmos: Incremental
Añadimos los puntos uno a uno.
En cada paso comprobamos si el nuevo punto está en el interior de la envolvente:
• SÍ: Lo ignoramos.
• NO: Lo incorporamos a la envolvente.
Al añadir un nuevo punto puede que tengamos que eliminar alguno de la envolvente.
![Page 65: Tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/Tema 1-Envolvente convexa(1... · puntos de S y dejan a todo el ... Algoritmos: • Quickhull • Ptos. extremos](https://reader031.vdocumento.com/reader031/viewer/2022012405/5bacedb009d3f29b4f8ca086/html5/thumbnails/65.jpg)
Algoritmos:
• Quickhull • Marcha de Jarvis
• Ptos. extremos
Tema 1 Envolvente convexa
Definiciones
Aplicaciones:
• Otros • Cota inferior
• Scan de Graham
Fundamentos de Geometría
Computacional I.T.I. Gestión
• Anchura • Diámetro
Algoritmos: Incremental
Añadimos los puntos uno a uno.
En cada paso comprobamos si el nuevo punto está en el interior de la envolvente:
• SÍ: Lo ignoramos.
• NO: Lo incorporamos a la envolvente.
Al añadir un nuevo punto puede que tengamos que eliminar alguno de la envolvente.
Cada inserción a lo bruto requiere O(n), por lo que serían necesarias O(n2) operaciones, pero puede mejorarse a O(log n), obteniendo O(n log n).
![Page 66: Tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/Tema 1-Envolvente convexa(1... · puntos de S y dejan a todo el ... Algoritmos: • Quickhull • Ptos. extremos](https://reader031.vdocumento.com/reader031/viewer/2022012405/5bacedb009d3f29b4f8ca086/html5/thumbnails/66.jpg)
Algoritmos:
• Quickhull • Marcha de Jarvis
• Ptos. extremos
Tema 1 Envolvente convexa
Definiciones
Aplicaciones:
• Anchura • Diámetro
• Cota inferior
• Scan de Graham
• Otros
Fundamentos de Geometría
Computacional I.T.I. Gestión
Algoritmos: Cota inferior
Construir la envolvente convexa de n puntos requiere, al menos, Ω(n log n) operaciones, ya que es equivalente a ordenar n números.
x -3 4 -1 5 3
(x,x2) (-3,9) (4,16) (-1,1) (5,25) (3,9)
(-3,9) (-1,1) (3,9) (4,16) (5,25)
![Page 67: Tema 1 - asignatura.us.esasignatura.us.es/fgcitig/presentaciones/Tema 1-Envolvente convexa(1... · puntos de S y dejan a todo el ... Algoritmos: • Quickhull • Ptos. extremos](https://reader031.vdocumento.com/reader031/viewer/2022012405/5bacedb009d3f29b4f8ca086/html5/thumbnails/67.jpg)
Algoritmos:
• Quickhull • Marcha de Jarvis
• Ptos. extremos
Tema 1 Envolvente convexa
Definiciones
Aplicaciones:
• Anchura • Diámetro
• Cota inferior
• Scan de Graham
• Otros
Fundamentos de Geometría
Computacional I.T.I. Gestión
Algoritmos: Cota inferior
Construir la envolvente convexa de n puntos requiere, al menos, Ω(n log n) operaciones, ya que es equivalente a ordenar n números.
x -3 4 -1 5 3
(x,x2) (-3,9) (4,16) (-1,1) (5,25) (3,9)
(-3,9) (-1,1) (3,9) (4,16) (5,25)