Constant time algorithms for computational geometry on the reconfigurable mesh

作     者：Jang, JW Nigam, M Prasanna, VK Sahni, S 

作者机构：SOGANG UNIVDEPT ELECT ENGNSEOUL 121742SOUTH KOREA UNIV FLORIDADEPT COMP SCI & INFORMAT ENGNGAINESVILLEFL 32611 UNIV SO CALIFDEPT EE SYSTLOS ANGELESCA 90089 

出 版 物：《IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS》 (IEEE Trans Parallel Distrib Syst)

年 卷 期：1997年第8卷第1期

页      面：1-12页

核心收录：

学科分类：0808[工学-电气工程] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：National Science Foundation, NSF, (IRI-9217528, MIP-9103379) Air Force Office of Scientific Research, AFOSR, (F-49260-89-C-0126, F-49620-90-C-0078) Defense Advanced Research Projects Agency, DARPA Korea Science and Engineering Foundation, KOSEF, (961-0909-052-1) 

主　　题：.Triangulation Parallel and Distributed neighbors Electronic Engineering Constant Time smallest Southern California enclosing Algorithms for Computational Reconfigurable Mesh planar points 

摘      要：The reconfigurable mesh consists of an array of processors interconnected by a reconfigurable bus system. The bus system can be used to dynamically obtain various interconnection patterns among the processors. Recently, this model has attracted a lot of attention. In this paper, we show O(1) time solutions to the following computational geometry problems on the reconfigurable mesh: all-pairs nearest neighbors, convex hull, triangulation, two-dimensional maxima, two-set dominance counting, and smallest enclosing box. All these solutions accept N planar points as input and employ an Nx N reconfigurable mesh. The basic scheme employed in our implementations is to recursively find an O(1) time solution. The number of recursion levels and the size of the subproblems at each level of recursion are optimized such that the problem decomposition and the solution to the problem can be obtained in constant time. As a result, we have developed some efficient merge techniques to combine the solutions for subproblems on the reconfigurable mesh. These techniques exploit reconfigurability in nontrivial ways leading to constant time solutions using optimal size of the mesh.