首页   按字顺浏览 期刊浏览 卷期浏览 TIME-OPTIMAL GEOMETRIC ALGORITHMS IN HYPERCUBIC NETWORKS
TIME-OPTIMAL GEOMETRIC ALGORITHMS IN HYPERCUBIC NETWORKS

 

作者: PASCAL BERTHOMÉ,   AFONSO FERREIRA,  

 

期刊: Parallel Algorithms and Applications  （Taylor Available online 1994）
卷期: Volume 4, issue 3-4  

页码: 169-181

 

ISSN:1063-7192

 

年代: 1994

 

DOI:10.1080/10637199408915462

 

出版商: Taylor & Francis Group

 

关键词: Parallel algorithms;hypercubic networks;computational geometry;time-processor tradeoff;C.1.2;F.1.2;E2.2

 

数据来源: Taylor

 

摘要:

We describe a new strategy to solve geometric problems that trades off time × processors in hypercubic networks. LetNbe the size of the input. Using a hypercube of sizeN1+1/κproposeO(κlog N)time solutions for the ECDF searching, closest points, and convex hull problems. Such a strategy, based on the sparse enumeration sort, is of practical interest, since it provides time-optimal parallel algorithms that arc simple and have small constants related to their running times.

 

点击下载:  PDF (251KB)



返 回