Application-Motivated Themes for Computational Geometry

Michael T. Goodrich

Dept. of Computer Science

Johns Hopkins University

Computational Geometry involves the study of methods for solving computational problems involving collections of geometric objects, such as points, lines, planes, and triangles. Since these objects arise naturally in a number of domains, it is not unreasonable to expect computational geometry to have a potentially large impact on research in other areas as well as being a research discipline that should be of interest in its own right. Computational Geometry has already had some successes on research for application-motived problems, but we believe its impact can be increased over that which has occurred so far. For that to occur we believe future research in Computational Geometry should focus more heavily on one or more of the following themes:

  1. Realistic models. The standard model for most computational geometry algorithms is the Random Access Machine (RAM). This model does not take into account a number of important factors of modern computers, including the use of caches, limited main-memory size, disk input/output, and multiple CPU's. One way to achieve more a more application-motivated approach is to incorporate some of these aspects into the models of computation being used.

  2. Robust Algorithms. Some algorithms that have been designed for geometric problems assume that the data is given to infinite precision, that it is in general position, and that error-free computations can be performed on all geometric objects. These are not always realistic assumptions, so in cases in which these assumptions do not necessarily hold algorithms should be designed to be robust in spite of degeneracies caused by objects that are not in general position or potential round-off errors that might result from a primitive function of some geometric objects.

  3. Attention to Constant Factors. Asymptotic analysis has proven to be a very powerful tool in the design of efficient algorithms, but it is not without its pitfalls. In particular, its natural hiding of constant factors may tempt some algorithm designers to declare an algorithm ``efficient'' even if, due to large constant factors, its running time is inferior to existing methods for most reasonable input sizes. Application-motivated research involves closer attention to constant factors, possibly even characterizing them explicitly (in terms of primitive geometric functions, such as line intersections, point-line comparisons, etc.).

  4. Problem Selection. An important aspect of application-motivated research, of course, also involves the selection of problems that are abstracted from other research domains that use geometric computations. This fact is gaining wide acceptance in the computational geometry research community, and should continue to be a major corner stone of application-motivated geometric algorithm design.

  5. Experimental validation. The final aspect of application-motivated research that we would like to highlight is that it involves experimental validation. That is, algorithms that claim to be of practical value should be implemented and tested against methods previously assumed to be the best in practice. This, of course, should involve the design of a suite of typical problem instances, preferably taken from several different types of uniform and non-uniform input distributions. It should also involve the testing of the algorithm for a wide range of sizes of the input, with several independent runs taken for each size.

By incorporating one or more of the above qualities of application-motivated research in the design of geometric algorithms we believe that the impact of computational geometry will be significantly strengthened over its already substantial levels.

Michael Goodrich
Fri May 10 21:37:26 EDT 1996