ACM/NSF Strategic Directions in Computing Research

Joseph O'Rourke

Rather than proselytize for the significance of my own research area, visibility, I would like to use this forum to emphasize the need for the Computational Geometry community to make its results available and accessible to the wider user community.

First I will list a variety of current activities aimed at exactly this broadening: our successes. Second I will propose several further steps I believe we should take to extend the effort.

Current Activities

  1. Bibliography. The community maintains an electronic bibliography of over 7,000 references in Computational Geometry. Bill Jones orchestrates the quarterly updates provided by the community, and upgrades the search software. It has developed into a unique and useful resource.
  2. Usenet newsgroups. Five prominent researchers in Computational Geometry participate actively in the Usenet newsgroup (Ken Clarkson, David Eppstein, Jeff Erickson, Seth Teller, and me; in fact I am the current FAQ maintainer). Our participation serves a dual purpose: we show the graphics community that Computational Geometry can answer some of their questions; and they provide us with applications and a feel for what is important to them.
  3. Textbooks. For many years, there was only one textbook, aimed at graduate students in Computer Science. The landscape is now changing, making the field accessible to undergraduates and to workers in various applied areas. A new text by Mark Overmars et al. focusing on applications is expected soon.
  4. Handbooks. There are two handbooks "in press": North Holland (Ed. Jorg Sack and Jorge Urrutia) and CRC Press (Ed. J.E. Goodman and me). These compendiums of current research will become resources for researchers in other fields.
  5. Research Monographs. More top researchers are pausing to write monographs. A notable example is the recently published book by Sharir and Agarwal on Davenport-Schinzel Sequences and their Geometric Applications.
  6. Columns Both Herbert Edelsbrunner and I write regular "Comptuational Geometry Columns" for professional newsletters (EATACS and SIGACT respectively). These inform researchers in other areas of Computer Science of the latest results in Computational Geometry. Herve Bronnimann produces a Computational Geometry Newsletter.
  7. Software Nina Amenta compiled a collection of pointers to Computational Geometry software into a Geometry Center Web page.


  1. Institutionalize the important resources. I am concerned that some of the most important efforts listed above are voluntary, dependent upon one individual. It would be safest if the projects were supported by the community in a more formal way. Nina Amenta has left the Geometry Center; will anyone replace her as the maintainer of the software directory? If Bill Jones tires of the bibliography project, will it continue?
  2. Software Testbeds. There is currently no easy way to compare algorithms. It would be very useful to have collections of standard test data that algorithm designers could run their code on and compare performance with other code run on the same input.
  3. Popularizations. Computer Science has few popularizers. Compare the situation with Mathematics or Physics. Brian Hayes's "Computing Science" column in the American Scientist is a notable exception.
  4. Algorithms Compendiums. Computational Geometry would benefit greatly from the equivalent of Numerical Recipes in C or the Graphics Gems series.
  5. NSF Grant Pages. NSF grants should require investigators to produce a Web page for each grant, from which the papers and software and other results of the grant are accessible.