W Randolph Franklin home page
... (old version) Login


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.

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

Alternate Terrain Reps


This theme has the following goals:

  1. Study alternate terrain representations that are more compact.
  2. Since the new representations will therefore be lossy, evaluate the size / quality tradeoffs.
  3. These new representations ought to make it easier to represent legal terrain than illegal terrain.
  4. We wish to process datasets up to 50000x50000 elevation posts.
  5. With these new representations, uncompression speed is more important than compression speed.
  6. 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.)

  1. bibtexsummary:[/wrf.bib,stuetzle-sdh-2012]
  2. bibtexsummary:[/wrf.bib,stuetzle-autocarto-2012]
  3. bibtexsummary:[/wrf.bib,li-autocarto-2010]
  4. bibtexsummary:[/wrf.bib,terrain-fwcg-2010]
  5. bibtexsummary:[/wrf.bib,xie-acmgis-2010]
  6. bibtexsummary:[/wrf.bib,wrf-ica99-web]
  7. bibtexsummary:[/wrf.bib,andrade-prog-trans-2008]
  8. bibtexsummary:[/wrf.bib,wrf-sdh-2008]
  9. bibtexsummary:[/wrf.bib,zx-wrf-spie-2007]
  10. bibtexsummary:[/wrf.bib,xie-fwcg-2007]
  11. bibtexsummary:[/wrf.bib,wrf-mi-spie-2006]
  12. bibtexsummary:[/wrf.bib,inanc-fwcg-2006]
  13. bibtexsummary:[/wrf.bib,wrf-autocarto-2006]
  14. bibtexsummary:[/wrf.bib,wrf-cagis-00]
  15. bibtexsummary:[/wrf.bib,wrfelev95]
  16. bibtexsummary:[/wrf.bib,wrf-icip]
  17. bibtexsummary:[/wrf.bib,wrflossy]

Parallel and distributed cartography computation

Publications include:

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

See also the parallel geometry papers below.

Hydrography, bathymetry

Publications include:

  1. bibtexsummary:[/wrf.bib,salles-agile-2012]
  2. bibtexsummary:[/wrf.bib,lau-autocarto-2012]
  3. bibtexsummary:[/wrf.bib,lau-sdh-2012]
  4. bibtexsummary:[/wrf.bib,lau-fwcg-2011]
  5. bibtexsummary:[/wrf.bib,stuetzle-acmgis-2011]
  6. bibtexsummary:[/wrf.bib,lau-cagis-2011]
  7. bibtexsummary:[/wrf.bib,lau-autocarto-2010]
  8. bibtexsummary:[/wrf.bib,lau-fwcg-2010]
  9. bibtexsummary:[/wrf.bib,li-acmgis-2010]
  10. bibtexsummary:[/wrf.bib,ica-2010]
  11. bibtexsummary:[/wrf.bib,lau-acmgis-2009]
  12. bibtexsummary:[/wrf.bib,stookey-acmgis-2008]
  13. bibtexsummary:[/wrf.bib,muckell-fwcg-2007]

Erosion modeling

Publications include:

  1. bibtexsummary:[/wrf.bib,kalamzare-geo-2012]
  2. bibtexsummary:[/wrf.bib,panam-2011]
  3. bibtexsummary:[/wrf.bib,chen-geofrontiers-2011]
  4. bibtexsummary:[/wrf.bib,gross-icse-2010]
  5. bibtexsummary:[/wrf.bib,chen-acmgis-2010]
  6. bibtexsummary:[/wrf.bib,stuetzle-icpmg-2010]
  7. bibtexsummary:[/wrf.bib,stuetzle-fwcg-2009]

More info on GeoStar

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:

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

Publications on Geo* as a project include:

  1. bibtexsummary:[/wrf.bib,icc-2011]

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

More info on Siting

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:

  1. bibtexsummary:[/wrf.bib,magalhaes-ijcisim-2011]
  2. bibtexsummary:[/wrf.bib,magalhaes-his-2010]
  3. bibtexsummary:[/wrf.bib,andrade-geoinfo-ext-viewshed-2008]
  4. bibtexsummary:[/wrf.bib,tracy-acmgis-2008]
  5. bibtexsummary:[/wrf.bib,wrf-fwcg-2008]
  6. bibtexsummary:[/wrf.bib,tracy-fwcg-2008]
  7. bibtexsummary:[/wrf.bib,dt-wrf-spie-2007]
  8. bibtexsummary:[/wrf.bib,acmgis07]
  9. bibtexsummary:[/wrf.bib,wrf-sdh2006]
  10. bibtexsummary:[/wrf.bib,wrf-cv-siting-isprs]
  11. bibtexsummary:[/wrf.bib,wrf-siting-apr2004]
  12. bibtexsummary:[/wrf.bib,wrf-site]
  13. bibtexsummary:[/wrf.bib,fr-hinbv-94]
  14. bibtexsummary:[/wrf.bib,wrf-savannah]

