I have a terrain presented by large set of points in 3D-space. What is the best way to triangulate it?
I can just to project all points on 2D-space, than make Delaunay triangulation in time O(n * log(n)) and lift it back to the previous heigth. But is it good enough? I've heard about Delaunay triangulation in time O(n * log(log(n))) in some special cases. Is it possible in my case? Or maybe I should to use some approximation algorithm?
Projection and Delaunay triangulation in 2D is certainly a good solution which will generate well shaped triangles. For a terrain you might also need to enforce certain edges, so look for a constrained Delaunay triangulation.
As to the runtime: For real world data you can assume linear runtime. If performance is important, make sure your input data is not degenerate: Scanning devices often return points on a grid. You can improve the situation by adding some noise.
