TEMAS DE GEOMETRÍA

La geometría computacional es una rama de la informática dedicada al estudio de algoritmos que se puede establecer en términos de geometría . Algunos problemas puramente geométricos surgen del estudio de los algoritmos geométricos computacionales , y estos problemas también se consideran parte de la geometría computacional. Si bien la geometría computacional moderna es un desarrollo reciente, es uno de los campos más antiguos de computación con una historia que se remonta a la antigüedad.

La complejidad computacional es fundamental para la geometría computacional, con una gran importancia práctica si los algoritmos se utilizan en conjuntos de datos muy grandes que contienen decenas o cientos de millones de puntos. Para tales conjuntos, la diferencia entre O ( n ² ) y O ( n log n ) puede ser la diferencia entre días y segundos de cálculo.

El principal impulso para el desarrollo de la geometría computacional como disciplina fue el progreso en los gráficos por computadora y el diseño y fabricación asistidos por computadora ( CAD / CAM ), pero muchos problemas en la geometría computacional son de naturaleza clásica y pueden provenir de la visualización matemática .

Otras aplicaciones importantes de la geometría computacional incluyen robótica (planificación de movimiento y problemas de visibilidad), sistemas de información geográfica (GIS) (ubicación geométrica y búsqueda, planificación de rutas), diseño de circuitos integrados (diseño y verificación de geometría de circuitos integrados), ingeniería asistida por computadora (CAE) (Generación de malla), Visión por computador ( Reconstrucción 3D).

Las principales ramas de la geometría computacional son:

• Geometría computacional combinatoria , también llamada geometría algorítmica , que trata los objetos geométricos como entidades discretas . Un libro de base en el tema por Preparata y Shamos fecha el primer uso del término "geometría computacional" en este sentido en 1975. ^[1]
• Geometría computacional numérica , también llamada geometría de máquina , diseño geométrico asistido por computadora (CAGD, por sus siglas en inglés) o modelado geométrico , que se ocupa principalmente de representar objetos del mundo real en formas adecuadas para cálculos computacionales en sistemas CAD / CAM. Esta rama puede verse como un desarrollo adicional de la geometría descriptiva y, a menudo, se considera una rama de gráficos de computadora o CAD. El término "geometría computacional" en este sentido ha estado en uso desde 1971.

Combinatoria geometría computacional [ editar ]

El objetivo principal de la investigación en geometría computacional combinatoria es desarrollar algoritmos y estructuras de datos eficientes para resolver problemas planteados en términos de objetos geométricos básicos: puntos, segmentos de línea, polígonos , poliedros , etc.

Algunos de estos problemas parecen tan simples que no fueron considerados como problemas hasta la llegada de las computadoras . Considere, por ejemplo, el problema de par más cercano :

• Dados n puntos en el plano, encuentra los dos con la menor distancia entre sí.

Uno podría calcular las distancias entre todos los pares de puntos, de los cuales hay n (n-1) / 2 , luego elegir el par con la distancia más pequeña. Este algoritmo de fuerza bruta lleva tiempo O ( n ² ); Es decir, su tiempo de ejecución es proporcional al cuadrado del número de puntos. Un resultado clásico en geometría computacional fue la formulación de un algoritmo que toma O ( n log n ). También se han descubierto los algoritmos aleatoriosque toman O ( n ) el tiempo esperado, ^[3] , así como un algoritmo determinista que toma el tiempo O ( n log log n), ^[4] .

Clases de problemas [ editar ]

Los problemas centrales de la geometría computacional se pueden clasificar de diferentes maneras, según diversos criterios. Las siguientes clases generales pueden ser distinguidas.

Problemas estáticos [ editar ]

En los problemas de esta categoría, se da alguna entrada y la salida correspondiente necesita ser construida o encontrada. Algunos problemas fundamentales de este tipo son:

