Parallel triangulation of a polygon in two calls to the trapezoidal map
We give a parallel method for triangulating a simple polygon by two (parallel) calls to the trapezoidal map computation. The method is simpler and more elegant than previous methods. Along the way we obtain an interesting partition of one-sided monotone polygons. Using the best known trapezoidal map algorithm, ours run in time O(log n) using O(n) CREW PRAM processors.
scientific article; zbMATH DE number 4055043
scientific article