Geometry has been my overriding interest since high
school in the 1960s. Geometry is the "branch of mathematics
that deals with the measurement, properties, and
relationships of points, lines, angles, surfaces, and
solids" (Merriam-Webster dictionary). The *Geo* in geometry
is from the Greek Γη meaning, ''earth, ground,
land'' (The American Heritage® Book of English Usage).

My big long-term unsolved problem is to devise a **mathematics of terrain**, which would respect its physical properties. To date, I've been nibbling around the edges.

One current funded project (Cutler, Zimmie, Franklin. NSF CMMI-0835762: CDI-Type I: Fundamental Terrain Representations and Operations) attempts to predict how erosion occurs in levee failure by overtopping, and, after a failure, to reverse-simulate what happened.

A earlier major project was *Geo**, funded by DARPA,
studied representing and operating on terrain, that is, elevation.

I've applied the same underlying principles in Computational Geometry producing algorithms useful for large datasets, mostly in 3D, and usually implemented.

Both topics are applications of my long term theme of
emphasizing small, simple, and fast data structures and
algorithms. Note that efficiency in both space and time can
become *more* important as machines get faster. This
research is applicable to computational cartography,
computer graphics, computational geometry, and geographic
information science.

16 PhD students (7 currently employed at a college), and
68 masters students have been graduated under my
advisement,
*(names and theses)*.

My research has been externally funded by the National Science Foundation under Grants ENG-7908139, ECS-8021504, ECS-8351942, CCF-9102553, CCF-0306502, DMS-0327634, CMMI-0835762 and IIS-1117277 by DARPA/DSO, via the NGA, under the GeoStar program, by the US Army Topographic Engineering Center, and by IBM, Sun Microsystems, and Schlumberger-Doll Research.

Many of the algorithms have been implemented. The code is available for nonprofit research and education.

There are two main groups in my research: **Computational Cartography** and **Computational Geometry**. The rest of this page describes various subtopics.

**Contents** (hide)

- 1. Computational cartography research
- 1.1 Alternate Terrain Reps
- 1.2 Parallel and distributed cartography computation
- 1.3 Hydrography, bathymetry
- 1.4 Erosion modeling
- 1.5 GeoStar
- 1.6 Visibility, Multi-observer siting, Path planning
- 1.7 Gridding contours
- 1.8 Overlaying two maps (aka Planar graphs)
- 1.9 Logic programming for map overlay
- 1.10 Triangulated irregular network
- 1.11 Prism
- 1.12 General cartography

- 2. Computational geometry research
- 2.1 Fundamentals
- 2.2 Local data structures for polyhedra
- 2.3 Parallel and distributed geometry algorithms
- 2.4 Connected components in $E^3$
- 2.5 Linear time object space hidden surfaces
- 2.6 Nearest points in E
^{2}and E^{3} - 2.7 All near point pairs in E
^{3} - 2.8 Overlaying 3D triangulations
- 2.9 UNION2, UNION3, and Boolean operations and their mass properties
- 2.10 Perimeter and area of the union of circles
- 2.11 Octree creation
- 2.12 Edge intersection
- 2.13 Misc papers

- 3. Other research topics
- 4. Open topics
- 5. Old program solicitations
- 6. Short notes
- 7. Advice
- 8. Proposal writers cheat sheet
- 9. Workshop organizers cheat sheet
- 10. Software notes and reviews

# 1. Computational cartography research

This, my major theme, includes terrain representation and operations thereon, applied to large datasets.

Terrain: This is the elevation of the earth's surface above the geoid.

Representation: What data structures should be used?
Leading existing representations include **Triangulated**
**Irregular Networks (TINs)** and **matrices** of
elevations. I am studying other methods such as
**scooping** and **Overdetermined Laplacian PDEs**.
Part of the representation problem is how to compress the
data, either losslessly or lossily, which maintaining some
metric, such as RMS elevation or slope error or visibility.

