Abstract
Delaunay triangulation has been much used in such applications as volume rendering, shape representation, terrain modeling and so on. The main disadvantage of Delaunay triangulation is large computation time required to obtain the triangulation on an input points set. This time can be reduced by using more than one processors, and several parallel algorithms for Delaunay triangulation have been proposed. In this paper, we propose an improved parallel algorithm for Delaunay triangulation, which partitions the bounding convex region of the input points set into a number of regions by using Delaunay edges and generates Delaunay triangles in each region by applying an incremental construction approach. Partitioning by Delaunay edges makes it possible to eliminate merging step required for integrating subresults. It is shown from the experiments that the proposed algorithm has good load balance and is more efficient than Cignoni et al.'s algorithm[8] and our previous algorithm[9].
| Original language | English (US) |
|---|---|
| Pages | 131-138 |
| Number of pages | 8 |
| State | Published - 1997 |
| Externally published | Yes |
| Event | Proceedings of the 1997 Conference on Advances in Parallel and Distributed Computing - Shanghai, China Duration: Mar 19 1997 → Mar 21 1997 |
Conference
| Conference | Proceedings of the 1997 Conference on Advances in Parallel and Distributed Computing |
|---|---|
| City | Shanghai, China |
| Period | 3/19/97 → 3/21/97 |
ASJC Scopus subject areas
- General Computer Science