Geometría algorítmica

Geometría algorítmica es un libro de texto sobre geometría computacional . Fue escrito originalmente en francés por Jean-Daniel Boissonnat y Mariette Yvinec , y publicado como Géometrie algorithmique por Edusciences en 1995. Fue traducido al inglés por Hervé Brönnimann, con mejoras en algunas demostraciones y ejercicios adicionales, y publicado por Cambridge University Press en 1998. ^{[ 1 ] [ 2 ] [ 3 ]}

El libro abarca los fundamentos teóricos y el análisis de algoritmos en geometría computacional, sus detalles de implementación y sus aplicaciones. ^{[ 1 ]} Está dividido en cinco secciones, la primera de las cuales cubre material de base sobre el diseño y análisis de algoritmos y estructuras de datos , incluyendo la teoría de la complejidad computacional y técnicas para diseñar algoritmos aleatorios . Sus secciones subsiguientes constan de un capítulo sobre las matemáticas de un subtema en esta área, presentado con el nivel de detalle necesario para analizar los algoritmos, seguido de dos o tres capítulos sobre algoritmos para ese subtema. ^{[ 2 ]}

Los temas presentados en estas secciones y capítulos incluyen envolventes convexas y algoritmos de envolventes convexas , programación lineal aleatoria de baja dimensión , triangulación de conjuntos de puntos para datos bidimensionales y tridimensionales, arreglos de hiperplanos , de segmentos de línea y de triángulos, diagramas de Voronoi y triangulaciones de Delaunay . ^{[ 2 ] [ 3 ]}

El libro puede utilizarse como libro de texto de posgrado o como referencia para la investigación en geometría computacional. ^{[ 1 ]} El crítico Peter McMullen lo califica como "una valiosa adición a la biblioteca de cualquier persona interesada en la geometría algorítmica". ^{[ 2 ]}