Comments on the report
"Application Challenges to Computational Geometry"
by the Computational Geometry Impact Task Force (http://www.cs.princeton.edu/~chazelle/taskforce/CGreport.ps.Z)

General Comments on the State of Computational Geometry

I believe that computational geometers too often get caught up in pointless "big Oh races". There is much, much more to the design and analysis of algorithms than asymptotic worst case analysis. Anyone who wants their algorithms to be implemented and used should keep in mind that the "n" in problem sizes is typically bounded and often quite small! Bounded because it is typically limited by current memory size on the computer, and often quite small because of the statistics of the input. Instead of spending one's time reducing log* to inverse Ackermann, wouldn't it do more good for mankind to optimize the solution to a common problem by an actual factor of 10 or 100? Constants matter! Certainly, pure theory has its place, but I believe that computational geometry has to balance theory and practice. Currently the field is out of balance, leaning too far toward theory.

As a concrete example of the difference between the theoretical mindset and the practical mindset, consider the problem of point inclusion testing within an n-sided polygon. If you asked most computational geometers (or computational geometry books) about point inclusion testing, they might say:

"it's O(log n) for concave polygons if you triangulate as a preprocess and then use Kirkpatrick's algorithm"

"for small n, test against the line equation of each edge",
"for large n, use a grid data structure, and you'll typically get O(1)"

Haines points out that typically n=3 or 4 when ray tracing surface models. Haines' paper is certainly not the last word in practical point inclusion testing, but it does provide basic, important information that cannot be found in most computational geometry texts. (Randolph Franklin has also explored practical algorithms for this problem.) Shouldn't practical algorithms for basic geometric operations be within the scope of computational geometry? Or do computational geometers prefer to let computer graphics and geographic information systems programmers claim that "territory"?

As another example, Voronoi diagrams can be computed on discrete grids, yielding an O(1) discrete nearest neighbor algorithm [Danielsson, Comp. Graph. & Image Proc., 14, 1980, 227-248]. Sometimes a discrete Voronoi is good enough. This algorithm is used in low level software for color image quantization to 8 bit pixels on some personal computers. One typically does not hear about such algorithms in computational geometry.

I propose that computational geometry research should not focus on minimization of asymptotic worst case complexity and the computation of "optimal" solutions as its primary goals, but should broaden its scope to include additional goals, among them:

• min. asymptotic expected case complexity, for realistic inputs
• min. expected cost for typical problem sizes
• min. expected memory cost
• fast computation of approximate solutions
• reasonably efficient, easily implementable algorithms
• working implementations shared on the internet

• What is the best data structure to optimize intersection testing with surfaces in ray tracing? (regular grid, octree, k-d tree, BSP tree?)

• What is the best data structure to optimize visibility culling (of off-screen or occluded objects) in a z-buffer algorithm [see Greene-Kass-Miller, SIGGRAPH 93].

• Answer the two questions above in a dynamic scene.

• What is an analyzable, yet realistic parameterized statistical model for scene geometry? (The fractal dimension of scenes varies.)

• How do you deal with very complex scenes larger than what can fit in primary memory? (i.e. how do you use disks?) Multiresolution modeling is a promising approach.

• How do you simplify a surface model to a given size or a given geometric approximation error? [Heckbert-Garland, Graphics Interface 94].

• Promising early work in scanline (sweepline) and object space (continuous) rendering algorithms has largely been overtaken, in practice, by more brute force image space (discrete sampling) algorithms such as z-buffer and ray tracing, mostly because the latter are more easily put in hardware or generalized. How can computational geometry recast some of its algorithms to take advantage of the large existing base of z-buffer and ray tracing hardware and software?

• What are the lessons for computational geometry here, regarding simple vs. complex algorithms?

• How do you morph one polygon into another? One polyhedron into another? (choosing a "good" correspondence is the hard part)

• The desired element shape depends on the problem being solved (e.g. structural analysis FEM, fluid flow FEM, or surface modeling for display). Computational geometers need to understand the varied geometric needs of different applications.

• Anisotropic meshes are particularly important for viscous flow [Simpson, Applied Numer. Math., 14(1-3), 1994].

• Maximizing the minimum angle, minimizing the maximum angle, and Delaunay triangulation are not always the answer (even though they are theoretically "pretty").

• No mesh can be fully judged without its basis functions. The basis functions often place constraints on acceptable meshes. Computational geometers working in this area need to learn more about FEM methods.

• Many FEM practitioners know what meshes work for their particular problem (e.g. one person does only structural analysis of bridges, another generates studies aerodynamics of wings), but much of the work is art, not science. There are few researchers attempting to formalize the entire field of mesh generation, and few researchers doing theoretical error analysis of FEM solutions as a function of mesh geometry [Zienkiewicz-Zhu, Intl. J. Numer. Meth. Eng., 32, 783-810, 1991]. There is great potential for innovation here.

• Output from some CAD systems is near-garbage (e.g. poorly designed file formats, buggy software), making mesh generation of these models very difficult. [Ernst Mücke, ANSYS, personal communication] Perhaps more computational geometers should be involved in file format standardization efforts.

• A survey of the practical side of mesh generation is [Thompson & Weatherill, Aspects of Numerical Grid Generation: Current Science and Art, 11th AIAA Applied Aerodynamics Conf., Aug. 1993, pp. 1029-1070]

Software

Correction to References

Michael Garland and Paul S. Heckbert, Fast Polygonal Approximation of Terrains and Height Fields, CS Dept., Carnegie Mellon U., Sept. 1995, CMU-CS-95-181, http://www.cs.cmu.edu/~garland/scape

Paul S. Heckbert and Michael Garland, Survey of Polygonal Surface Simplification Algorithms, CS Dept., Carnegie Mellon U., to appear,