vi presenterar en experimentell studie av strategier för triangulering av polygoner parallellt på flerkärniga maskiner, inklusive parallell beräkning av begränsade Delaunay trianguleringar. Som vanligt kallar vi tre på varandra följande hörn av en (plan) polygon ett öra om triangeln som spänns av dem är helt inuti polygonen. Omfattande tester på tusentals provpolygoner indikerar att cirka 50% av hörn av de flesta polygoner bildar öron. Detta experimentella resultat tyder på att polygon-trianguleringsalgoritmer baserade på öronklippning kan vara väl lämpade för parallellisering.
vi diskuterar tre olika tillvägagångssätt för parallelliserande öronklippning, och vi presenterar en parallell kantflippningsalgoritm för att omvandla en triangulering till en begränsad Delaunay-triangulering. Alla algoritmer implementerades som en del av helds FIST framework. Vi rapporterar om våra experimentella resultat, som visar att den mest lovande metoden uppnår en genomsnittlig hastighet på 2-3 på en fyrkärnig processor. I alla fall är vår nya trianguleringskod snabbare än den sekventiella trianguleringskoderna Triangle (av Shewchuk) och FIST.