Posted to compgeom-discuss by Kumar Ramaiyer (kumar@research.att.com) May 31, 1996:

I would like to continue the discussions on geometric software with my suggestions. My summary here also includes the suggestions made by various people at the workshop.

1. Our past success at group efforts:

As a community we have achieved great success in creating the "geom.bib". I think almost all the latex papers now use this bib. We have a good model in that as a group effort. The people who maintain that bib can provide us with details of the work involved.

Its success is mainly due to the fact that it is a tool for a widely accepted standard (latex) for writing papers. As a result many people are able to contribute to this effort.

For geometric software, before we discuss building library, experiments, evaluation, and rewards, we need to discuss the standard, starting from programming standard (does everyone like C++?).

2. About layered library:

We should build a library "dag" by carefully analyzing the dependency between nodes of library.

First we need:

These two libraries already enrich an object-oriented language to build many algorithms. They can be circulated to various institutions to have a good understanding (like bib-TeX), to fix the problems, and to eventually evolve a common standard.

We need this first before we even think of building complex programs and data structures. All of us must be familiar with the basic types and routines so that we all can contribute.

The "library-dag" can then be expanded by applications (convex hulls, proximity, arrangement, etc. - one for each chapter of Preparata and Shamos!) with careful analysis of dependency. This "dag" can be documented properly.

A task-force can be created to monitor the evolution of the standard.

3. About programs:

The contributed programs should only use the types and primitives from the library and should come with a "behavior sheet":
  1. Using exact arithmetic.
  2. Using perturbation schemes.
  3. Using floating point filters.
  4. What degeneracies it cannot handle?
  5. Breaking point in space consumption for a given configuration
    ....
We need to come up with a behavior sheet. This will also helps us in evaluation as it is not fair to compare "exact arithmetic" programs and "filter" programs.

4. Data collection:

Many of us have inputs which can crash different programs. The data also should come with a behavior sheet.
  1. General position
  2. Degeneracy (its type and appropriate documentation)
(NOTE: When I was implementing point location algorithm, I had problems in inputting a planar subdivision whose PSLG was 2-connected as it did not have an unique embedding. The software I was using had a totally different internal representation from my input. I needed to input the subdivision as a planar graph, but the embedding routines ignore the geometric coordinates and only use the topology. I understood this behavior only after weeks of debugging. We need data like these and also documentation which lists our experiences with degeneracies with the corresponding data.)

Thanks for listening.

--Kumar