Doctorado
  1. Comprendiendo el Álgebra  1.1. Teoría de grupos  1.1.1. Propiedades básicas de los grupos  1.1.2. Subgrupos  1.1.3. Cosets y el teorema de Lagrange  1.1.4. Subgrupos normales  1.1.5. Grupo cociente  1.1.6. Homomorfismos de grupos  1.1.7. Teorema de Sylow  1.1.8. Introducción a los grupos libres  1.1.9. ¿Qué son las actividades grupales?  1.1.10. Grupos simples y resolubles  1.2. Teoría de anillos  1.2.1. Anillos e ideales  1.2.2. Introducción a los homomorfismos de anillos  1.2.3. Anillos polinomiales  1.2.4. Dominios Ideales Principales  1.2.5. Dominios de factorización única  1.2.6. Anillos noetherianos  1.2.7. Anillos de Artiniano  1.3. Teoría de campos  1.3.1. Extensiones de campos  1.3.2. División de áreas  1.3.3. Teoría de Galois  1.3.4. Cierre algebraico en teoría de campos  1.3.5. Campos finitos  1.3.6. Extensión trascendental  1.4. Teoría de módulos  1.4.1. Módulos sobre anillos  1.4.2. Módulos libres  1.4.3. Morfismo de módulos  1.4.4. Módulos simples y semisimples  1.4.5. Módulos proyectivos  1.4.6. Módulos inyectivos  1.5. Álgebra lineal  1.5.1. Espacio vectorial  1.5.2. Transformaciones lineales  1.5.3. Comprendiendo Valores Propios y Vectores Propios  1.5.4. Forma canónica  1.5.5. Espacio de producto interior  1.5.6. Teorema Espectral  1.5.7. Descomposición en valores singulares
  2. Entendiendo el Análisis Matemático  2.1. Análisis real  2.1.1. Números reales y completitud  2.1.2. Introducción a las secuencias y series  2.1.3. Continuidad en el análisis real  2.1.4. Diferenciación en el análisis real  2.1.5. Integración de Riemann  2.1.6. Introducción a los espacios métricos  2.1.7. Medida de Lebesgue  2.2. Análisis complejo  2.2.1. Números complejos  2.2.2. Funciones analíticas  2.2.3. Integración de contornos  2.2.4. Teorema de Cauchy  2.2.5. Teorema del residuo  2.2.6. Mapeo conforme  2.3. Análisis funcional  2.3.1. Comprender ubicaciones estándar  2.3.2. Introducción a los espacios de Banach  2.3.3. Espacios de Hilbert  2.3.4. Operadores lineales  2.3.5. Teoría espectral  2.3.6. Operadores compactos  2.4. Teoría de la medida  2.4.1. Álgebra sigma  2.4.2. Medidas e integrales en la teoría de la medida  2.4.3. Integración de Lebesgue  2.4.4. Teorema de convergencia  2.4.5. Teorema de Fubini  2.5. Análisis Armónico  2.5.1. Serie de Fourier  2.5.2. Transformada de Fourier  2.5.3. Teoría de la distribución  2.5.4. Wavelets
  3. Topología  3.1. Topología general  3.1.1. Conjuntos abiertos y cerrados  3.1.2. Continuidad  3.1.3. Introducción a la compacidad  3.1.4. Conectividad en topología general  3.1.5. Topología métrica  3.2. Topología algebraica  3.2.1. Grupo fundamental  3.2.2. Teoría de la homotopía  3.2.3. Teoría de la homología  3.2.4. Cohomología  3.2.5. Secuencia exacta  3.3. Topología diferencial  3.3.1. Variedades suaves  3.3.2. Espacio tangente  3.3.3. Campos vectoriales  3.3.4. Comprensión de las Formas Diferenciales
  4. Geometría  4.1. Geometría diferencial  4.1.1. Curvas y superficies en geometría diferencial  4.1.2. Geometría Riemanniana  4.1.3. Comprendiendo las geodésicas en la geometría diferencial  4.1.4. Curvatura  4.2. Geometría algebraica  4.2.1. Variedades afines y proyectivas  4.2.2. Planes  4.2.3. Separadores e intersecciones  4.2.4. Cohomología en geometría algebraica  4.3. Geometría Computacional  4.3.1. Introducción a las cubiertas convexas en geometría computacional  4.3.2. Triangulación  4.3.3. Diagrama de Voronoi  4.3.4. Algoritmos Geométricos
  5. Teoría de números  5.1. Teoría de números elemental  5.1.1. Divisibilidad en la teoría de números elemental  5.1.2. Congruencia en teoría de números elemental  5.1.3. Aritmética modular  5.2. Teoría analítica de números  5.2.1. Teorema de los números primos  5.2.2. Series de Dirichlet  5.2.3. Zeta y funciones L  5.3. Teoría de números algebraicos  5.3.1. Campos numéricos  5.3.2. Introducción a ideales en teoría de números algebraicos  5.3.3. Grupos de clases en teoría de números algebraicos  5.3.4. Representación de Galois
  6. Compañerismo  6.1. Combinatoria computacional  6.1.1. Función generadora  6.1.2. Relación de recurrencia  6.1.3. Ppermutaion y combinaciones  6.2. Teoría de grafos  6.2.1. Isomorfismo de grafos  6.2.2. Planicidad en teoría de grafos  6.2.3. Coloración de grafos  6.3. Combinatoria extrema  6.3.1. Teoría de Ramsey  6.3.2. Métodos probabilísticos en combinatoria extrema  6.4. Combinatoria algebraica  6.4.1. Métodos de matrices en combinatoria algebraica  6.4.2. Teoría de la representación
  7. Argumentos y fundamentos  7.1. Teoría de conjuntos  7.1.1. Axiomas de Zermelo-Fraenkel  7.1.2. Ordinales y cardinales  7.2. Introducción a la teoría de modelos  7.2.1. Estructuras y teorías en la teoría de modelos  7.2.2. Teorema de compacidad  7.3. Teoría de la demostración  7.3.1. Sistemas formales  7.3.2. Consistencia y completitud
  8. Probabilidad y Estadística  8.1. Teoría de la probabilidad  8.1.1. Variables aleatorias  8.1.2. Expectativa y variación  8.1.3. Teorema central del límite  8.2. Procesos estocásticos  8.2.1. Cadenas de Markov  8.2.2. Movimiento Browniano  8.3. Inferencia estadística  8.3.1. Pruebas de hipótesis  8.3.2. Análisis de regresión
  9. Matemáticas aplicadas  9.1. Análisis numérico en matemáticas aplicadas  9.1.1. Métodos iterativos  9.1.2. Interpolación  9.1.3. Análisis de errores  9.2. Ecuaciones diferenciales parciales  9.2.1. Ecuación elíptica  9.2.2. Ecuación parabólica  9.2.3. Ecuaciones hiperbólicas  9.3. Sistemas dinámicos  9.3.1. Teoría del caos  9.3.2. Análisis de estabilidad en sistemas dinámicos