The hard part of representation is devising more powerful,
though less tractable, nonlinear encoding techniques to
compat with the nonlinear physics of terrain formation. This
research is cognizant of the peculiar properties of terrain,
such as its low degree of continuity, its long-range
correlations (drainage basins), and its vertical asymmetry
(there are many local maxima, but few local minima).
Important *operations* include lossy compression, drainage
computation, observer siting, and mobility determination.

Operations: What do we want to do with the terrain?
Typical operations include **multiobserver siting** and
**path planning**.

More info on Alternate Terrain Reps

## 1.1 Alternate Terrain Reps

This theme has the following goals:

- Study alternate terrain representations that are more compact.
- Since the new representations will therefore be lossy, evaluate the size / quality tradeoffs.
- These new representations ought to make it easier to represent legal terrain than illegal terrain.
- We wish to process datasets up to 50000x50000 elevation posts.
- With these new representations, uncompression speed is more important than compression speed.
- The new representations are to be evaluated on metrics such as visibility and mobility.

This is my most promising long-term theme. Unfortunately, shortterm pressures have prevented its getting the time it deserves.

Publications include the following. (Publications relevant to more than one topic are listed under each topic.)

- bibtexsummary:[/wrf.bib,stuetzle-sdh-2012]
- bibtexsummary:[/wrf.bib,stuetzle-autocarto-2012]
- bibtexsummary:[/wrf.bib,li-autocarto-2010]
- bibtexsummary:[/wrf.bib,terrain-fwcg-2010]
- bibtexsummary:[/wrf.bib,xie-acmgis-2010]
- bibtexsummary:[/wrf.bib,wrf-ica99-web]
- bibtexsummary:[/wrf.bib,andrade-prog-trans-2008]
- bibtexsummary:[/wrf.bib,wrf-sdh-2008]
- bibtexsummary:[/wrf.bib,zx-wrf-spie-2007]
- bibtexsummary:[/wrf.bib,xie-fwcg-2007]
- bibtexsummary:[/wrf.bib,wrf-mi-spie-2006]
- bibtexsummary:[/wrf.bib,inanc-fwcg-2006]
- bibtexsummary:[/wrf.bib,wrf-autocarto-2006]
- bibtexsummary:[/wrf.bib,wrf-cagis-00]
- bibtexsummary:[/wrf.bib,wrfelev95]
- bibtexsummary:[/wrf.bib,wrf-icip]
- bibtexsummary:[/wrf.bib,wrflossy]

## 1.2 Parallel and distributed cartography computation

Publications include:

- bibtexsummary:[/wrf.bib,giscience-hdodetlap-2012]
- bibtexsummary:[/wrf.bib,stookey-acmgis-2008]
- bibtexsummary:[/wrf.bib,f-moaap-92]
- bibtexsummary:[/wrf.bib,stookey-acmgis-2008]

See also the parallel geometry papers below.

## 1.3 Hydrography, bathymetry

Publications include:

- bibtexsummary:[/wrf.bib,salles-agile-2012]
- bibtexsummary:[/wrf.bib,lau-autocarto-2012]
- bibtexsummary:[/wrf.bib,lau-sdh-2012]
- bibtexsummary:[/wrf.bib,lau-fwcg-2011]
- bibtexsummary:[/wrf.bib,stuetzle-acmgis-2011]
- bibtexsummary:[/wrf.bib,lau-cagis-2011]
- bibtexsummary:[/wrf.bib,lau-autocarto-2010]
- bibtexsummary:[/wrf.bib,lau-fwcg-2010]
- bibtexsummary:[/wrf.bib,li-acmgis-2010]
- bibtexsummary:[/wrf.bib,ica-2010]
- bibtexsummary:[/wrf.bib,lau-acmgis-2009]
- bibtexsummary:[/wrf.bib,stookey-acmgis-2008]
- bibtexsummary:[/wrf.bib,muckell-fwcg-2007]

## 1.4 Erosion modeling

Publications include:

More info on GeoStar

## 1.5 GeoStar

