Nous présentons une étude expérimentale de stratégies de triangulation de polygones en parallèle sur des machines multicœurs, y compris le calcul parallèle de triangulations de Delaunay contraintes. Comme d’habitude, nous appelons trois sommets consécutifs d’un polygone (planaire) une oreille si le triangle qu’ils couvrent est complètement à l’intérieur du polygone. Des tests approfondis sur des milliers de polygones d’échantillons indiquent qu’environ 50% des sommets de la plupart des polygones forment des oreilles. Ce résultat expérimental suggère que les algorithmes de triangulation de polygones basés sur l’écrêtage des oreilles pourraient être bien adaptés à la parallélisation.
Nous discutons de trois approches différentes de la parallélisation de l’écrêtage des oreilles, et nous présentons un algorithme de retournement de bord parallèle pour convertir une triangulation en une triangulation de Delaunay contrainte. Tous les algorithmes ont été implémentés dans le cadre du cadre FIST de Held. Nous rendons compte de nos résultats expérimentaux, qui montrent que la méthode la plus prometteuse atteint une accélération moyenne de 2-3 sur un processeur quad-core. Dans tous les cas, notre nouveau code de triangulation est plus rapide que les codes de triangulation séquentielle Triangle (de Shewchuk) et FIST.