One theme of Franklin's research is computational geometry algorithms useful for large datasets, mostly in 3D, and usually implemented. They include the following (dates are approximate).

  1. 2D edge intersection in expected time linear in the input plus output size (1978). This is a subproblem of most of the other algorithms. The algorithm is input-sensitive, but has been shown to be fast for a wide range of very uneven real data, including edges of a nonuniform grid, edge on a USGS Digital Line Graph, and edges of rectangles in an integrated circuit design.
    This algorithm's design, a uniform grid, illustrates a longterm theme of the research. Since most data's spatial density varies, the obvious optimization is to adapt the grid to the data's varying density. That is wrong, repeat wrong. First, it is ugly. Second, it is unnecessary, both theoretically and practically. Theoretically, if the data's density variation is limited, then the mean times still hold, i.e., linear in the size of the input plus output. Second, this behavior has been observed in practice.
    Why is there not even a log factor in the time? Sorting an objects into a grid cell takes constant time. That is a more powerful operation than the binary decision that is the basis of many time analyses, such as sorting, that produce a log factor.
  2. Red-blue edge intersection: Given a set of red edges and a set of blue edges, determine only the intersections of a red and a blue edge, in expected time linear in the size of the input plus the size of the output. Note that there may be a quadratic number of red-red and blue-blue intersections, but only a linear number of red-blue intersections, the time should be linear. This was implemented as part of the planar graph overlay.
    Red-blue edge intersection illustrates the strength of these input-sensitive techniques. SFAIK, the best worst-case algorithm requires time linear in the number of red-red intersections.
  3. Object space hidden surface algorithm, to determine the visible parts of faces in 3D, in expected linear time, regardless of the depth complexity of the scene. Implemented in 1980 for spheres of varying sizes. Largest test case: 10,000.
  4. Planar graph (map) overlay: areas of all the nonempty intersections of the faces of two overlaid planar graphs. Implemented in about 1990. Algorithm extended to 3D and published.
  5. Point location in a planar graph in expected constant time per query. That was implemented as a subproblem of the planar graph overlay.
  6. Connected Components on a 3D regular grid of bits, assuming either 6- or 26-connectivity. Largest test case: 1000x1000x1000. This is a specialization of union-find for this particular geometry.
  7. Volume and surface area of the union of many polyhedra. Implemented for isothetic identical cubes. Expected linear execution time for i.i.d. cubes. This is not a sampling method; the answers are exact. Largest test case: 20,000,000 cubes.
    One key to this algorithm is a set of formula devised by Franklin for computing mass properties of a polyhedron from only its set of vertices, including their positions and local neighborhoods, such as the direction vectors of adjacent edges. There is no explicit global topological info, such as which pairs of vertices are adjacent. This is important when the polyhedron is a boolean combination of other polyhedra. Determining local information of the resulting polyhedron is much easier than determining global ingo.
  8. Parallel determination of mass properties of boolean combinations of polyhedra.
  9. Nearest point determination in 3D. Preprocess a fixed set of points so as to perform queries against it. Implemented. Largest test case: > 100,000,000.
  10. Surface area of the union of overlapping spheres. Since the area seems not to have a closed form, this uses quadrature. It is implemented and mostly working.

Geometric Operations on Millions of Objects is a good summary talk from 2004.

A big reason for testing algorithms on large examples is that it's fun. However, it's possible that people aren't generally running large examples now since most current implementations are much too slow, when they don't crash. Large examples are an excellent stress test of the whole system. Also, these techniques scale down; when large examples take minutes, small examples run too fast to measure.

Franklin still gets occasional questions about PNPOLY, a subroutine he wrote in 1970 to test whether a polygon contains a point. Translated to C, PNPOLY has only eight lines of executable code. He has also showed why raster graphics is ultimately more difficult than vector graphics, altho the opposite appears to be true at first glance.

He has graduated 61 masters students, and 11 PhD students, six of whom are now on the faculties of other universities. Some of those students' theses were in other topics than listed above, such as logic programming, debugging expert systems, and software engineering.


<< | Research Page List | >>