More info on Gridding Contours

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:

  1. bibtexsummary:[/wrf.bib,Gousie05]
  2. bibtexsummary:[/wrf.bib,gousie98]
  3. bibtexsummary:[/wrf.bib,acmgis2003]
  4. Contours to digital elevation models: grid-based surface reconstruction methods, MB Gousie, and
  5. 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

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:

  1. bibtexsummary:[/wrf.bib,fs-ocamo-90-in-geom]
  2. bibtexsummary:[/wrf.bib,fk-vo3tp-93]
  3. bibtexsummary:[/wrf.bib,f-moaap-92]
  4. bibtexsummary:[/wrf.bib,fsskn-ofmop-93]
  5. bibtexsummary:[/wrf.bib,f-cmopa-90]
  6. 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.

Logic programming for map overlay


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

  1. bibtexsummary:[/wrf.bib,wf-lpacm-90]
  2. bibtexsummary:[/wrf.bib,fw-posp-87]
  3. bibtexsummary:[/wrf.bib,fnsw-eupg-86]
  4. bibtexsummary:[/wrf.bib,fwsn-gp-86]
  5. bibtexsummary:[/wrf.bib,fwsn-pgp-86]
  6. bibtexsummary:[/wrf.bib,f-cgp-85]
  7. Polygon overlay in Prolog, (PYF Wu).

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.

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

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:

  1. bibtexsummary:[/wrf.bib,wrf-cga-82]
  2. bibtexsummary:[/wrf.bib,wrf-prism-hu]
  3. bibtexsummary:[/wrf.bib,fl-3gdds-78]

More info on General Cartography

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:

  1. bibtexsummary:[/wrf.bib,wrf-ucgia]
  2. bibtexsummary:[/wrf.bib,f-tcfg-92]
  3. bibtexsummary:[/wrf.bib,f-cslld-91]
  4. bibtexsummary:[/wrf.bib,ucgis-ancart]

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

Fundamentals


Here are pages on

  1. 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.
  2. The uniform grid data structure, for efficiently culling likely intersections in E2 and E3. 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.
  3. Why raster graphics is harder than vector graphics. It's because integers are harder than rationals.

Publications include:

  1. bibtexsummary:[/wrf.bib,grid-2010]
  2. bibtexsummary:[/wrf.bib,afkn-gcugd-89]
  3. bibtexsummary:[/wrf.bib,fnkszw-ugtid-89]
  4. bibtexsummary:[/wrf.bib,fcksa-eugid-88]
  5. bibtexsummary:[/wrf.bib,f-aggo-84]
  6. bibtexsummary:[/wrf.bib,f-aggo-83]
  7. bibtexsummary:[/wrf.bib,f-prga-85]
  8. bibtexsummary:[/wrf.bib,f-cesua-84]
  9. bibtexsummary:[/wrf.bib,f-ero-83]

More info on Local Topology

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:

  1. bibtexsummary:[/wrf.bib,f-ppcvn-87]
  2. bibtexsummary:[/wrf.bib,f-rnrpp-83]

Parallel and distributed geometry algorithms

  1. bibtexsummary:[/wrf.bib,kf-apcus-92]
  2. bibtexsummary:[/wrf.bib,fk-vo3tp-93]
  3. bibtexsummary:[/wrf.bib,nf-bcpp-92]
  4. bibtexsummary:[/wrf.bib,nf-eihc-92]
  5. bibtexsummary:[/wrf.bib,nf-dmppci-91]
  6. bibtexsummary:[/wrf.bib,fk-poshs-90-in-geom]
  7. bibtexsummary:[/wrf.bib,fck-pagc-siam-89]
  8. bibtexsummary:[/wrf.bib,fnkszw-ugtid-89]
  9. bibtexsummary:[/wrf.bib,fcksa-eugid-88]

More info on Connected Components

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:

  1. bibtexsummary:[/wrf.bib,wrf-connect-fwcg2006]
  2. bibtexsummary:[/wrf.bib,landis2006]
  3. bibtexsummary:[/wrf.bib,acse2003]
  4. bibtexsummary:[/wrf.bib,capri01]

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 E3 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:

  1. bibtexsummary:[/wrf.bib,fk-poshs-90-in-geom]
  2. bibtexsummary:[/wrf.bib,f-ltehs-88]
  3. bibtexsummary:[/wrf.bib,fa-agpvo-88-in-geom]
  4. bibtexsummary:[/wrf.bib,fa-sehla-87]
  5. bibtexsummary:[/wrf.bib,f-ehsao-81]
  6. bibtexsummary:[/wrf.bib,f-ltehs-80-in-geom]
  7. bibtexsummary:[/wrf.bib,f-chsa-78]