This major theme was a 2005-2009 DARPA-funded project for representing and operating on terrain, that is, elevation.

A good summary is this Geo* talk *(7/2010)*, Videos in talk:
1,
2,
3.

Its accomplishments included:

- efficient hi–res visibility computation on terrain,
- multiple observer siting to maximize joint viewshed,
- ODETLAP, an extension of the Laplacian PDE to an overdetermined system of equations, which is used in many of the following results,
- extremely compact lossy terrain (elevation) compression,
- terrain compression that reconstructs slopes accurately,
- lossily compressed terrain supports motion-planning (path planning),
- path planning with sophisticated cost metric on large terrain, and
- a better surface fitting procedure for bathymetry data that is very unevenly spaced.

Publications on Geo* as a project include:

In addition many other publications listed on this page present various aspects of Geo*.

More info on Siting

## 1.6 Visibility, Multi-observer siting, Path planning

The idea is to start with some terrain, i.e, elevation data, and then to place (site) a set of observers to oversee the terrain as well as possible. Previous work by other researchers has tended to compute the viewsheds of individual observers. Our work starts by computing higher resolution viewsheds than often computed elsewhere, and then extends the siting concept by choosing quasi-optimal sets of observers.

Even for single observer viewsheds, some counterintuitive results have been obtained. For example, for some terrain, there is no significant correlation between elevation and visibility index; on the average, higher is no better for observation. Publications include:

- bibtexsummary:[/wrf.bib,magalhaes-ijcisim-2011]
- bibtexsummary:[/wrf.bib,magalhaes-his-2010]
- bibtexsummary:[/wrf.bib,andrade-geoinfo-ext-viewshed-2008]
- bibtexsummary:[/wrf.bib,tracy-acmgis-2008]
- bibtexsummary:[/wrf.bib,wrf-fwcg-2008]
- bibtexsummary:[/wrf.bib,tracy-fwcg-2008]
- bibtexsummary:[/wrf.bib,dt-wrf-spie-2007]
- bibtexsummary:[/wrf.bib,acmgis07]
- bibtexsummary:[/wrf.bib,wrf-sdh2006]
- bibtexsummary:[/wrf.bib,wrf-cv-siting-isprs]
- bibtexsummary:[/wrf.bib,wrf-siting-apr2004]
- bibtexsummary:[/wrf.bib,wrf-site]
- bibtexsummary:[/wrf.bib,fr-hinbv-94]
- bibtexsummary:[/wrf.bib,wrf-savannah]

More info on Gridding Contours

## 1.7 Gridding contours

Mike Gousie and I have new techniques for the classic problem of converting elevation contours to a grid, and generally fitting a surface to data. Our innovations reduce the terracing effect seen in many other methods, and produce a smoother, more realistic, result. One technique is based on ODETLAP (described separately). Publications include:

- bibtexsummary:[/wrf.bib,Gousie05]
- bibtexsummary:[/wrf.bib,gousie98]
- bibtexsummary:[/wrf.bib,acmgis2003]
- Contours to digital elevation models: grid-based surface
reconstruction methods, MB Gousie,
*and* - Development of a two-level iterative computational method for solution of the Franklin approximation algorithm for the interpolation of large contour line, J Childs.

More info on Overlaying Two Maps

## 1.8 Overlaying two maps (aka Planar graphs)