• Casco convexo : dado un conjunto de puntos, encuentre el poliedro / polígono convexo más pequeño que contenga todos los puntos.
• Intersección de segmento de línea : encuentre las intersecciones entre un conjunto dado de segmentos de línea.
• Triangulación de Delaunay
• Diagrama de Voronoi : dado un conjunto de puntos, divide el espacio según los puntos que están más cerca de los puntos dados.
• Programación lineal
• El par de puntos más cercano : dado un conjunto de puntos, encuentra los dos con la menor distancia entre sí.
• Círculo vacío más grande : dado un conjunto de puntos, encuentra un círculo más grande con su centro dentro de su casco convexo y que no incluya ninguno de ellos.
• Ruta más corta euclidiana : conecta dos puntos en un espacio euclídeo (con obstáculos poliédricos) mediante una ruta más corta.
• Triangulación de polígonos : dado un polígono, divide su interior en triángulos
• Generación de malla
• Operaciones booleanas sobre polígonos.

La complejidad computacional para esta clase de problemas se estima por el tiempo y el espacio (memoria de la computadora) necesarios para resolver una instancia de problema dada.

Problemas de consulta geométrica [ editar ]

En los problemas de consulta geométrica, conocidos comúnmente como problemas de búsqueda geométrica, la entrada consta de dos partes: la parte de espacio de búsqueda y la parte de consulta , que varía según las instancias del problema. Por lo general, el espacio de búsqueda debe procesarse previamente , de manera que se puedan responder de manera eficiente a múltiples consultas.

Algunos problemas fundamentales de consulta geométrica son:

• Búsqueda de rango : preprocesar un conjunto de puntos, para contar de manera eficiente el número de puntos dentro de una región de consulta.
• Ubicación del punto : Dada una partición del espacio en celdas, produzca una estructura de datos que indique de manera eficiente en qué celda se encuentra el punto de consulta.
• Vecino más cercano : preprocesar un conjunto de puntos, para encontrar de manera eficiente el punto más cercano a un punto de consulta.
• Rastreo de rayos : dado un conjunto de objetos en el espacio, produzca una estructura de datos que indique de manera eficiente qué objeto se interseca primero un rayo de consulta.

Si el espacio de búsqueda es fijo, la complejidad computacional para esta clase de problemas generalmente se estima por:

• El tiempo y el espacio necesarios para construir la estructura de datos a buscar en
• el tiempo (y, a veces, un espacio adicional) para responder a las consultas.

En el caso de que el espacio de búsqueda pueda variar, consulte " Problemas dinámicos ".

Problemas dinámicos [ editar ]

Otra clase importante son los problemas dinámicos , en los cuales el objetivo es encontrar un algoritmo eficiente para encontrar una solución repetidamente después de cada modificación incremental de los datos de entrada (elementos geométricos de entrada o eliminación). Los algoritmos para problemas de este tipo generalmente involucran estructuras de datos dinámicos . Cualquiera de los problemas geométricos computacionales se puede convertir en uno dinámico, al costo de un mayor tiempo de procesamiento. Por ejemplo, el problema de búsqueda de rango se puede convertir en el problema de búsqueda de rango dinámico al proporcionar la adición y / o eliminación de los puntos. El dinámico casco convexo. El problema es hacer un seguimiento del casco convexo, por ejemplo, para el conjunto de puntos que cambian dinámicamente, es decir, mientras se insertan o eliminan los puntos de entrada.

La complejidad computacional para esta clase de problemas es estimada por:

• El tiempo y el espacio necesarios para construir la estructura de datos a buscar en
• el tiempo y el espacio para modificar la estructura de datos buscados después de un cambio incremental en el espacio de búsqueda
• el tiempo (y, a veces, un espacio adicional) para responder a una consulta.

Variaciones [ editar ]

Algunos problemas pueden tratarse como pertenecientes a cualquiera de las categorías, según el contexto. Por ejemplo, considere el siguiente problema.

• Punto en polígono : decida si un punto está dentro o fuera de un polígono dado.

En muchas aplicaciones, este problema se trata como de un solo disparo, es decir, pertenece a la primera clase. Por ejemplo, en muchas aplicaciones de gráficos de computadora, un problema común es encontrar en qué área de la pantalla se hace clic con un puntero . Sin embargo, en algunas aplicaciones, el polígono en cuestión es invariante, mientras que el punto representa una consulta. Por ejemplo, el polígono de entrada puede representar un borde de un país y un punto es una posición de un avión, y el problema es determinar si el avión violó el borde. Finalmente, en el ejemplo mencionado anteriormente de gráficos de computadora, en las aplicaciones CAD , los datos de entrada cambiantes a menudo se almacenan en estructuras de datos dinámicos, que pueden aprovecharse para acelerar las consultas de punto en polígono.

