This is an award winning page

Visualizing Geometric Algorithms - State of the Art

David Dobkin

Department of Computer Science
Princeton University
Princeton, NJ 08540


The visual nature of geometry makes it a natural area where visualization can be an effective tool in communicating ideas. This is enhanced by the observation that much of the action in computational geometry occurs in 2 and 3 dimensions, where visualization is highly plausible. Given these observations, it is not surprising that there has been noticeable progress during the past few years in the production of visualizations of geometric algorithms and concepts. There is every reason to believe that this will continue and even accelerate in the future. In this note, I briefly survey the current state of the art as well as suggesting new directions that should be pursued in the future. Further details appear in the survey article [HD96].

As anyone who has tried to implement a complex geometric algorithm knows, implementing geometric algorithms is a difficult task. Conventional tools are limited as aids in this process. The programmer spends time with pen and pencil drawing the geometry and data structures the program is developing. This problem could be solved by the use of visualization tools. In the ideal world, this visualization would be used for 3 purposes; demonstration, debugging and isolation of degeneracies. Ideally, we would like to use the same tools for all 3 functions. So, we would use the tool to help us debug the implementation of an algorithm by providing visual interaction during the debugging process. Next, we would like to use the same tool to create a visualization of the algorithm with which the user can interact. This interaction can be either passive or active. For example, a video tape provides passive interaction since the viewer's controls are limited to the VCR controls. Active interactions allow the viewer greater control over the visualization as we describe further below. Finally, there is the issue of isolating problems in code that is symbolically correct. Typically, such bugs come from degeneracies either in the data or in the computational model. Visualization has the potential to be a great help here as the tool allowing the user to jump into the code at (or preferably before) the point at which it breaks.

Of these 3 purposes, we have seen the most success in demonstration. After 5 years, the video proceedings of the computational geometry conference continue to thrive. Researchers in various computing environments are able to create videos of visualizations that are satisfying and useful adjuncts to understanding the algorithms or systems which they visualize. However, there is significant room for improvement. Many of the visualizations submitted to the review are prepared in ad hoc fashion. We are quite distant from having a set of tools that rivals LaTeX or even TeX in any form. Further, there is no agreement on the styles to be used to produce high quality visualizations. Computational geometry videos are different in nature from the recent high quality mathematical visualizations that have been produced at the Geometry Center (eg Not Knot [EG91] or Outside In [LM94]). Visualizations in computational geometry tend to make minimal use of high quality graphics preferring instead ``low budget'' visualizations. The objects being visualized support this decision. It makes little sense to use smooth rendering techniques to hide edges and vertices of a polyhedron when these are the defining components of the shape. Instead techniques are typically chosen which highlight these components. The videos that have been produced serve as excellent adjuncts to papers that have been or are about to be published. The challenge remains to develop tools that make the process easer. Ideally, we should expect that a paper describing a geometric algorithm will always be accompanied by an animation of the algorithm.

The problem of creating active interactions remains largely unsolved. It is still the case that a visualization demonstrates the behavior of an algorithm on one sample input and explains the behavior of the algorithm on that input. A better scenario would allow the to not only specify the input, but also to interact with the view (and possibly even the input data) as the algorithm is running. There are a few systems that exist that allow the user to interact with a running animation (e.g. [Tel], [TD95]).

However, the interactions come at a price. The viewer must typically have the hardware that was used to develop the interaction. This limits the ability to integrate such animations into hypermedia documents. There is hope that the emergence of Java and VRML will help remove this limitation.

The hope is that the existence of Java as a programming language and VRML as a file format will enable interactions to be easily transmitted over the World Wide Web. This is far from a solved problem. There remain various speed problems. Java does solve much of the bandwidth problem by doing a single download of the algorithm. However, there remains the speed of execution problem. The interpreted nature of Java may make interaction impossible for complex algorithms. Further, there is a need for toolkits on which Java applets can be built. Ideally, there would be a computational geometry set of classes that would achieve wide use in the community. These classes would make code sharing easier and would allow implementors of new algorithms to begin at a higher level. This hope also arises in the other uses of visualization.

Ideally, Java will not only enable interactions, but will also enable implementors to use their applet as it is being developed as an aid in debugging their implementation. The visual nature of geometry makes Java a natural tool for debugging. Rather than drawing by hand the emerging data structures and geometry, an applet that displays the situation would be a wonderful adjunct. Disregarding issues of speed, it is not difficult to create the plumbing necessary to allow a developing applet to run in tandem with a conventional debugger which provides control over the running process. This combination should prove useful to all implementors.

Beyond classes and tools that simplify implementation, implementors also need data sets to be used as inputs to algorithms. Various issues arise here. First there should be generators for simple data sets that can be used for demonstration. The simplest example is N random points or segments in the plane. Tools need to be created as in [Sch], [EKK...] to create and modify such sample inputs. These are absolutely necessary for simple debugging of implementations. Next, there need to be more subtle input sets (eg points in (or near degenerate situations). Finally, there need to be collections of data from real applications. It is unnecessary for each implementor to reinvent input sets. Indeed, we as a community must create a set of classes and sample inputs that are usable for a wide range of applications.

I have attempted to describe here the current state of visualization for geometric algorithms. To summarize, the field is doing well but there are exciting opportunities for the future. The video review has become well established within the field. It is now time to take a closer look at the possibilities of hypermedia. A first step in this direction is the construction of appropriate classes upon which Java applets can be built for animations. An accompanying task is the generation of good sets of test data on which algorithms can be implemented. The value of such work will lie both in easier communication of results within our community and in an increased ability to reach those outside of our community.


David Epstein, Charlie Gunn, et al, ``Not-Knot'', distributed by A K Peters, Wellesley MA, 1991.

P. Epstein, J. Kavanagh, A. Knight, J. May, T. Nguyen and J.-R. Sack, ``Workbench for Computational Geometry'' in Animation of Geometric Algorithms: A Video Review, edited by Brown and Hershberger, DEC SRC TR 87b, 1992.

A. Hausner and D. Dobkin, ``Making Geometry Visible: An introduction to the Animation of Geometric Algorithms'', in Handbook for Computational Geometry, edited by Sack and Urrutia, to appear.

Silvio Levy, Delle Maxwell and Tamara Munzner. ``Outside In'', distributed by A K Peters, Wellesley MA, 1994.

Peter Schorn, Adrian Brüngger and Michele De Lorenzi, ``The XYZ GeoBench: Animation of Geometric Algorithms'' in Animation of Geometric Algorithms: A Video Review, edited by Brown and Hershberger, DEC SRC TR 87b, 1992.

A.Y. Tal and D.P. Dobkin, ``Visualization of Geometric Algorithms'', IEEE Transactions on Visualization and Computer Graphics (TVCG) Volume 1, Number 2.

Seth Teller, ``Visualizing Fortune's Sweepline Algorithm for Planar Voronoi Diagrams'' in Symposium on Computational Geometry, 1993 Video Review, edited by Brown and Hershberger.

About this document ...

This document was first generated using the LaTeX2HTML translator Version 0.5.3 (Wed Jan 26 1994) Copyright © 1993, Nikos Drakos, Computer Based Learning Unit, University of Leeds.

The command line arguments were:
latex2html -split 0 Mine.tex.

The translation was initiated by dpd@cs.CS.Princeton.EDU on Thu May 9 06:16:53 EDT 1996

The results of this translation were then modified to produce the document here

Wed May 15 05:56:21 EDT 1996