I agree with a lot of what Paul Heckbert's comments. However, our company is very much focussed on the Big Oh issue & I believe that it would be a grave mistake to ignore the importance of this issue.

Our company has been producing commercial mining software for the last fifteen years. The amount of data needed to be processed has exploded over recent times. For example, fly over surveys can easily produce millions of points. Clients using our software need fast algorithms to process this data. For them it is a matter of having an up to date model. A lot of this data is very expensive to obtain, so the software companies that can deal with it have an edge. To put things in perspective, ten years ago our clients were modelling surfaces of around 10,000 points. Today we have many clients wanting to model surfaces of 500,000 points. I do not see this trend changing.

One of the biggest challenges for us is to make the theoretical algorithms robust. One of the problems with many of the algorithms is that a slightly numerical wrong result can cause the entire algorithm to fail. For example, having four almost co-circular points in a 2D delaunay triangulation. In practice, it wouldn't matter a great deal if the delaunay property wasn't honoured exactly in this sort of situation. However, many of the algorithms will break completely in such a situation. A common approach is to add tolerances, but we have found that this approach just shifts the problem. In practice this limits the amount of data you can process (i.e. the probability of a "problem" situation occurring becomes higher with big data sets).

One of the challenges we face at the moment is to produce a robust constrained tetrahedral model of the data. A lot of research has been done of the 2D problem, but not a whole lot on the 3D problem (There has been some good work done). One of the major problems is visualising these data structures. Debugging algorithms would be much easier if you could visualise the results (e.g. see what the effects of a 3D delaunay flip is). A good set of visualisation tools may also provide the catalyst for new inspiration. It would also be an excellent teaching tool to demonstrate how some of the algorithms work (This may not be possible for four dimensional problems. For example, generating the convex hull in 4D).