Efficient VLSI parallel algorithm for Delaunay triangulation on orthogonal tree network in two and three dimensions
Sanjeev Saxena, P.C.P. Bhatt, V.C. Prasad · IEEE Transactions on Computers · 1990
An algorithm with worst case time complexity O(log/sup 2/N) in two dimensions and O(m/sup 1/2/log N) in three dimensions with N input points and m as the number of tetrahedra in triangulation is given. Its AT/sup 2/ VLSI complexity on Thompson's logarithmic delay model, (1983) is O(N/sup 2/log/sup 6/N) in two dimensions and O(m/sup 2/Nlog/sup 4/ N) in three dimensions.>