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.
- Parallel algorithm
ASJC Scopus subject areas
- Computer Science(all)
- Computer Science Applications
- Applied Mathematics