首页   按字顺浏览 期刊浏览 卷期浏览 An optimal parallel algorithm for finding shortest paths inside simple polygons
An optimal parallel algorithm for finding shortest paths inside simple polygons

 

作者: Wei Chen,   Koji Nakano,   Toshimitsu Masuzawa,   Yoshihiro Tsujino,   Nobuki Tokura,  

 

期刊: Systems and Computers in Japan  （WILEY Available online 1993）
卷期: Volume 24, issue 1  

页码: 1-15

 

ISSN:0882-1666

 

年代: 1993

 

DOI:10.1002/scj.4690240101

 

出版商: Wiley Subscription Services, Inc., A Wiley Company

 

关键词: Computational geometry;parallel algorithms;optimal speed‐up;convex hull problems

 

数据来源: WILEY

 

摘要:

AbstractGiven a triangulation of a simplen‐gonPand two pointsaandbinsideP, a parallel algorithm is presented for determining the path betweenaandbwith the shortest Euclidean distance insideP.The algorithm has time complexityO(logn) on CREW PRAM withn/lognprocessors and thus is optimal in the sense that the time‐processor product agrees with Ω(n)—the lower bound of time complexity of the sequential algo

 

点击下载:  PDF (1178KB)



返 回