Doctorado → Geometría → Geometría Computacional ↓


Introducción a las cubiertas convexas en geometría computacional


En el estudio de la geometría computacional, el concepto de "cubierta convexa" es un componente básico. Imagina un conjunto de puntos dispersos en un plano. La cubierta convexa es como envolver una banda elástica alrededor de esos puntos. La banda tomará la forma del polígono convexo más pequeño que puede encerrar todos los puntos dispersos.

Entendiendo las formas convexas

Antes de profundizar en las cubiertas convexas, es importante entender qué significa la convexidad. Una forma es convexa si, para cualquier par de puntos dentro de la forma, el segmento de línea que los conecta yace completamente dentro de la forma. Piénsalo como un globo. Si pinchas dos alfileres en cualquier parte de la superficie del globo y los conectas con un hilo, el hilo no se saldrá del globo.

Definición de cubierta convexa

La cubierta convexa de un conjunto de puntos es el conjunto convexo más pequeño que encierra todos los puntos. Matemáticamente, si tienes un conjunto S de puntos, entonces la cubierta convexa es la intersección de todos los conjuntos convexos que contienen S. Alternativamente, es una frontera que utiliza el perímetro más pequeño mientras encierra todos los puntos.

Representación matemática

La cubierta convexa de un conjunto de puntos S puede ser representada como:

Convex hull(S) = { x : x es una combinación convexa de puntos en S }

Visualización de cubiertas convexas

Ejemplo 1: Cubierta convexa básica

Considera un escenario simple donde el conjunto tiene solo tres puntos que forman un triángulo.

En este ejemplo, la cubierta convexa es el triángulo en sí, ya que los tres puntos son sus vértices.

Ejemplo 2: Un conjunto más complejo

Consideremos algunos puntos más complejos:

Aquí, los puntos forman una figura que incluye un punto interior. La cubierta convexa es un triángulo, excluyendo el punto en (130, 80), que no afecta el perímetro de la cubierta.

