An efficient VLSI architecture with applications to geometric problems

DOI10.1016/0167-8191(89)90007-0MaRDI QIDQ1124264zbMATH OpenOpenAlexFDO

Authors H. M. Alnuweiri, V. K. Prasanna Kumar

Publication date 1989

Published in Parallel Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0167-8191(89)90007-0

zbMATH Keywords

convex hullintersectionmultiprocessorparallel algorithmsplane computational geometryprocessor-time optimal solutionsVLSI architecture

Mathematics Subject Classification ID

Descriptive geometry (51N05) Algorithms for approximation of functions (65D15) Parallel numerical computation (65Y05) Theory of operating systems (68N25)

Review text

The authors show that a multiprocessor with n processors and \(n^ 2\) memory elements (element \(m_{ij}\) accessible by processors {\#}i,j) can execute the basic operations of plane computational geometry (convex hull, intersection, etc.) for \(n^ 2\) points in \(O(n \log n)\) time. \{For numbers of points that are not square the count is not so advantageous and the switching and access time to the memory elements can be considerable.\}

Recommendations

• VLSI systems for some problems of computational geometry
• scientific article; zbMATH DE number 3938571
• Parallel geometric algorithms on a mesh-connected computer
• Parallel computational geometry
• Efficient parallel convex hull algorithms

Cited in

(4)

• VLSI systems for some problems of computational geometry
• scientific article; zbMATH DE number 3938571 (Why is no real title available?)
• Digital Circuit Optimization via Geometric Programming
• VLSI circuit performance optimization by geometric programming

This page was built for publication: An efficient VLSI architecture with applications to geometric problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1124264)