Hispanopedia WikiLa geometría computacional es una rama de la informática dedicada al estudio de algoritmos que pueden expresarse en términos de geometría . Algunos problemas puramente geométricos surgen del estudio de algoritmos geométricos computacionales, y dichos 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 la informática con una historia que se remonta a la antigüedad.
La complejidad computacional es fundamental para la geometría computacional y tiene una gran importancia práctica si se utilizan algoritmos en conjuntos de datos muy grandes que contienen decenas o cientos de millones de puntos. Para estos conjuntos, la diferencia entre O( n 2 ) 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 la robótica ( planificación de movimiento y problemas de visibilidad), los sistemas de información geográfica (SIG) (ubicación y búsqueda geométrica, planificación de rutas), el diseño de circuitos integrados (diseño y verificación de geometría de CI), la ingeniería asistida por computadora (generación de mallas) y la visión por computadora ( reconstrucción 3D ).
Las principales ramas de la geometría computacional son:
- La geometría computacional combinatoria , también llamada geometría algorítmica , trata los objetos geométricos como entidades discretas . Un libro que sienta las bases sobre el tema, escrito por Preparata y Shamos, data 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) o modelado geométrico , que se ocupa principalmente de representar objetos del mundo real en formas adecuadas para cálculos informáticos en sistemas CAD/CAM. Esta rama puede considerarse un desarrollo posterior de la geometría descriptiva y a menudo se considera una rama de los gráficos por computadora o CAD. El término "geometría computacional" con este significado se ha utilizado desde 1971. [2]
Aunque la mayoría de los algoritmos de geometría computacional se han desarrollado (y se están desarrollando) para computadoras electrónicas, algunos algoritmos se desarrollaron para computadoras no convencionales (por ejemplo, computadoras ópticas [3] ).
Geometría computacional combinatoria
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 se los consideraba problemas hasta la llegada de las computadoras . Consideremos, por ejemplo, el problema del par más cercano :
- Dados n puntos en el plano, encuentre los dos con la menor distancia entre sí.
Se podrían calcular las distancias entre todos los pares de puntos, de los cuales hay n(n-1)/2 , y luego elegir el par con la distancia más pequeña. Este algoritmo de fuerza bruta toma O ( n 2 ) tiempo; 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 algoritmos aleatorios que toman O( n ) tiempo esperado, [4] así como un algoritmo determinista que toma O( n log log n ) tiempo, [5] .
Clases de problemas
Los problemas centrales de la geometría computacional pueden clasificarse de diferentes maneras, según diversos criterios. Se pueden distinguir las siguientes clases generales:
Problema estático
En los problemas de esta categoría se proporciona una entrada y es necesario construir o encontrar la salida correspondiente. Algunos problemas fundamentales de este tipo son:
- Envolvente convexa : dado un conjunto de puntos, encuentre el poliedro/polígono convexo más pequeño que contenga todos los puntos.
- Intersección de segmentos 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, dividir el espacio según qué puntos estén más cerca de los puntos dados.
- Programación lineal
- Par de puntos más cercano : dado un conjunto de puntos, encuentre los dos con la menor distancia entre sí.
- Par de puntos más lejano
- Círculo vacío más grande : dado un conjunto de puntos, encuentre el círculo más grande con su centro dentro de su envoltura convexa y que no encierre a ninguno de ellos.
- Camino más corto euclidiano : conecta dos puntos en un espacio euclidiano (con obstáculos poliédricos) mediante un camino más corto.
- 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 mediante el tiempo y el espacio (memoria de la computadora) necesarios para resolver una instancia de problema determinada.
Problemas de consulta geométrica
En los problemas de consulta geométrica , comúnmente conocidos como problemas de búsqueda geométrica , la entrada consta de dos partes: la parte del espacio de búsqueda y la parte de la consulta , que varía según las instancias del problema. El espacio de búsqueda normalmente debe preprocesarse de manera que se puedan responder varias consultas de manera eficiente.
Algunos problemas fundamentales de consulta geométrica son:
- Búsqueda de rango : preprocesar un conjunto de puntos para contar de manera eficiente la cantidad de puntos dentro de una región de consulta.
- Problema de ubicación de puntos : dada una partición del espacio en celdas, producir una estructura de datos que indique de manera eficiente en qué celda se encuentra un punto de consulta.
- Vecino más cercano : preprocesa un conjunto de puntos para encontrar de manera eficiente qué punto es el más cercano a un punto de consulta.
- Trazado de rayos : dado un conjunto de objetos en el espacio, produce una estructura de datos que indica de manera eficiente qué objeto 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 mediante:
- el tiempo y el espacio necesarios para construir la estructura de datos que se buscará en
- el tiempo (y a veces un espacio extra) para responder consultas.
Para el caso en el que se permite variar el espacio de búsqueda, consulte "Problemas dinámicos".
Problemas dinámicos
Otra clase importante son los problemas dinámicos , en los que 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 (adición o eliminación de elementos geométricos de entrada). Los algoritmos para problemas de este tipo generalmente involucran estructuras de datos dinámicas . Cualquiera de los problemas geométricos computacionales se puede convertir en uno dinámico, a costa 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 problema de envoltura convexa dinámica es realizar un seguimiento de la envoltura convexa, por ejemplo, para el conjunto de puntos que cambia dinámicamente, es decir, mientras se insertan o eliminan los puntos de entrada.
La complejidad computacional para esta clase de problemas se estima mediante:
- el tiempo y el espacio necesarios para construir la estructura de datos que se buscará en
- El tiempo y el espacio para modificar la estructura de datos buscada después de un cambio incremental en el espacio de búsqueda.
- el tiempo (y a veces un espacio extra) para responder una consulta.
Variaciones
Algunos problemas pueden considerarse pertenecientes a cualquiera de las categorías, según el contexto. Por ejemplo, considere el siguiente problema.
- Punto en el polígono : decide si un punto está dentro o fuera de un polígono determinado.
En muchas aplicaciones, este problema se trata como un problema de una sola vez, es decir, perteneciente a la primera clase. Por ejemplo, en muchas aplicaciones de gráficos por ordenador , 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 invariable, mientras que el punto representa una consulta. Por ejemplo, el polígono de entrada puede representar la frontera de un país y un punto es la posición de un avión, y el problema es determinar si el avión violó la frontera. Finalmente, en el ejemplo de gráficos por ordenador mencionado anteriormente, en las aplicaciones CAD los datos de entrada cambiantes a menudo se almacenan en estructuras de datos dinámicas, que pueden aprovecharse para acelerar las consultas de puntos en polígonos.
En algunos contextos de problemas de consulta, existen expectativas razonables sobre la secuencia de las consultas, que pueden aprovecharse para lograr estructuras de datos eficientes o para realizar estimaciones de complejidad computacional más precisas. Por ejemplo, en algunos casos es importante conocer el peor caso para el tiempo total de toda la secuencia de N consultas, en lugar de para una sola consulta. Véase también " análisis amortizado ".
Geometría computacional numérica
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 en este caso son las curvas paramétricas y las superficies paramétricas , como las curvas de Bézier , las curvas spline y las superficies. Un enfoque no paramétrico importante es el método de conjunto de niveles .
Las áreas de aplicación de la geometría computacional incluyen la construcción naval, la aeronáutica y la industria automotriz.
Lista de algoritmos
- Problema del par más cercano : encontrar el par de puntos (de un conjunto de puntos) con la menor distancia entre ellos
- Algoritmos de detección de colisiones : comprueban la colisión o intersección de dos sólidos dados
- Algoritmo de cono : identificar puntos de la superficie
- Algoritmos de envoltura convexa : determinación de la envoltura convexa de un conjunto de puntos
- Transformada de distancia euclidiana : calcula la distancia entre cada punto de una cuadrícula y una colección discreta de puntos.
- Hashing geométrico : un método para encontrar de manera eficiente objetos bidimensionales representados por puntos discretos que han sufrido una transformación afín
- Algoritmo de distancia de Gilbert–Johnson–Keerthi : determinación de la distancia más pequeña entre dos formas convexas .
- Algoritmo Jump-and-Walk : un algoritmo para la localización de puntos en triangulaciones
- Suavizado laplaciano : un algoritmo para suavizar una malla poligonal
- Intersección de segmentos de línea : determinar si las líneas se intersecan, generalmente con un algoritmo de línea de barrido
- Algoritmo de Bentley-Ottmann
- Algoritmo de Shamos-Hoey
- Algoritmos de cuadro delimitador mínimo : encuentre el cuadro delimitador mínimo orientado que encierra un conjunto de puntos
- Búsqueda de vecino más cercano : busque el punto o los puntos más cercanos a un punto de consulta
- Algoritmo de anidamiento : hacer el uso más eficiente del material o el espacio
- Algoritmos de puntos en polígonos : comprueban si un punto determinado se encuentra dentro de un polígono determinado
- Algoritmos de registro de conjuntos de puntos : encuentra la transformación entre dos conjuntos de puntos para alinearlos de forma óptima.
- Calibradores rotatorios : determinan todos los pares antípodas de puntos y vértices en un polígono convexo o una envoltura convexa .
- Algoritmo del cordón : determinar el área de un polígono cuyos vértices están descritos por pares ordenados en el plano
- Triangulación
- Triangulación de Delaunay
- Algoritmo de Ruppert (también conocido como refinamiento de Delaunay): crear triangulaciones de Delaunay de calidad
- Segundo algoritmo de Chew : crear triangulaciones de Delaunay con restricciones de calidad
- Triángulos en marcha : reconstrucción de la geometría de una superficie bidimensional a partir de una nube de puntos no estructurada
- Algoritmos de triangulación de polígonos : descomponen un polígono en un conjunto de triángulos
- Diagramas de Voronoi , dual geométrico de la triangulación de Delaunay
- Algoritmo de Bowyer-Watson : crea un diagrama de Voronoi en cualquier número de dimensiones
- Algoritmo de la fortuna : crear un diagrama de Voronoi
- Cuasitriangulación
- Triangulación de Delaunay
Véase también
- Lista de temas de geometría computacional combinatoria
- Lista de temas de geometría computacional numérica
- CAD / CAM / CAE
- Modelado de sólidos
- Topología computacional
- Representación informática de superficies
- Geometría digital
- Geometría discreta (geometría combinatoria)
- Partición del espacio
- Número tricomplejo
- Cálculo geométrico robusto
- Wikiversidad:Tema:Geometría computacional
- Wikiversidad:Diseño geométrico asistido por ordenador
Referencias
- ^ Franco P. Preparata y Michael Ian Shamos (1985). Geometría computacional: una introducción . Springer-Verlag . ISBN 0-387-96131-3. 1ª edición; 2ª impresión, corregida y ampliada, 1988.
- ^ AR Forrest, "Geometría computacional", Proc. Royal Society London , 321, serie 4, 187-195 (1971)
- ^ Yevgeny B. Karasik (2019). Geometría computacional óptica . ISBN 979-8511243344.
- ^ S. Khuller y Y. Matias. Un algoritmo de criba aleatorizado simple para el problema del par más cercano. Inf. Comput., 118(1):34—37,1995 ( PDF )
- ^ S. Fortune y JE Hopcroft. "Una nota sobre el algoritmo del vecino más próximo de Rabin". Information Processing Letters, 8(1), págs. 20-23, 1979
Lectura adicional
Revistas
Geometría computacional combinatoria/algorítmica
A continuación se muestra la lista de las principales revistas que han publicado investigaciones sobre algoritmos geométricos. Tenga en cuenta que, con la aparición de revistas dedicadas específicamente a la geometría computacional, la proporción de publicaciones geométricas en revistas de informática y gráficos computacionales de uso general disminuyó.
- Encuestas de informática de ACM
- Transacciones ACM en gráficos
- Acta Informática
- Avances en geometría
- Algoritmica
- Arte Combinatorio
- Geometría computacional: teoría y aplicaciones
- Comunicaciones de la ACM
- Diseño geométrico asistido por ordenador
- Gráficos y aplicaciones informáticas
- El mundo de los gráficos por ordenador
- Computación en geometría y topología
- Geometría discreta y computacional
- Geombinatorica
- Geometrias dedicadas
- Transacciones IEEE sobre gráficos
- Transacciones IEEE sobre computadoras
- Transacciones IEEE sobre análisis de patrones e inteligencia de máquinas
- Cartas de procesamiento de información
- Revista internacional de geometría computacional y aplicaciones
- Revista de teoría combinatoria , serie B
- Revista de geometría computacional
- Revista de geometría diferencial
- Revista de la ACM
- Revista de algoritmos
- Revista de Ciencias de la Computación y Sistemas
- Ciencia de la gestión
- Reconocimiento de patrones
- Letras de reconocimiento de patrones
- Revista SIAM sobre informática
- Noticias de SIGACT ; presentó la "Columna de geometría computacional" de Joseph O'Rourke
- Ciencias de la computación teóricas
- La computadora visual
Enlaces externos
- Geometría computacional
- Páginas de geometría computacional
- Geometría en acción
- "Direcciones estratégicas en geometría computacional: informe del grupo de trabajo" (1996)
- Revista de geometría computacional
- (Anual) Escuela de invierno sobre geometría computacional
- Laboratorio de Geometría Computacional
