首页   按字顺浏览 期刊浏览 卷期浏览 ANALOG PARALLEL ALGORITHMS FOR COMPUTATIONAL GEOMETRY
ANALOG PARALLEL ALGORITHMS FOR COMPUTATIONAL GEOMETRY

 

作者: FRANK DEHNE,   JÖRG-RÜDIGER SACK,   NATANA VALIVETI,   BORIS FLACH,  

 

期刊: Parallel Algorithms and Applications  (Taylor Available online 1995)
卷期: Volume 5, issue 1-2  

页码: 1-14

 

ISSN:1063-7192

 

年代: 1995

 

DOI:10.1080/10637199508915472

 

出版商: Taylor & Francis Group

 

关键词: Analog computing;computational geometry;Hopfield nets;neural nets;parallel algorithms

 

数据来源: Taylor

 

摘要:

This paper presents a new approach toParallel Computational Geometryby using networks ofanalogcomponents (referred to asanalog networksoranalog circuits). Massively parallel analog circuits with large numbers of processing elements exist in hardware and have proven to be efficient architectures for important problems (e.g. constructing an associative memory). In this paper it is demonstrated how Parallel Computational Geometry problems can be solved by exploiting the features of such analog parallel architectures. Using massively parallel analog circuits requires a radically different approach to geometric problem solving because (1) time is continuous instead of the standard discretized stepwise parallel processing, and (2) geometric data is represented by analog components (e.g. voltages at certain positions of the circuit) instead of the usual digital representation We presentanalogparallel algorithms for the following geometrical problems: minimum weight triangularization of planar point sets or of polygons with holes, minimum rectangular partitions of rectilinear polygons with holes, finding the smallest ϵ so that two given point sets are ϵ-congruent via translation, and determining for a given line segment set a subset of non-intersecting line segments of maximum total length. The paper also includes experimental results which demonstrate that, in practice, our analog parallel circuits produce high quality outputs.

 

点击下载:  PDF (277KB)



返 回