Presentamos un estudio experimental de estrategias para triangular polígonos en paralelo en máquinas de varios núcleos, incluido el cálculo paralelo de triangulaciones restringidas de Delaunay. Como de costumbre, llamamos oreja a tres vértices consecutivos de un polígono (plano) si el triángulo que se extiende por ellos está completamente dentro del polígono. Pruebas exhaustivas en miles de polígonos de muestra indican que alrededor del 50% de los vértices de la mayoría de los polígonos forman orejas. Este resultado experimental sugiere que los algoritmos de triangulación de polígonos basados en recortes de orejas podrían ser adecuados para la paralelización.
Discutimos tres enfoques diferentes para el recorte de orejas en paralelo, y presentamos un algoritmo de cambio de bordes paralelo para convertir una triangulación en una triangulación restringida de Delaunay. Todos los algoritmos se implementaron como parte del marco de trabajo FIST de Held. Informamos sobre nuestros hallazgos experimentales, que muestran que el método más prometedor logra un aumento de velocidad promedio de 2-3 en un procesador de cuatro núcleos. En cualquier caso, nuestro nuevo código de triangulación es más rápido que los códigos de triangulación secuencial Triangle (por Shewchuk) y FIST.