Content deleted Content added
m Improve sections. |
Mention time complexity of the pollowing pseudocode. It was a point of confusion for readers and even lead to a stackoverflow question. |
||
Line 18:
==Pseudocode==
The following [[pseudocode]] describes a basic implementation of the Bowyer-Watson algorithm. It's time complexity is <math>O(n^2)</math>. Efficiency can be improved in a number of ways. For example, the triangle connectivity can be used to locate the triangles which contain the new point in their circumcircle, without having to check all of the triangles - by doing so we can decrease time complexity to <math>O(n \log n)</math>. Pre-computing the circumcircles can save time at the expense of additional memory usage. And if the points are uniformly distributed, sorting them along a space filling [[Hilbert curve]] prior to insertion can also speed point ___location.<ref>Liu, Yuanxin, and Jack Snoeyink. "A comparison of five implementations of 3D Delaunay tessellation." Combinatorial and Computational Geometry 52 (2005): 439-458.</ref>
function BowyerWatson (pointList)
// pointList is a set of coordinates defining the points to be triangulated
| |||