Wir präsentieren eine experimentelle Studie über Strategien zur parallelen Triangulation von Polygonen auf Multi-Core-Maschinen, einschließlich der parallelen Berechnung von Constrained Delaunay Triangulationen. Wie üblich nennen wir drei aufeinanderfolgende Eckpunkte eines (ebenen) Polygons ein Ohr, wenn sich das von ihnen aufgespannte Dreieck vollständig innerhalb des Polygons befindet. Umfangreiche Tests an Tausenden von Beispielpolygonen zeigen, dass etwa 50% der Eckpunkte der meisten Polygone Ohren bilden. Dieses experimentelle Ergebnis legt nahe, dass Polygon-Triangulationsalgorithmen, die auf Ohrclipping basieren, für die Parallelisierung gut geeignet sein könnten.
Wir diskutieren drei verschiedene Ansätze zur Parallelisierung des Ohrclipping und stellen einen parallelen Edge-Flipping-Algorithmus zur Umwandlung einer Triangulation in eine eingeschränkte Delaunay-Triangulation vor. Alle Algorithmen wurden als Teil des FIST-Frameworks von Held implementiert. Wir berichten über unsere experimentellen Ergebnisse, die zeigen, dass die vielversprechendste Methode eine durchschnittliche Beschleunigung von 2-3 auf einem Quad-Core-Prozessor erreicht. In jedem Fall ist unser neuer Triangulationscode schneller als die sequentiellen Triangulationscodes Triangle (von Shewchuk) und FIST.