These are listed from new to old. The dates are approximately when the idea was worked out. The ref and code links point to complete citations in the publications section of my resume. The paper and talk links point to a table containing links to the complete paper or talk slides, which is on my Papers and Talks page.
Conversion of Elevation Contours to a Grid. Mike Gousie and I have new techniques for this classic problem, which reduce the terracing effect and produce a smoother result. Ref. Paper and talk. (1997)
Lossy and lossless compression of gridded terrain elevation data. Wavelet-based compression algorithms intended for gray-scale images perform excellently on elevation data. Ref. Paper. (1996)
Several new algorithms and implementations relating to terrain visibility, and defending low-level avenues of approach in air defense. These involve fast approximations to the Line of Sight (LOS) problem, where we wish to compute the visibility index of every point in a Digital Elevation Model (DEM) array describing some terrain. The object is to find a set of site which, together, can cover the whole area of interest. This work has produced some counterintuitive results. For example, for some terrain, there is no significant correlation between elevation and visibility index; on the average, higher is no better for observation. Paper and contract report. (1992)
An algorithm for combining two different triangulations of the same 3D faceted object, to determine which pairs of tetrahedra overlap, and the intersection volumes. This is useful for interpolating data from one triangulation of an object to another. Ref. Paper. (1992)
A parallel algorithm and implementation for determining mass properties of Constructive Solid Geometry objects. Ref. (1991)
A logic programming approach to map overlay, implemented in Prolog. This was mostly a test of using Prolog in geometry. Ref. (1990)
An investigation into why raster graphics algorithms can be surprisingly counterintuitive and difficult. For example, consider finding the raster line segment between two points, such as with the Bresenham algorithm. Now, pick two points on the interior of that line and draw the new line segment between them. Probably the points of the new line segment will not be a subset of the points of the original line segment. This does not happen with ideal, vector, lines.
The deep reason that raster graphics can be harder than vector graphics is that, in algebra, the integers are harder than the reals, not easier. E.g., first order logic over the reals with addition and multiplication is solvable. Not so over the integers. Ref. (1985)
A better method for creating octrees by a bottom-up approach instead of using top-down subdivision. The idea is to intersect 1-D rays with the object, split the part of each ray that is inside the object into bintrees, group adjacent bintrees into quadtrees, then group adjacent quadtrees into octrees. This whole process has a systolic computation flavor. The advantage of this method is that it iss easier to intersect the object with a line than with a cube. Ref, ref, ref. (1985)
A map overlay algorithm for Geographic Information Systems, which can find the areas of the output regions without finding the regions themselves. The determination of the areas of all the output overlay polygons has been implemented. This is useful in interpolating data from one map to another. Ref. Code. Paper. (1983)
A new data structure for representing polygons and polyhedra by the location and purely local topology of each vertex. This contrasts with the complete topologies used in many CAD systems. My local data structure simplifies many operations, such as determination of the mass properties of boolean combinations of objects. Talk. (1983)
A linear expected-time object-space hidden surface algorithm and implemented, useful in CAD. This relies on the useful property that, if the input faces are IID (independently and identically distributed), then the expected number of visible edge pieces is linear in the number of input edges, and I can find them all in expected linear time.
This is remarkable since the total number of intersections of the projected input edges might be superlinear if the edges' lengths do not shrink fast enough. However, in that case, most of those intersections are hidden, and I can delete them in groups w/o spending even constant time per one. (1978)
A linear expected-time (in the output size) parallelizable algorithm and implementation, for finding all the intersections among a large set of small edge segments. This is a common operation in many of the following problems. (1977) Ref, ref, ref.
The uniform grid technique, which is used in many of the following applications. This idea is intended to be just sophisticated enough to solve the problem, without being so complicated that it is difficult to implement, including the messy special cases, and parallelize.
The concept, which is useful for culling pairs of objects that may intersect, is to overlay a uniform grid on the data. Then iterate over the elements, finding which grid cells each passes thru. Finally, iterate over the cells, comparing pairs of elements that pass thru the same cell. Implementing this properly requires some attention to detail. This method works well even when the data is unevenly distributed, where one's first impulse would be to use the, more complicated, quadtree. Ref, ref, ref, ref, ref. (1977)
An algorithm and implementation for displaying 3D prism maps showing data depending on geographic regions by raising a prism above each region. The program preprocessed the 2D map in advance so that new data could be displayed, with hidden surfaces removed, quickly. Ref. (1975)
Triangulated Irregular Network (TIN) for terrain elevation implementation. I probably did the first implementation of a TIN in GIS, under the direction of Tom Poiker and David Douglas. Ref, ref. (1973).
Many of these implementations are so efficient that the computation time is less than the I/O time.
All the implementations are tested on the largest datasets available. For example, the map overlay area program was tested, in 1989, on a map of US counties overlaid on a hydrography map. These contained over 5,000 polygons and 130,000 vertices in total. Finding edge intersections was tested on a database with 2,000,000 edges.