An optimal speed-up parallel algorithm for triangulating simplicial point sets in space |
| |
Authors: | Hossam ElGindy |
| |
Affiliation: | (1) Department of Computer and Information Science, Faculty of Engineering and Applied Science, University of Pennsylvania, 19104 Philadelphia, PA |
| |
Abstract: | Previous research on developing parallel triangulation algorithms concentrated on triangulating planar point sets.O(log3
n) running time algorithms usingO(n) processors have been developed in Refs. 1 and 2. Atallah and Goodrich(3) presented a data structure that can be viewed as a parallel analogue of the sequential plane-sweeping paradigm, which can be used to triangulate a planar point set inO(logn loglogn) time usingO(n) processors. Recently Merks(4) described an algorithm for triangulating point sets which runs inO(logn) time usingO(n) processors, and is thus optimal. In this paper we develop a parallel algorithm for triangulating simplicial point sets in arbitrary dimensions based on the idea of the sequential algorithm presented in Ref. 5. The algorithm runs inO(log2
n) time usingO(n/logn) processors. The algorithm hasO(n logn) as the product of the running time and the number of processors; i.e., an optimal speed-up. |
| |
Keywords: | Computational geometry parallel algorithms triangulation simplicial sets |
本文献已被 SpringerLink 等数据库收录! |
|