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 sólo en términos de puntos se denominan a veces problemas del punto más cercano , [1] aunque el término "problema del 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 ) en su complejidad computacional mediante la reducción del problema de unicidad del elemento basándose en la observación de que si existe un algoritmo eficiente para calcular algún tipo de distancia para un conjunto de objetos, es trivial comprobar si esta distancia es igual a 0.
Problemas atómicos
Si bien estos problemas no plantean ningún desafío de complejidad computacional, algunos de ellos son notables debido a su ubicuidad en las aplicaciones informáticas de la geometría.
- Distancia entre un par de segmentos de línea . No se puede expresar mediante una fórmula única, a diferencia de, por ejemplo, la distancia de un punto a una línea . Su cálculo requiere una cuidadosa enumeración de posibles configuraciones, especialmente en 3D y dimensiones superiores. [2]
- Cuadro delimitador, el hiperrectángulo alineado con el eje mínimo que contiene todos los datos geométricos
Problemas en los puntos
- Par de puntos más cercano : Dados N puntos, encuentre dos con la distancia más pequeña entre ellos
- Consulta de punto más cercano / consulta de vecino más cercano : Dados N puntos, encuentre uno con la distancia más pequeña a un punto de consulta dado
- Problema de todos los vecinos más cercanos (construcción del gráfico del vecino más cercano ): Dados N puntos, encuentre uno más cercano para cada uno de ellos
- Diámetro de un conjunto de puntos : Dados N puntos, encuentre dos con la mayor distancia entre ellos
- Ancho de un conjunto de puntos : Dados N puntos, busque dos (hiper) planos con la distancia más pequeña entre ellos y con todos los puntos entre ellos
- Árbol de expansión mínimo para un conjunto de puntos
- Triangulación de Delaunay
- Diagrama de Voronoi
- Esfera envolvente más pequeña : Dados N puntos, encuentre una esfera más pequeña (círculo) que los encierre a todos.
- Círculo vacío más grande : Dados N puntos en el plano, encuentre un círculo más grande centrado dentro de su casco convexo y que no encierre ninguno de ellos.
- Rectángulo envolvente 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
- Llave geométrica , un gráfico ponderado sobre un conjunto de puntos como sus vértices que para cada par de vértices tiene una ruta entre ellos de peso como máximo 'k' veces la distancia espacial entre estos puntos para una 'k' fija.
Otro
- Camino más corto entre obstáculos
- Distancia de aproximación más cercana
Referencias
- Franco P. Preparata y Michael Ian Shamos (1985). Geometría computacional: una introducción . Springer-Verlag . ISBN 0-387-96131-3. 1ra edición: ISBN 0-387-96131-3 ; Segunda impresión, corregida y ampliada, 1988: ISBN 3-540-96131-3 ; Traducción rusa, 1989: ISBN 5-03-001041-6 . Los problemas de proximidad se tratan en los capítulos 6 y 7.
- ^ JR Sack y J. Urrutia (eds.) (2000). Manual de geometría computacional . Holanda Septentrional . ISBN 0-444-82537-1.CS1 maint: texto adicional: lista de autores ( enlace )
- ^ VJ Lumelsky (1985). "En el cálculo rápido de la distancia entre segmentos de línea". Inf. Proceso. Letón. 21 (2): 55–61. doi : 10.1016 / 0020-0190 (85) 90032-8 .