An algorithm for calculating the areas of overlaid polygons without calculating the overlay itself, is presented. OVERPROP is useful when the sole purpose of overlaying two maps is to find some mass property of the resulting polygons, or for an areal interpolation of data from one map to the other. Finding the areas of all the output polygons is both simpler and more robust than finding the polygons themselves. OVERPROP works from a reduced representation of each map as a set of `half-edges'; with no global topology. It uses the uniform grid to find edge intersections. The method is not statistical, but is exact within the arithmetic precision of the machine. It is well suited to a parallel machine, and could be extended to overlaying more than two maps simultaneously, and to determining other properties of the output polygons, such as perimeter or center of mass. OVERPROP has been implemented as a C program, and is very fast.

One useful subtask is to locate all the points of each map in a specific polygon of the other. Its expected execution time is constant per query point regardless of the other map's complexity.

Publications include:

- bibtexsummary:[/wrf.bib,fs-ocamo-90-in-geom]
- bibtexsummary:[/wrf.bib,fk-vo3tp-93]
- bibtexsummary:[/wrf.bib,f-moaap-92]
- bibtexsummary:[/wrf.bib,fsskn-ofmop-93]
- bibtexsummary:[/wrf.bib,f-cmopa-90]
- bibtexsummary:[/wrf.bib,fsmoa-83]

The current version of Overprop uses the Exact Predicates kernel of CGAL. That avoids problems caused by roundoff error, but runs 100x more slowly. However, badly formed input maps still cause erroneous output. The unsolved question is, whether these might be handled automatically.

Overprop is an example of applying topology in cartography.

More info on Logic Programming Map Overlay

## 1.9 Logic programming for map overlay

In the late 1980s, we investigated using declarative, rather than procedural, programming techniques for map overlay. Titles include:

More info on Triangulated Irregular Network

## 1.10 Triangulated irregular network

This program takes an array of terrain elevations, and iteratively approximates it with a Triangulated Irregular Network, aka a piecewise linear triangular spline. I implemented the first TIN in cartography or geography, back in 1973; my PL/1 code is online. My current program has the following advantages compared to its competitors.

- Since it operates incrementally, by repeatedly inserting the worst point
into the TIN, after the
*K*-th stage, it has identified, in some sense, the*K*most important points. That is useful for, e.g., progressive transmission. - By virtue of a compact data structure, it does not require external storage even for rather large datasets. On a 32-bit PC, even many years ago, arrays of up to 10800x10800 posts could be processed; much larger datasets would be feasible today. Therefore it also does not require that the points first be externally sorted. >><<

More info on Prism

## 1.11 Prism

This is a 1970s 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. Publications include:

More info on General Cartography

## 1.12 General cartography

Here are broader papers and talks covering more than one topic, or reviewing the field, or that don't fit into one of the other categories. Titles of papers and talks include:

# 2. Computational geometry research

Efficient geometric operations on large datasets, or efficient spatial algorithms and data structures, is another research theme.

Here are the slides of a good summary talk: ''Geometric Operations on Millions of Objects'', presented at Koc University, Istanbul, 16 July, Sabanci University, Istanbul, 20 July, Bilkent University, 26 July, and Middle Eastern Technical University, 27 July 2004.

More info on Fundamentals

## 2.1 Fundamentals

Here are pages on

- PNPOLY, an 8-line program for determining point inclusion in a polygon. Written in 1970 it is both shorter and more robust than many later competitors.
- The
*uniform grid*data structure, for efficiently culling likely intersections in E^{2}and E^{3}. Although this appears to be too simple to work, implementations (supported by analysis) show that it does work quite well, even on unevenly distributed data. It is also simple enough to implemente and test, and also parallelizes well. - Why raster graphics is
*harder*than vector graphics. It's because integers are harder than rationals.

Publications include:

- bibtexsummary:[/wrf.bib,grid-2010]
- bibtexsummary:[/wrf.bib,afkn-gcugd-89]
- bibtexsummary:[/wrf.bib,fnkszw-ugtid-89]
- bibtexsummary:[/wrf.bib,fcksa-eugid-88]
- bibtexsummary:[/wrf.bib,f-aggo-84]
- bibtexsummary:[/wrf.bib,f-aggo-83]
- bibtexsummary:[/wrf.bib,f-prga-85]
- bibtexsummary:[/wrf.bib,f-cesua-84]
- bibtexsummary:[/wrf.bib,f-ero-83]

More info on Local Topology

## 2.2 Local data structures for polyhedra

These representations use little or no global topology. 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. That simplifies many operations, such as determination of the mass properties of boolean combinations of objects. There are fewer special cases, and parallel processing is facilitated.

Publications include:

## 2.3 Parallel and distributed geometry algorithms

- bibtexsummary:[/wrf.bib,kf-apcus-92]
- bibtexsummary:[/wrf.bib,fk-vo3tp-93]
- bibtexsummary:[/wrf.bib,nf-bcpp-92]
- bibtexsummary:[/wrf.bib,nf-eihc-92]
- bibtexsummary:[/wrf.bib,nf-dmppci-91]
- bibtexsummary:[/wrf.bib,fk-poshs-90-in-geom]
- bibtexsummary:[/wrf.bib,fck-pagc-siam-89]
- bibtexsummary:[/wrf.bib,fnkszw-ugtid-89]
- bibtexsummary:[/wrf.bib,fcksa-eugid-88]

More info on Connected Components

## 2.4 Connected components in {$E^3$}

This is an efficient implementation on a laptop computer of the union-find algorithm for finding connected components when the input is a 1000x1000×1000 3D box of binary voxels. Each voxel may be connected either to its 6 orthogonal neighbors, or to all 26 neighbors. Component properties, such as area, and volume are also computed. This implementation is fast enough to permit experimental studies of random connectivity. Publications include:

More info on Linear Object Space Hidden Surfaces

## 2.5 Linear time object space hidden surfaces

This is an object space algorithm from the late 1970s for
determining the visible parts of objects such as polyhedra and
spheres in E^{3} that operates in expected time linear in the
number of objects, independent of their depth complexity. We
have implemented it for spheres and cubes. Around 1980, it could
handle 10,000 random spheres stacked 10 deep. (Some other
algorithm's times are quadratic in the depth.) Publications include:

More info on Nearpt3

## 2.6 Nearest points in E^{2} and E^{3}

This is a pair of subroutines to find nearest points in
E^{3}. **Preprocess** takes a list of fixed points, and
preprocesses them into a data structure. **Query** takes a
query point, and returns the closest fixed point to it.
**Nearpt2** is a special case for E^{2}.

**Nearpt3** is very fast, very small, and can process very
nonhomogeneous data. The largest example run on a laptop
computer was St Matthew from the Stanford Digital Michelangelo
Project Archive, with 184,088,599 fixed points.

Preprocessing the David data set, with 28,158,109 fixed points,
into a 723^{3} grid took 0.6 microseconds per fixed point. Each
query required 6 microseconds. The platform was an IBM T43p
laptop computer with a 2GHz Intel Pentium M processor and 2GB of
memory. Publications include:

More info on All Near Pairs

## 2.7 All near point pairs in E^{3}

This is a program to report all pairs of points nearer than a given
distance, from a fixed set of points in E^{3}.

Sample time: Processing 20K points to report 688K pairs took 20msec CPU time, excluding I/O on a 2.8GHz machine.

More info on Overlaying 3D Triangulations

## 2.8 Overlaying 3D triangulations

This 1992 algorithm combines 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. Publications include:

- bibtexsummary:[/wrf.bib,fk-vo3tp-93]

More info on Union

## 2.9 UNION2, UNION3, and Boolean operations and their mass properties

This theme computes mass properties of boolean operations on large sets of polyhedra, typically in linear time. Besides algorithms, it includes demo implementations such as computing the volume and area of the union of up to 20,000,000 cubes. That took one hour on a dual xeon workstation.

My technique is to combine several other themes.
The first is to optimizes the composition of *volume* and *union*
operators; finding the volume of the union of two polyhedra does not
require finding their explicit union with global topology etc. That also
uses my local topological formulae. Finally, the linear execution time is
effected with a uniform grid.

Publications include:

- bibtexsummary:[/wrf.bib,nf-dmppci-91]
- bibtexsummary:[/wrf.bib,wrf-union-analysis-2004]
- bibtexsummary:[/wrf.bib,wrf-dimacs2005]
- bibtexsummary:[/wrf.bib,kf-apcus-92]
- bibtexsummary:[/wrf.bib,nf-bcpp-92]
- bibtexsummary:[/wrf.bib,nf-eihc-92]
- bibtexsummary:[/wrf.bib,fckaw-egoc-90]
- bibtexsummary:[/wrf.bib,fck-pagc-siam-89]
- bibtexsummary:[/wrf.bib,f-eiclb-89]
- bibtexsummary:[/wrf.bib,fkn-epgol-89]
- bibtexsummary:[/wrf.bib,f-epiu-82]

More info on Unite Circles

## 2.10 Perimeter and area of the union of circles

This is a variation of the above theme: to find mass properties of the union of many circles. For i.i.d. circles, the expected time is linear in the number of circles, regardless of the number of intersections. The algorithm is not statistical, but is exact up to the machine's numerical precision.

A test implementation taking cubic time is included, for circles of identical radii.

More info on Octrees

## 2.11 Octree creation

Forming an octree from the bottom up by combining individual voxels has several advantages over top-down construction. Publications include:

## 2.12 Edge intersection

- 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. - 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.

## 2.13 Misc papers

- bibtexsummary:[/wrf.bib,akman-dublin]
- bibtexsummary:[/wrf.bib,akman-mental]
- bibtexsummary:[/wrf.bib,akman-design-89]
- bibtexsummary:[/wrf.bib,fa-wcusp-87]
- bibtexsummary:[/wrf.bib,akman-barcelona-86]
- bibtexsummary:[/wrf.bib,af-oqiss-86]
- bibtexsummary:[/wrf.bib,fa-rvrvs-86]
- bibtexsummary:[/wrf.bib,fa-sp3sv-85]
- bibtexsummary:[/wrf.bib,fav-vdbpm-85]
- bibtexsummary:[/wrf.bib,akman-robexs-85]
- bibtexsummary:[/wrf.bib,fa-spsgo-84]
- bibtexsummary:[/wrf.bib,wrf-sigplan-84]
- bibtexsummary:[/wrf.bib,wrf-vlsi-82]
- bibtexsummary:[/wrf.bib,wrf-cg-82]
- bibtexsummary:[/wrf.bib,f-3gduh-81]
- bibtexsummary:[/wrf.bib,wrf-cga-81]
- bibtexsummary:[/wrf.bib,f-eadvp-79]
- bibtexsummary:[/wrf.bib,wrf-crc00]
- bibtexsummary:[/wrf.bib,wrf-business-83]
- bibtexsummary:[/wrf.bib,nisen-maturation-78]

# 3. Other research topics

This section presents research that is neither computational cartography nor computational geometry.

More info on Expert System Sensitivity Analysis

## 3.1 Expert system sensitivity analysis

In the 1980s we applied sensitivity analysis from software engineering to expert systems. The titles include:

More info on Non Geometric Data Structures Algorithms

## 3.2 Non-geometric data structures and algorithms

Here are some algorithms and data structures that are neither geometric nor cartographic. The titles include:

# 4. Open topics

Students looking to work with me should read this separate page; its table of contents is below.

More info on Old Program Solicitations

# 5. Old program solicitations

Here are some solicitations and planning documents I wrote while at NSF from 2000 to 2003. They include:

- NSF01-111 and NSF02-155 Computational Algorithms and
Representations for Geometric Objects (CARGO).
*(with B Mann and D Cochran)*. - GeoSpatial Terrain Analysis and Representations (Geo*), ''(with D Cochran)'',
- Computational and Geometric Cartography.

# 6. Short notes

Here are short notes on various topics more-or-less research-related, but not about my research.

- Bresenham Circle And Line Drawing
- Polygon Equation
Does the (piecewise straight border) line of a polygon have an equation, as a circle has the equation
*x*?^{2}+y^{2}=1 - OpenGL Summary
- NTSC and Other TV Formats
- Portability and Standards
- Journals Are Obsolescent
- Efficient Programming
- Splines
- More short notes that haven't yet been transferred to this wiki.

# 7. Advice

# 10. Software notes and reviews

A separate page with usage notes and recommendations on various programs written by others.