Lista de temas de geometría computacional combinatoria

La lista de temas de geometría computacional combinatoria enumera los temas de geometría computacional que plantean problemas en términos de objetos geométricos como entidades discretas y, por lo tanto, los métodos para su solución son principalmente teorías y algoritmos de carácter combinatorio .

Consulte la Lista de temas de geometría computacional numérica para conocer otro tipo de geometría computacional que trata los objetos geométricos como entidades continuas y aplica métodos y algoritmos propios del análisis numérico .

• Operaciones booleanas en polígonos
• Envoltura convexa
• Disposición del hiperplano
• Descomposición de polígonos
  • Triangulación de polígonos
    • descomposición convexa mínima
    • Problema de cobertura convexa mínima ( NP-difícil )
    • descomposición rectangular mínima
  • Problemas de teselación
• Problemas de disección de formas
• Esqueleto recto
• Problema de la línea punzante
• Triangulación
  • Triangulación de Delaunay
  • Triangulación de conjuntos de puntos
  • Triangulación de polígonos
• Diagrama de Voronoi

• Cuadro delimitador mínimo ( Cuadro delimitador más pequeño , Cuadro delimitador más pequeño )
  • Caso 2D: Rectángulo delimitador más pequeño ( Rectángulo envolvente más pequeño )
  • Existen dos variantes comunes de este problema.
    • En muchos ámbitos de los gráficos por ordenador, el cuadro delimitador (a menudo abreviado como bbox) se entiende como el cuadro más pequeño delimitado por lados paralelos a los ejes de coordenadas que encierra los objetos en cuestión.
    • En otras aplicaciones, como el embalaje , el problema consiste en encontrar la caja más pequeña en la que quepa el objeto (o los objetos) ("embalado"). En este caso, la caja puede adoptar una orientación arbitraria con respecto a los objetos "embalados".
• Esfera delimitadora más pequeña (esfera envolvente más pequeña)
  • Caso 2D: Círculo delimitador más pequeño
• Rectángulo vacío más grande ( rectángulo vacío máximo )
• La esfera vacía más grande
  • Caso 2D: Círculo vacío máximo ( círculo vacío más grande )

• Detección de colisiones
• Intersección de segmentos de línea
• Ubicación del punto
  • Punto en un polígono
• Intersección de polígonos
• Búsqueda de rango
  • búsqueda de rango ortogonal
  • Búsqueda de rango simplex
• Ray casting (que no debe confundirse con el trazado de rayos en gráficos por computadora)
• Método de losas

• Problema del final feliz
• Problema del sándwich de jamón
• problemas de ensamblaje de formas
• problemas de coincidencia de formas
• El problema de medición de Klee
• Problemas sobre polígonos isotéticos y poliedros isotéticos
  • envoltura convexa ortogonal
• Planificación de rutas
  • Senderos entre obstáculos
  • Camino más corto en un polígono
• Contención de polígonos
• La computación geométrica robusta aborda dos problemas principales: la representación de precisión fija de los números reales en las computadoras y la posible degeneración geométrica (matemática) de los datos de entrada.