Vi presentiamo uno studio sperimentale di strategie per la triangolazione di poligoni in parallelo multi-core macchine, tra cui il calcolo parallelo vincolata triangolazioni di Delaunay. Come al solito, chiamiamo tre vertici consecutivi di un poligono (planare) un orecchio se il triangolo che è attraversato da loro è completamente all’interno del poligono. Test approfonditi su migliaia di poligoni campione indicano che circa il 50% dei vertici della maggior parte dei poligoni formano orecchie. Questo risultato sperimentale suggerisce che gli algoritmi di triangolazione poligonale basati sul ritaglio dell’orecchio potrebbero essere adatti per la parallelizzazione.
Discutiamo tre diversi approcci alla parallelizzazione del ritaglio dell’orecchio e presentiamo un algoritmo di capovolgimento del bordo parallelo per convertire una triangolazione in una triangolazione di Delaunay vincolata. Tutti gli algoritmi sono stati implementati come parte del framework FIST di Held. Riportiamo i nostri risultati sperimentali, che mostrano che il metodo più promettente raggiunge una velocità media di 2-3 su un processore quad-core. In ogni caso, il nostro nuovo codice di triangolazione è più veloce dei codici di triangolazione sequenziale Triangle (di Shewchuk) e FIST.