En algunos contextos de problemas de consulta, existen expectativas razonables sobre la secuencia de las consultas, que pueden aprovecharse para estructuras de datos eficientes o para estimaciones de complejidad computacional más estrictas. Por ejemplo, en algunos casos es importante conocer el peor de los casos para el tiempo total para la secuencia completa de N consultas, en lugar de una sola consulta. Ver también " análisis amortizado ".

Numerical geometría computacional [ editar ]

Artículo principal: diseño geométrico asistido por ordenador.

Esta rama también se conoce como modelado geométrico y diseño geométrico asistido por computadora(CAGD).

Los problemas centrales son el modelado y la representación de curvas y superficies.

Los instrumentos más importantes aquí son las curvas paramétricas y las superficies paramétricas , como las curvas de Bézier , las curvas spline y las superficies. Un importante enfoque no paramétrico es el método de nivel establecido .

Las áreas de aplicación de la geometría computacional incluyen la construcción naval, aeronaves y las industrias automotrices.

La geometría ordenada es una forma de geometría que presenta el concepto de intermediación (o "intermediación") pero, como la geometría proyectiva , omite la noción básica de medición. La geometría ordenada es una geometría fundamental que forma un marco común para la geometría afín , euclidiana , absoluta e hiperbólica (pero no para la geometría proyectiva).

Historia [ editar ]

Moritz Pasch definió por primera vez una geometría sin referencia a la medición en 1882. Sus axiomas fueron mejorados por Peano (1889), Hilbert (1899) y Veblen (1904). ^[1] : 176 Euclid anticipó el enfoque de Pasch en la definición 4 de Los Elementos : "una línea recta es una línea que se encuentra uniformemente con los puntos sobre sí misma". ^[2]

Conceptos primitivos [ editar ]

Las únicas nociones primitivas en geometría ordenada son los puntos A, B, C, ... y la relación ternaria de intermediación [ABC] que se puede leer como "B está entre A y C".

Definiciones [ editar ]

El segmento AB es el conjunto de puntos P tal que [APB].

El intervalo AB es el segmento AB y sus puntos finales A y B.

El rayo A / B (leído como "el rayo de A lejos de B") es el conjunto de puntos P tal que [PAB].

La línea AB es el intervalo AB y los dos rayos A / B y B / A. Se dice que los puntos en la línea AB son colineales .

Un ángulo consiste en un punto O (el vértice ) y dos rayos no colineales que salen de O (los lados ).

Un triángulo viene dado por tres puntos no colineales (llamados vértices ) y sus tres segmentos AB, BC y CA.

Si tres puntos A, B y C no son colineales, entonces un plano ABC es el conjunto de todos los puntos colineales con pares de puntos en uno o dos de los lados del triángulo ABC.

Si los cuatro puntos A, B, C y D no son coplanares, entonces un ABCD de espacio ( 3 espacios ) es el conjunto de todos los puntos colineales con pares de puntos seleccionados de cualquiera de las cuatro caras (regiones planas) del tetraedro A B C D.

Axiomas de la geometría ordenada [ editar ]

1. Existen al menos dos puntos.
2. Si A y B son puntos distintos, existe una C tal que [ABC].
3. Si [ABC], entonces A y C son distintos (A ≠ C).
4. Si [ABC], entonces [CBA] pero no [CAB].
5. Si C y D son puntos distintos en la línea AB, entonces A está en la línea CD.
6. Si AB es una línea, hay un punto C que no está en la línea AB.
7. ( Axioma de Pasch ) Si ABC es un triángulo y [BCD] y [CEA], entonces existe un punto F en la línea DE para la cual [AFB].
8. Axioma de dimensionalidad :
   1. Para la geometría ordenada plana, todos los puntos están en un plano. O
   2. Si ABC es un plano, entonces existe un punto D que no está en el plano ABC.
