Analog parallel algorithms for computational geometry
This paper presents a new approach to Parallel Computational Geometry by using networks of analog components (referred to as analog networks or analog 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 present analog parallel 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 e so that two given point sets are e-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.
|Keywords||Analog computing, Computational geometry, Hopfield nets, Neural nets, Parallel algorithms|
|Journal||Parallel Algorithms and Applications|
Dehne, F, Sack, J.-R, Valiveti, N. (Natana), & Flach, B. (Boris). (1995). Analog parallel algorithms for computational geometry. Parallel Algorithms and Applications, 5(1-2), 1–14. doi:10.1080/10637199508915472