My Response to Application Challenges to Computational Geometry

Please excuse any mis-statements of current theory since I'm primarily applied, previously in Computer Graphics, currently mostly in GIS.

Computational Geometry and Other Fields

1. The statement in 'Terrain analysis' about TINs starting in 1978 is incorrect. In 1973, while working for the summer at Simon Fraser University, for David Douglas, who was acting for Tom Peucker (now Poiker), I designed and implemented a PL/1 program that is possibly the first implementation of a TIN. I still have the source code, which is available here. It even compares three different rules for diagonal swapping.

2. Geographic Information Systems, the field of Computer Graphics also developed long before Computational Geometry. Visibility determination algorithms, then called hidden surface algorithms, date from the 1960s, and were implemented in commercial flight simulators by around 1970. A canonical ref is this:

      @Article{sutherland-1974-characterization,
         author = "I. E. Sutherland and R. F. Sproull and R. A. Shumacker",
         title = "A characterization of ten hidden surface algorithms",
         journal = "ACM Comput. Surv.",
         volume = "6",
         year = "1974",
         pages = "1--55",
         oldlabel = "geom-590",
      }
   

   In addition, techniques such as horizon lines date back about as far, e.g.:

      @Article{wright-1973-two-space,
         author = "Thomas J. Wright",
         title = "A Two-Space Solution to the Hidden Line Problem for 
   	     Plotting Functions of Two Variables" ,
         year = "1973",
         month = "January",
         journal = "IEEE Trans. Computers",
         keywords = "height field",
      }
   

3. Of course, the above algorithms were not theoretically deep, DS sequences hadn't been invented, and an adversary could make those programs perform slowly. Nevertheless, they worked fast on the usual data, at a time when no theoretical algorithms existed.

4. What can really annoy applications people is that the theoreticians sometimes discover one of these fields, which may have had widely-used both public and commercial implementations for 20 years, based on algorithms published in society journals.

   They then start publishing papers, as if they'd invented the area, asymptotically analyzing complicated, unimplementable, worst-case algorithms w/o ever acknowledging that the earlier work even exists. One such paper introduced its literature search approximately as follows, previous papers in this field, meaning previous, theoretical, papers in only Computational Geometry.

   Although some of these old algorithms are only approximate, but so are some of the new papers that ignore them.

   A variant of this is the opinion that even implementation papers at good conferences should not mention implementation details, such as the computer system and SW used. Contrast this with experimental physics, where the experimental setup is considered quite relevant.

A Role for Theory

1. Of course, there's an excellent reason for asymptotic results. Before them, there was too much research of the form, My program in Fortran on an XDS is 3% faster than your PL/1 version on a 360; you're obsolete! We need general results.

   In addition, applications conferences often have papers not far from, How I designed and implemented a GIS to count bicycle traffic in Nfld w/o ever having to read a GIS or CG book. Those papers have nothing to teach anyone who doesn't want to use that specific system.

   Nevertheless, things have now gone too far the other way.

2. In other areas of CS, optimal algorithms are often quite simple. An example is hashing algorithms, where location = key mod tablesize is quite good (if tablesize has no small factors). Another example is virtual memory page-replacement strategies, where least recently used (LRU) works well. Another example is bin packing by the obvious strategy: first fit decreasing.

3. Therefore, theoreticians should also investigate simple algorithms and data structures in Computational Geometry applications in graphics and GIS. Simple algorithms have the advantage that you don't spend all your time getting the program syntactically legal, let alone executing correctly.

   They are also implementable, which is saying something, and take a reasonable time on reasonable problems, regardless of their asymptotic complexity.

   Also, after getting the algorithm implemented correctly, there is time to play with the program to understand its behavior and improve it. Simple algorithms also often parallelize more easily and better. Finally simple algorithms also tend to work very fast on large datasets since their constant factors in their times are often small.

   A worthwhile question is this: Why do some simple data structures work so well in practice? What does in practice mean? It's unfairly optimistic to assume the data to be uniform and uncorrelated, but unfairly pessimistic to make no assumptions at all.

4. Simple algorithms with limitations can also sometimes do quite well in places where no theoretical, worst-case, algorithm exists. Consider the red-blue edge segment intersection problem w/o preprocessing of the edges, when there are O(N^2) red-red and blue-blue intersections, which you don't know and don't want, and O(1) red-blue intersections, which you do want.

   So far as I know, there is no good theoretical, asymptotic algorithm. Nevertheless, a bucketing, uniform grid approach may find them all in O(size_in+size_out) time, w/o finding any red-red or blue-blue intersections, if the input is not too badly distributed.

5. Nevertheless, simple algorithms can still cause deep theoretical questions. They include expected performance (over what probability measure?), limitations, and how to work around those limitations. Is much known about expected performance of discrete data structures? Even Knuth once incorrectly analyzed the average depth of a 3 node binary search tree under uniform, random, insertion and deletion.

6. We have to control the caste system, exemplified by the joke at one meeting a few years ago that first, people try to do pure theory. If there are no jobs there, they try computational geometry. Finally, only if necessary to avoid starving do they teach applications. However, this isn't a joke. This leads to bad Computational Geometry, and to worse applications.

7. For a model of how things might operate better, consider physics and astronomy. The theoretical physicists predict some phenomema, such as the gravitational redshift, which the experimentalists then look for. However, in addition, the experimentalists observe anomalous phenomema, such as, in the 19th century, the precession of Mercury's orbit, which the theoreticians then try to explain.

   Not every anomaly leads to interesting theory; there were several other 19th century orbital oddities, which had classical explanations and therefore are forgotten today. Nevertheless, every so often general relativity results.

   As another example, trying to explain the photoelectric effect motivated quantum mechanics (and got Einstein his Nobel).

   One place where knowledge of theory could have helped was Edison's observation of the Edison effect, which is that the flow of electrons can be controlled in a vacuum tube. Edison, knowing little theory, didn't realize that he was seeing something significant, and ignored it. Later, Lee de Forest used this effect to invent the triode, the first electrical amplifier.

   Might theoreticians in Computational Geometry likewise both help applications by studying simpler algorithms, and help themselves to discover deep new theory by studying real applications?