Parallel triangulation of a polygon in two calls to the trapezoidal map |
| |
| Authors: | Chee -Keng Yap |
| |
| Affiliation: | (1) Courant Institute of Mathematical Sciences, New York University, 251 Mercer Street, 10012 New York, NY, USA |
| |
| Abstract: | 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 timeO(logn) usingO(n) CREW PRAM processors.This research was supported by NSF Grants No. DCR-84-01898 and No. DCR-84-01633, and ONR Contract N00014-85-K-0046. |
| |
| Keywords: | Parallel algorithm Triangulation Polygon |
| 本文献已被 SpringerLink 等数据库收录！ |
|
