Jesús Valenzuela
http://personal.us.es/jesusv
Aplicaciones
(anchura y diámetro)
Parte 2: Aplicaciones
(anchura y diámetro)
Matemática
Aplicada I
Envolvente convexa:
Envolvente
convexa
Tema 1
Matemática
Aplicada I
Aplicaciones
(anchura y diámetro)
Anchura: La distancia más corta entre paralelas que
contienen el conjunto.
Diámetro: La mayor distancia entre dos puntos del
conjunto.
Jesús Valenzuela
http://personal.us.es/jesusv
Envolvente convexa:
Aplicaciones de la envolvente
convexa
Tema 1
Anchura de un conjunto
Jesús Valenzuela
http://personal.us.es/jesusv
La distancia más corta entre paralelas que contienen
a toda la nube en su interior se llama anchura.
Lema: La anchura equivale al cálculo de la recta centro.
Aplicaciones
(anchura y diámetro)
Envolvente convexa:
Recta centro (que minimiza la
Matemática
distancia a los puntos de la nube)Aplicada I
Tema 1
Anchura de un conjunto
Jesús Valenzuela
http://personal.us.es/jesusv
La distancia más corta entre paralelas que contienen
a toda la nube en su interior se llama anchura.
Aplicaciones
(anchura y diámetro)
Usaremos el método de
rotación de un calibre
(rotating calliper).
Envolvente convexa:
Lema: La anchura de una nube
de puntos la determina un par
antipodal arista-punto de su
envolvente convexa.
Matemática
Aplicada I
Tema 1
Anchura de un conjunto
Jesús Valenzuela
http://personal.us.es/jesusv
Empezamos en los vértices norte y sur de la
envolvente.
• Mido los ángulos entre
cada recta y la siguiente
arista de la envolvente.
• Roto ambas rectas
hasta llegar al siguiente
más pequeño.
• Almaceno los nuevos
pares antipodales.
Aplicaciones
(anchura y diámetro)
En cada paso:
Matemática
Aplicada I
Envolvente convexa:
Trazamos dos rectas horizontales (calibre).
Tema 1
Anchura de un conjunto
Jesús Valenzuela
http://personal.us.es/jesusv
Empezamos en los vértices norte y sur de la
envolvente.
• Mido los ángulos entre
cada recta y la siguiente
arista de la envolvente.
• Roto ambas rectas
hasta llegar al siguiente
más pequeño.
• Almaceno los nuevos
pares antipodales.
Aplicaciones
(anchura y diámetro)
En cada paso:
Matemática
Aplicada I
Envolvente convexa:
Trazamos dos rectas horizontales (calibre).
Tema 1
Anchura de un conjunto
Jesús Valenzuela
http://personal.us.es/jesusv
Empezamos en los vértices norte y sur de la
envolvente.
• Mido los ángulos entre
cada recta y la siguiente
arista de la envolvente.
• Roto ambas rectas
hasta llegar al siguiente
más pequeño.
• Almaceno los nuevos
pares antipodales.
Aplicaciones
(anchura y diámetro)
En cada paso:
Matemática
Aplicada I
Envolvente convexa:
Trazamos dos rectas horizontales (calibre).
Tema 1
Anchura de un conjunto
Jesús Valenzuela
http://personal.us.es/jesusv
Empezamos en los vértices norte y sur de la
envolvente.
• Mido los ángulos entre
cada recta y la siguiente
arista de la envolvente.
• Roto ambas rectas
hasta llegar al siguiente
más pequeño.
• Almaceno los nuevos
pares antipodales.
Aplicaciones
(anchura y diámetro)
En cada paso:
Matemática
Aplicada I
Envolvente convexa:
Trazamos dos rectas horizontales (calibre).
Tema 1
Anchura de un conjunto
Jesús Valenzuela
http://personal.us.es/jesusv
Empezamos en los vértices norte y sur de la
envolvente.
• Mido los ángulos entre
cada recta y la siguiente
arista de la envolvente.
• Roto ambas rectas
hasta llegar al siguiente
más pequeño.
• Almaceno los nuevos
pares antipodales.
Aplicaciones
(anchura y diámetro)
En cada paso:
Matemática
Aplicada I
Envolvente convexa:
Trazamos dos rectas horizontales (calibre).
Tema 1
Anchura de un conjunto
Jesús Valenzuela
http://personal.us.es/jesusv
Empezamos en los vértices norte y sur de la
envolvente.
• Mido los ángulos entre
cada recta y la siguiente
arista de la envolvente.
• Roto ambas rectas
hasta llegar al siguiente
más pequeño.
• Almaceno los nuevos
pares antipodales.
Aplicaciones
(anchura y diámetro)
En cada paso:
Matemática
Aplicada I
Envolvente convexa:
Trazamos dos rectas horizontales (calibre).
Tema 1
Anchura de un conjunto
Jesús Valenzuela
http://personal.us.es/jesusv
Empezamos en los vértices norte y sur de la
envolvente.
• Mido los ángulos entre
cada recta y la siguiente
arista de la envolvente.
• Roto ambas rectas
hasta llegar al siguiente
más pequeño.
• Almaceno los nuevos
pares antipodales.
Aplicaciones
(anchura y diámetro)
En cada paso:
Matemática
Aplicada I
Envolvente convexa:
Trazamos dos rectas horizontales (calibre).
Tema 1
Anchura de un conjunto
Jesús Valenzuela
http://personal.us.es/jesusv
Empezamos en los vértices norte y sur de la
envolvente.
• Mido los ángulos entre
cada recta y la siguiente
arista de la envolvente.
• Roto ambas rectas
hasta llegar al siguiente
más pequeño.
• Almaceno los nuevos
pares antipodales.
Aplicaciones
(anchura y diámetro)
En cada paso:
Matemática
Aplicada I
Envolvente convexa:
Trazamos dos rectas horizontales (calibre).
Tema 1
Anchura de un conjunto
Jesús Valenzuela
http://personal.us.es/jesusv
Empezamos en los vértices norte y sur de la
envolvente.
• Mido los ángulos entre
cada recta y la siguiente
arista de la envolvente.
• Roto ambas rectas
hasta llegar al siguiente
más pequeño.
• Almaceno los nuevos
pares antipodales.
Aplicaciones
(anchura y diámetro)
En cada paso:
Algunos vértices no son
antipodales de ninguna arista.
Matemática
Aplicada I
Envolvente convexa:
Trazamos dos rectas horizontales (calibre).
Tema 1
Anchura de un conjunto
Jesús Valenzuela
http://personal.us.es/jesusv
Empezamos en los vértices norte y sur de la
envolvente.
• Mido los ángulos entre
cada recta y la siguiente
arista de la envolvente.
• Roto ambas rectas
hasta llegar al siguiente
más pequeño.
• Almaceno los nuevos
pares antipodales.
Aplicaciones
(anchura y diámetro)
En cada paso:
Matemática
Aplicada I
Envolvente convexa:
Trazamos dos rectas horizontales (calibre).
Tema 1
Anchura de un conjunto
Jesús Valenzuela
http://personal.us.es/jesusv
Empezamos en los vértices norte y sur de la
envolvente.
• Mido los ángulos entre
cada recta y la siguiente
arista de la envolvente.
• Roto ambas rectas
hasta llegar al siguiente
más pequeño.
• Almaceno los nuevos
pares antipodales.
Aplicaciones
(anchura y diámetro)
En cada paso:
Matemática
Aplicada I
Envolvente convexa:
Trazamos dos rectas horizontales (calibre).
Tema 1
Anchura de un conjunto
Jesús Valenzuela
http://personal.us.es/jesusv
Empezamos en los vértices norte y sur de la
envolvente.
• Mido los ángulos entre
cada recta y la siguiente
arista de la envolvente.
• Roto ambas rectas
hasta llegar al siguiente
más pequeño.
• Almaceno los nuevos
pares antipodales.
Aplicaciones
(anchura y diámetro)
En cada paso:
Matemática
Aplicada I
Envolvente convexa:
Trazamos dos rectas horizontales (calibre).
Tema 1
Anchura de un conjunto
Jesús Valenzuela
http://personal.us.es/jesusv
Empezamos en los vértices norte y sur de la
envolvente.
• Mido los ángulos entre
cada recta y la siguiente
arista de la envolvente.
• Roto ambas rectas
hasta llegar al siguiente
más pequeño.
• Almaceno los nuevos
pares antipodales.
Aplicaciones
(anchura y diámetro)
En cada paso:
Matemática
Aplicada I
Envolvente convexa:
Trazamos dos rectas horizontales (calibre).
Tema 1
Anchura de un conjunto
Jesús Valenzuela
http://personal.us.es/jesusv
Lema: La anchura de una nube de puntos la determina
un par antipodal arista-punto de su envolvente convexa.
Aplicaciones
(anchura y diámetro)
Teorema: Es posible
determinar la anchura de
un conjunto en tiempo
lineal a partir de su
envolvente convexa.
Matemática
Aplicada I
Envolvente convexa:
Lema: Es posible determinar todos los pares antipodales
arista-punto de un polígono convexo en tiempo lineal.
Tema 1
Aplicaciones
(anchura y diámetro)
Matemática
Aplicada I
Envolvente convexa:
Anchura de un conjunto
Jesús Valenzuela
http://personal.us.es/jesusv
Tema 1
Aplicaciones
(anchura y diámetro)
Matemática
Aplicada I
Envolvente convexa:
Anchura de un conjunto
Jesús Valenzuela
http://personal.us.es/jesusv
Tema 1
Aplicaciones
(anchura y diámetro)
Matemática
Aplicada I
Envolvente convexa:
Anchura de un conjunto
Jesús Valenzuela
http://personal.us.es/jesusv
Tema 1
Aplicaciones
(anchura y diámetro)
Matemática
Aplicada I
Envolvente convexa:
Anchura de un conjunto
Jesús Valenzuela
http://personal.us.es/jesusv
Tema 1
Aplicaciones
(anchura y diámetro)
Matemática
Aplicada I
Envolvente convexa:
Anchura de un conjunto
Jesús Valenzuela
http://personal.us.es/jesusv
Tema 1
Aplicaciones
(anchura y diámetro)
Matemática
Aplicada I
Envolvente convexa:
Anchura de un conjunto
Jesús Valenzuela
http://personal.us.es/jesusv
Tema 1
Aplicaciones
(anchura y diámetro)
Matemática
Aplicada I
Envolvente convexa:
Anchura de un conjunto
Jesús Valenzuela
http://personal.us.es/jesusv
Tema 1
Aplicaciones
(anchura y diámetro)
Matemática
Aplicada I
Envolvente convexa:
Anchura de un conjunto
Jesús Valenzuela
http://personal.us.es/jesusv
Tema 1
Anchura de un conjunto
Jesús Valenzuela
http://personal.us.es/jesusv
¿Conoces alguna figura de anchura constante?
…que no sea un círculo…
Aplicaciones
(anchura y diámetro)
Ventana de la Catedral de
Notre Dame de Brujas
Matemática
Aplicada I
Envolvente convexa:
La más conocida es el Triángulo de Reuleaux
http://kmoddl.library.cornell.edu/tutorials/02/
Tema 1
Anchura de un conjunto
Jesús Valenzuela
http://personal.us.es/jesusv
¿Conoces alguna figura de anchura constante?
…que no sea un círculo…
La más conocida es el Triángulo de Reuleaux
Matemática
Aplicada I
http://mecanicavirtual.iespana.es/inyeccion-wankel.htm
Aplicaciones
(anchura y diámetro)
Envolvente convexa:
que se utiliza, por ejemplo, en el motor Wankel (vídeo).
Tema 1
Anchura de un conjunto
Jesús Valenzuela
http://personal.us.es/jesusv
Aunque podemos construir muchas más:
Aplicaciones
(anchura y diámetro)
Envolvente convexa:
Matemática
Aplicada I
http://kmoddl.library.cornell.edu/tutorials/02/
Tema 1
Diámetro de un conjunto
Jesús Valenzuela
http://personal.us.es/jesusv
El par más alejado
Aplicaciones
(anchura y diámetro)
Lema: El diámetro de una nube de puntos coincide con
el diámetro de sus puntos extremos.
Matemática
Aplicada I
Envolvente convexa:
Entre muchos puntos en el plano encontrar los dos más
alejados
Tema 1
Aplicaciones
(anchura y diámetro)
Matemática
Aplicada I
Envolvente convexa:
Diámetro de un conjunto
Jesús Valenzuela
http://personal.us.es/jesusv
Tema 1
Matemática
Aplicada I
Envolvente convexa:
Puntos antipodales
Un par de puntos se llaman antipodales si por ellos pasan
paralelas que contienen a toda la nube en su interior
Aplicaciones
(anchura y diámetro)
Diámetro de un conjunto
Jesús Valenzuela
http://personal.us.es/jesusv
Tema 1
Diámetro de un conjunto
Jesús Valenzuela
http://personal.us.es/jesusv
Un par de puntos se llaman antipodales si por ellos pasan
paralelas que contienen a toda la nube en su interior
Aplicaciones
(anchura y diámetro)
Envolvente convexa:
Matemática
Aplicada I
Tema 1
Diámetro de un conjunto
Jesús Valenzuela
http://personal.us.es/jesusv
Un par de puntos se llaman antipodales si por ellos pasan
paralelas que contienen a toda la nube en su interior
Aplicaciones
(anchura y diámetro)
Envolvente convexa:
Matemática
Aplicada I
Tema 1
Diámetro de un conjunto
Jesús Valenzuela
http://personal.us.es/jesusv
Un par de puntos se llaman antipodales si por ellos pasan
paralelas que contienen a toda la nube en su interior
Aplicaciones
(anchura y diámetro)
Envolvente convexa:
Matemática
Aplicada I
Tema 1
Diámetro de un conjunto
Jesús Valenzuela
http://personal.us.es/jesusv
Lema: El diámetro de una nube de puntos coincide con la
distancia entre su par antipodal punto-punto más lejano.
Aplicaciones
(anchura y diámetro)
Envolvente convexa:
Matemática
Aplicada I
Tema 1
Diámetro de un conjunto
Jesús Valenzuela
http://personal.us.es/jesusv
Los vértices antipodales a un vértice v dado son todos
aquellos comprendidos entre los vértices antipodales a las
dos aristas incidentes en v
Aplicaciones
(anchura y diámetro)
Envolvente convexa:
Matemática
Aplicada I
Tema 1
Diámetro de un conjunto
Jesús Valenzuela
http://personal.us.es/jesusv
Los vértices antipodales a un vértice v dado son todos
aquellos comprendidos entre los vértices antipodales a las
dos aristas incidentes en v
Aplicaciones
(anchura y diámetro)
Corolario 5.1: Todos los pares antipodales vértice-vértice pueden
ser calculados en tiempo lineal una vez conocida la envolvente
convexa.
Envolvente convexa:
Teorema: El diámetro de un conjunto pueden ser calculados en
tiempo lineal una vez conocida la envolvente convexa.
Matemática
Aplicada I
Tema 1
Problemas
Jesús Valenzuela
http://personal.us.es/jesusv
1.- Probar que dado un conjunto de puntos en el plano, se puede encontrar en
tiempo O(n log n) un polígono que tenga a dicho conjunto como sus vértices.
Aplicaciones
(anchura y diámetro)
3.- Dado un conjunto con n puntos rojos y n puntos azules en el plano, dar un algoritmo
que una cada punto rojo con un azul mediante segmentos que no se corten entre sí
(emparejamiento geométrico perfecto).
Matemática
Aplicada I
Envolvente convexa:
2.- Sea P un polígono monótono (existe una recta tal que toda perpendicular a dicha recta
a lo más corta en dos puntos al polígono). Diseñar un algoritmo que calcule su envolvente
convexa en tiempo lineal.
Tema 1
Descargar

Diapositiva 1