More info on Nearpt3

Nearest points in E2 and E3


This is a pair of subroutines to find nearest points in E3. 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 E2.

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 7233 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:

  1. bibtexsummary:[/wrf.bib,wrf-nearpt3-mit-2004]
  2. bibtexsummary:[/wrf.bib,wrf-nearpt3-cccg-2005]

More info on All Near Pairs

All near point pairs in E3


This is a program to report all pairs of points nearer than a given distance, from a fixed set of points in E3.

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

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:

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

More info on Union

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:

  1. bibtexsummary:[/wrf.bib,nf-dmppci-91]
  2. bibtexsummary:[/wrf.bib,wrf-union-analysis-2004]
  3. bibtexsummary:[/wrf.bib,wrf-dimacs2005]
  4. bibtexsummary:[/wrf.bib,kf-apcus-92]
  5. bibtexsummary:[/wrf.bib,nf-bcpp-92]
  6. bibtexsummary:[/wrf.bib,nf-eihc-92]
  7. bibtexsummary:[/wrf.bib,fckaw-egoc-90]
  8. bibtexsummary:[/wrf.bib,fck-pagc-siam-89]
  9. bibtexsummary:[/wrf.bib,f-eiclb-89]
  10. bibtexsummary:[/wrf.bib,fkn-epgol-89]
  11. bibtexsummary:[/wrf.bib,f-epiu-82]

More info on Unite Circles

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

Octree creation


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

  1. bibtexsummary:[/wrf.bib,fa-bospj-85]
  2. bibtexsummary:[/wrf.bib,fa-bospi-85]
  3. bibtexsummary:[/wrf.bib,fa-odscs-85]
  4. bibtexsummary:[/wrf.bib,af-rorhp-89]
  5. bibtexsummary:[/wrf.bib,af-rrkt-89]

Edge intersection

  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.

Misc papers

  1. bibtexsummary:[/wrf.bib,akman-dublin]
  2. bibtexsummary:[/wrf.bib,akman-mental]
  3. bibtexsummary:[/wrf.bib,akman-design-89]
  4. bibtexsummary:[/wrf.bib,fa-wcusp-87]
  5. bibtexsummary:[/wrf.bib,akman-barcelona-86]
  6. bibtexsummary:[/wrf.bib,af-oqiss-86]
  7. bibtexsummary:[/wrf.bib,fa-rvrvs-86]
  8. bibtexsummary:[/wrf.bib,fa-sp3sv-85]
  9. bibtexsummary:[/wrf.bib,fav-vdbpm-85]
  10. bibtexsummary:[/wrf.bib,akman-robexs-85]
  11. bibtexsummary:[/wrf.bib,fa-spsgo-84]
  12. bibtexsummary:[/wrf.bib,wrf-sigplan-84]
  13. bibtexsummary:[/wrf.bib,wrf-vlsi-82]
  14. bibtexsummary:[/wrf.bib,wrf-cg-82]
  15. bibtexsummary:[/wrf.bib,f-3gduh-81]
  16. bibtexsummary:[/wrf.bib,wrf-cga-81]
  17. bibtexsummary:[/wrf.bib,f-eadvp-79]
  18. bibtexsummary:[/wrf.bib,wrf-crc00]
  19. bibtexsummary:[/wrf.bib,wrf-business-83]
  20. bibtexsummary:[/wrf.bib,nisen-maturation-78]

Other research topics

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

Expert system sensitivity analysis


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

  1. bibtexsummary:[/wrf.bib,wrf-gupta]
  2. bibtexsummary:[/wrf.bib,wrf-hawaii-88]

Non-geometric data structures and algorithms


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

  1. bibtexsummary:[/wrf.bib,wrf-cacm-82]
  2. bibtexsummary:[/wrf.bib,wrf-ipl-79]

Open topics

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

Old program solicitations


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

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

Short notes

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

  1. Bresenham Circle And Line Drawing
  2. Polygon Equation Does the (piecewise straight border) line of a polygon have an equation, as a circle has the equation x2+y2=1?
  3. OpenGL Summary
  4. NTSC and Other TV Formats
  5. Portability and Standards
  6. Journals Are Obsolescent
  7. Efficient Programming
  8. Splines
  9. More short notes that haven't yet been transferred to this wiki.

Advice

Proposal writers cheat sheet

Workshop organizers cheat sheet

Software notes and reviews

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