Algoritmos en pocas palabras, 2ª edición

Capítulo 9. Geometría computacional

Este trabajo se ha traducido utilizando IA. Agradecemos tus opiniones y comentarios: [e-mail]

La geometría computacional es la aplicación rigurosa de las matemáticas para calcular estructuras geométricas y sus propiedades con precisión y eficacia. Limitamos nuestra discusión a la resolución de problemas que implican estructuras bidimensionales representadas en el plano cartesiano; existen extensiones naturales a estructuras n-dimensionales. Los matemáticos han investigado tales problemas durante siglos, pero el campo se ha reconocido como un estudio sistemático desde la década de 1970. Este capítulo presenta las abstracciones computacionales utilizadas para resolver problemas de geometría computacional. Estas técnicas no se limitan en absoluto a los problemas de geometría y tienen muchas aplicaciones en el mundo real.

Los algoritmos de esta categoría resuelven numerosos problemas del mundo real:

Casco convexo

Calcula la forma convexa más pequeña que encierra completamente un conjunto de n puntos bidimensionales, P. Esto puede resolverse en O(n log n) en lugar de una solución de fuerza bruta O(ⁿ⁴).

Segmentos de línea que se intersecan

Calcula todas las intersecciones dado un conjunto de n segmentos de línea bidimensionales, S. Esto puede resolverse en O((n + k) log n) donde k es el número de intersecciones, en lugar de una solución de fuerza bruta O(ⁿ²).

Diagrama de Voronoi

Divide un plano en regiones en función de ...