Position Paper - Geometry

Making Geometric Algorithms Practical and Usable

Scot Drysdale

The case that Computational Geometry should be more applied and driven by applications is made very well by Chazelle in "Application Challenges to Computational Geometry." I agree with the conclusions given there, and will not elaborate on them further. However, for us to succeed in application areas we must do more than abstract interesting and relevant problems and find good asymptotic-time solutions. There are already many applications that could use geometric algorithms, but do not.

Sometimes this is because the person writing the code does not know about the appropriate algorithms. But often it is because the algorithms are too complex to implement easily and there are no easily accessible implementations available. In cases where there are multiple algorithms or implementations available it is often not clear which one should be chosen. To alleviate these problems, work needs to be done in the following areas:

Inventing simple, practical algorithms. Many geometric algorithms (e.g. for computing 2-D convex hulls, finding line segment intersections via a sweepline, segment trees, interval trees, etc.) are conceptually easy and can be implemented in reasonably straightforward ways. (Robustness may be a problem, but that is a another point.) Randomized algorithms, approximation algorithms, and algorithms that use bucketing to get good average-case run times are also often easy to implement. In practice such algorithms are much more useful than more complicated algorithms which guarantee better asymptotic worst-case run times but at the cost of large constant factors and very complex implementations. We need to value research into developing practical algorithms that work well in practice (even if they are sub-optimal) as much as research into developing impractical but asymptotically optimal algorithms. Of course, the ideal case is when there is a simple algorithm that is also optimal, but this may not be possible.
Robustness. Research must be done on how to make geometric algorithms more robust. I refer the reader to Steve Fortune's position paper for the reasons for and possible solutions to this problem.
Libraries of Implemented Algorithms. Some geometric algorithms are complicated to implement, but the implemented algorithm is fast and practical. Even relatively simple algorithms can be difficult to implement robustly. Ideally these algorithms would be implemented well once (or a few times), and then made available in easily-shared form (packages or code libraries).
The computational geometry community is taking steps in this direction. Nina Amenta, Seth Teller, and Ernst Mücke have begun such collections. The LEDA project incorporates a number of geometric algorithms, and more are being added. But to date there is no geometric equivalent to the packages for solving linear programs or even to the book Numerical Recipes. The geometric programs collected are usually implemented by researchers to test their algorithm, and may not be "industrial strength." They often use incompatible data structures. The collectors of these programs usually do this work as volunteers, and they do not have the resources to rigorously evaluate all contributions.
Ideally there would be at least one well-funded group with the charge to evaluate algorithms for the entire range of geometric problems, to implement the better ones correctly and robustly, and to make them available to researchers and programmers. How this group would be funded is a difficult but important question.
Experimental Evaluation of Algorithms. A prerequisite to deciding which algorithms to implement in geometric libraries is knowing which ones perform well in practice. The last couple of SCG conferences have encouraged papers that do experimental work, as has SODA. However, comparative studies of algorithms for solving given geometric problems are just beginning to appear. We need to encourage and reward such studies.
The algorithms should be implemented to share data structures and primitives whenever possible (so that the relative speeds of the algorithms and not the cleverness of the implementers is being tested). The programs need to be ported to a range of machines, because differences in architecture seem to greatly influence the relative speeds of algorithms.
A sub-area of experimental evaluation is choosing appropriate test data. We at least have some idea of what "random" point sets might be (uniform, normal, etc.), even if we do not know how realistically these distributions model the real world. But what is a "random" collection of non-intersecting line segments or rectangles or polygons? We have barely begun to consider such questions. Furthermore, how do these correspond to "real world" data?
Using "real world" data is not a panacea, either, because applications differ widely in what sort of data they use. What is needed is a collection of benchmark data drawn from a wide range of applications. I know of no such collections of benchmark data available, and creating such collections would be a valuable service to the community.