Efficient VLSI parallel algorithm for Delaunay triangulation on orthogonal tree network in two and three dimensions
- 1 March 1990
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 39 (3) , 400-404
- https://doi.org/10.1109/12.48871
Abstract
An algorithm with worst case time complexity O(log2 N) in two dimensions and O(m1/2 log N) in three dimensions with N input points and m as the number of tetrahedra in triangulation is given. Its AT2 VLSI complexity on Thompson's logarithmic delay model, (1983) is O(N2log6 N) in two dimensions and O(m2N log4 N) in three dimensionsKeywords
This publication has 12 references indexed in Scilit:
- An O(log n) time parallel algorithm for triangulating a set of points in the planeInformation Processing Letters, 1987
- AnO(N logN) minimal spanning tree algorithm forN points in the planeBIT Numerical Mathematics, 1986
- Primitives for the manipulation of general subdivisions and the computation of VoronoiACM Transactions on Graphics, 1985
- Computational GeometryPublished by Springer Nature ,1985
- Geometric structures for three-dimensional shape representationACM Transactions on Graphics, 1984
- The VLSI Complexity of SortingIEEE Transactions on Computers, 1983
- Efficient VLSI Networks for Parallel Processing Based on Orthogonal TreesIEEE Transactions on Computers, 1983
- A Mesh-Connected Area-Time Optimal VLSI Multiplier of Large IntegersIEEE Transactions on Computers, 1983
- An O(n log n) heuristic for steiner minimal tree problems on the euclidean metricNetworks, 1981
- Automatic triangulation of arbitrary planar domains for the finite element methodInternational Journal for Numerical Methods in Engineering, 1974