Propiedades de la cubierta convexa

Convexidad

La forma resultante es siempre convexa, es decir, cada ángulo interno es menor o igual a 180 grados.

Especificación

Para un conjunto dado de puntos, la cubierta convexa es única. Esta unicidad surge porque no hay diferencia entre la definición de convexidad y la naturaleza del espacio euclidiano.

Minimalismo

La cubierta convexa tiene la frontera más pequeña posible que encierra todos los puntos del conjunto.

Algoritmos para calcular la cubierta convexa

Varios algoritmos pueden calcular la cubierta convexa de un conjunto de puntos, cada uno con diferentes complejidades y casos de uso. Algunos de los algoritmos populares son los siguientes:

Algoritmo del envoltorio de regalo

También conocido como el algoritmo de Jarvis March, es como envolver un regalo moviéndose alrededor del borde de la forma.

1. Comienza en el punto más a la izquierda del conjunto (con la coordenada x más pequeña).
2. Selecciona el punto que haga el ángulo más pequeño en sentido contrario a las agujas del reloj con la línea formada por el punto de inicio.
3. Repite el paso 2 con el punto más recientemente agregado hasta que regreses al punto de partida.

La complejidad computacional del envoltorio de regalo es típicamente O(nh), donde n es el número de puntos en el conjunto de entrada, y h es el número de puntos en la solución.

Escaneo de Graham

Este algoritmo calcula la cubierta convexa ordenando primero los vértices y luego considerándolos uno por uno.

1. Encuentra el punto con la coordenada y más baja, rompiendo el empate con la coordenada x más pequeña.
2. Ordena los puntos en orden creciente del ángulo que forman con el punto elegido en el paso 1 con el eje x.
3. Repite los puntos y elimina los puntos que causan rotación en sentido horario.

Su complejidad computacional es O(n log n), principalmente debido a la operación de ordenamiento inicial.

Algoritmo Quickhull

El algoritmo Quickhull es un método basado en el paradigma de dividir y vencer.

1. Encuentra los puntos con las coordenadas x mínima y máxima, que deben ser parte de la cubierta convexa.
2. Usa un procedimiento recursivo de dividir y vencer para encontrar el conjunto de puntos que forman una cubierta convexa en cada lado de la línea definida por los dos puntos.

La complejidad promedio es O(n log n), mientras que en el peor caso, puede ser O(n^2).

Algoritmo incremental

En este algoritmo, los puntos se agregan uno a uno y la cubierta convexa se actualiza en cada paso.

1. Comienza con un pequeño subconjunto de los puntos que forman la cubierta inicial.
2. Agrega un nuevo punto y verifica si se encuentra dentro del envoltorio actual.
3. Si se encuentra fuera, actualiza el envoltorio para incluir el nuevo punto.

Aunque no es el más eficiente en términos de notación Big-O, este algoritmo puede ser intuitivo y útil en aplicaciones específicas.

Aplicaciones de la cubierta convexa

Las cubiertas convexas tienen muchas aplicaciones prácticas en la geometría computacional y campos relacionados:

Gráficos por computadora

Las cubiertas convexas se utilizan en gráficos por computadora para determinar la frontera de un conjunto de objetos y para detección de colisiones y búsqueda de caminos.

Análisis geográfico

En los sistemas GIS, las cubiertas convexas ayudan a definir la frontera de unidades geográficas, como agrupaciones de ubicaciones.

Reconocimiento de patrones

Se utilizan en el reconocimiento de patrones para dar forma a grupos de puntos, ayudando en la clasificación y detección.

Robótica

En robótica, las cubiertas convexas ayudan en la navegación espacial y planificación de movimientos, proporcionando caminos seguros alrededor de conjuntos de obstáculos.

Conclusión

El estudio de las cubiertas convexas es una puerta de entrada para entender problemas más complejos en la geometría computacional. Aunque su definición es simple, la computación eficiente y la aplicación requieren un conocimiento profundo de la geometría y el diseño de algoritmos. Como un aspecto fundamental de la geometría, las cubiertas convexas siguen siendo un área de investigación activa y desempeñan un papel esencial en una variedad de aplicaciones tecnológicas.


Doctorado → 4.3.1


U
username
0%
completado en Doctorado

← Anterior (4.3)
Geometría Computacional
Siguiente (4.3.2) →
Triangulación

Comentarios 



Introducción a las cubiertas convexas en geometría computacional

https://www.buddymath.com/phd/4.3.1?bmal=es