La triangulación codiciosa es un método para calcular una triangulación poligonal o una triangulación de conjunto de puntos utilizando un esquema codicioso , que agrega bordes uno por uno a la solución en estricto orden creciente por longitud, con la condición de que un borde no pueda cortar un borde previamente insertado. [1] [2]
![]() Polígono Pasos de triangulación codiciosos. En cada paso se agrega un nuevo borde (rojo) que une el par de vértices más cercano, sin cruzar un borde anterior | |
Clase | Algoritmo de búsqueda |
---|---|
Estructura de datos | |
Rendimiento en el peor de los casos | |
Rendimiento en el mejor de los casos |
Referencias
- ^ J. Loera , J. Rambau y F. Santos (2010), Triangulaciones: Estructuras y algoritmos (segunda edición revisada), Springer-Verlag , ISBN 9783642129711 Capítulo 3: Triangulación de polígonos: pág.103.
- ^ Mark de Berg , Marc van Kreveld , Mark Overmars y Otfried Schwarzkopf (2000), Computational Geometry (segunda edición revisada), Springer-Verlag , ISBN 3-540-65620-0CS1 maint: varios nombres: lista de autores ( enlace )