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:
- 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.
- 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.
- 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.).
- 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.
- 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