首页   按字顺浏览 期刊浏览 卷期浏览 AN OPTIMAL PARALLEL ALGORITHM FOR FINDING THE SMALLEST ENCLOSING TRIANGLE ON A MESH-CON...
AN OPTIMAL PARALLEL ALGORITHM FOR FINDING THE SMALLEST ENCLOSING TRIANGLE ON A MESH-CONNECTED COMPUTER*

 

作者: JUNG-JU CHOI,   CHANG-SUNG JEONG,   MYUNG-SOO KIM,  

 

期刊: Parallel Algorithms and Applications  （Taylor Available online 1993）
卷期: Volume 1, issue 2  

页码: 115-126

 

ISSN:1063-7192

 

年代: 1993

 

DOI:10.1080/10637199308915435

 

出版商: Taylor & Francis Group

 

关键词: Parallel algorithm;smallest enclosing triangle;mesh-connected computer

 

数据来源: Taylor

 

摘要:

In this paper, we consider the problem of finding the smallest triangle circumscribing a convex polygon withnedges. We show that this can be done inO( √n)time by efficient data partition schemes and proper set mapping and comparison operations using the so-called√n-decomposition technique. Since the nontrivial operation on mesh-connected computers requiresΩ(,√n), the time complexity is optimal within a constant time factor.

 

点击下载:  PDF (204KB)



返 回