Problemas de proximidad

Los problemas de proximidad son una clase de problemas en geometría computacional que implican la estimación de distancias entre objetos geométricos.

Un subconjunto de estos problemas, expresados ​​únicamente en términos de puntos, a veces se denominan problemas de punto más cercano , ^{[ 1 ]} aunque el término "problema de punto más cercano" también se utiliza como sinónimo de búsqueda del vecino más cercano .

Un rasgo común para muchos de estos problemas es la posibilidad de establecer el límite inferior Θ ( n log n ) de su complejidad computacional mediante reducción a partir del problema de unicidad de elementos basándose en una observación de que si hay un algoritmo eficiente para calcular algún tipo de distancia mínima para un conjunto de objetos, es trivial comprobar si esta distancia es igual a 0.

Si bien estos problemas no plantean ningún desafío en cuanto a complejidad computacional, algunos de ellos son notables debido a su omnipresencia en las aplicaciones informáticas de la geometría.

• Distancia entre dos segmentos de línea . No puede expresarse mediante una sola fórmula, a diferencia, por ejemplo, de la distancia de un punto a una línea . Su cálculo requiere una enumeración cuidadosa de las posibles configuraciones, especialmente en 3D y dimensiones superiores. ^{[ 2 ]}
• Caja delimitadora , el hiperrectángulo mínimo alineado con los ejes que contiene todos los datos geométricos.

• Par de puntos más cercanos : Dados N puntos, encuentra dos con la menor distancia entre ellos.
• Consulta del punto más cercano / consulta del vecino más cercano : dados N puntos, encontrar uno con la menor distancia a un punto de consulta dado.
• Problema de todos los vecinos más cercanos (construcción del grafo de vecinos más cercanos ): Dados N puntos, encontrar el más cercano para cada uno de ellos.
• Diámetro (geometría computacional) : Dados N puntos, encontrar dos con la mayor distancia entre ellos.
• Ancho de un conjunto de puntos : Dados N puntos, encontrar dos (hiper)planos con la menor distancia entre ellos y con todos los puntos entre ellos.
• Árbol de expansión mínima para un conjunto de puntos
  • árbol de expansión mínima euclidiana
• Triangulación de Delaunay
• Diagrama de Voronoi
• Esfera mínima que los encierre : Dados N puntos, encuentra la esfera (círculo) más pequeña que los encierre a todos.
• Círculo vacío más grande : Dados N puntos en el plano, encontrar el círculo más grande centrado dentro de su envolvente convexa y que no encierre ninguno de ellos.
• Rectángulo de contención más pequeño : a diferencia del problema del cuadro delimitador mencionado anteriormente, el rectángulo puede tener cualquier orientación.
• Rectángulo vacío más grande
• Engranaje geométrico , un grafo ponderado sobre un conjunto de puntos como vértices que para cada par de vértices tiene un camino entre ellos con un peso como máximo 'k' veces la distancia espacial entre estos puntos para un 'k' fijo.

• El camino más corto entre obstáculos
• Distancia de aproximación más cercana

• Franco P. Preparata y Michael Ian Shamos (1985). Geometría computacional: una introducción . Springer-Verlag . ISBN 0-387-96131-31.ª edición: ISBN 0-387-96131-3; 2.ª edición, corregida y ampliada, 1988: ISBN 3-540-96131-3Traducción al ruso, 1989: ISBN 5-03-001041-6.Los problemas de proximidad se tratan en los capítulos 6 y 7.