9. Todos los puntos están en el mismo plano, espacio, etc. (dependiendo de la dimensión en la que uno elija trabajar).
10. (El Axioma de Dedekind) Para cada partición de todos los puntos en una línea en dos conjuntos no vacíos, de manera que ningún punto de ninguno de los dos se encuentra entre dos puntos del otro, hay un punto de un conjunto que se encuentra entre cada otro punto de ese conjunto y cada uno Punto del otro conjunto.

Estos axiomas están estrechamente relacionados con los axiomas de orden de Hilbert . Para un estudio completo de las axiomatizaciones de la geometría ordenada, consulte. ^[3]

Resultados [ editar ]

Problema de puntos colineales de Sylvester [ editar ]

El teorema de Sylvester-Gallai se puede probar dentro de la geometría ordenada. ^{[4] [1] : 181,2}

Paralelismo [ editar ]

Gauss , Bolyai y Lobachevsky desarrollaron una noción de paralelismo que puede expresarse en geometría ordenada. ^{[1] : 189,90}

Teorema (existencia de paralelismo): dado un punto A y una línea r, no a través de A, existen exactamente dos rayos limitantes de A en el plano Ar que no cumplen con r. Así que hay una línea paralela a través de A que no cumple con r.

Teorema (transmisibilidad del paralelismo): el paralelismo de un rayo y una línea se conserva sumando o restando un segmento del comienzo de un rayo.

La simetría del paralelismo no se puede probar en geometría ordenada. ^[5] Por lo tanto, el concepto "ordenado" de paralelismo no forma una relación de equivalencia en líneas.

geometría parabólica es un espacio homogéneo G / P que es el cociente de un grupo de Lie semisimple G por un subgrupo P parabólico . Más generalmente, los análogos curvos de una geometría parabólica en este sentido también se denominan geometría parabólica: cualquier geometría que se modele en un espacio de este tipo mediante una conexión de Cartan .

Ejemplos [ editar ]

El espacio proyectivo P ⁿ es un ejemplo. Es el espacio homogéneo PGL ( n +1) / H donde H es el grupo de isotropía de una línea. En este espacio geométrico, la noción de una línea recta es significativa, pero no hay un parámetro preferido ("afín") a lo largo de las líneas. El análogo curvo del espacio proyectivo es una variedad en la que la noción de geodésica tiene sentido, pero para la cual no hay parametrizaciones preferidas en esas geodésicas. Una conexión proyectiva es la conexión de Cartan relevante que proporciona un medio para describir una geometría proyectiva pegando copias del espacio proyectivo a los espacios tangentes de la base múltiple. Hablando en general,La geometría proyectiva se refiere al estudio de múltiples con este tipo de conexión.

Otro ejemplo es la esfera conformal . Topológicamente, es la esfera n , pero no hay una noción de longitud definida, solo de ángulo entre curvas. De manera equivalente, esta geometría se describe como una clase de equivalencia de métricas riemannianas en la esfera (llamada clase conforme). El grupo de transformaciones que preservan ángulos sobre la esfera es el grupo de Lorentz O ( n +1,1), y así S ⁿ = O ( n +1,1) / P . Geometría conformales, más ampliamente, el estudio de múltiples con una clase de equivalencia conforme de métricas de Riemann, es decir, múltiples modelados en la esfera conforme. Aquí la conexión de Cartan asociada es la conexión conforme .

Otros ejemplos incluyen:

• Geometría CR , el estudio de múltiples modelado en un hiperquadric real.$${\ displaystyle Q ^ {2 (p + q) -1} = SU (p, q) / P \ subseteq \ mathbb {C} ^ {p + q}}, dónde $${\ displaystyle P}es el estabilizador de una línea isotrópica (ver colector CR )
• contacto con la geometría proyectiva, el estudio de múltiples modelado en $${\ displaystyle SP (n) / P} dónde $${\ displaystyle P}es ese subgrupo del grupo simpléctico que estabiliza la línea generada por el primer vector de base estándar en$${\ displaystyle \ mathbb {R} ^ {2n}}