Franklin's research interests since high school have centered on geometry, including graphics, cartography, and efficient implementations thereof. The current major theme is a GeoStar, DARPA-funded project for representing and operating on terrain, that is, elevation. Recent successes, with the assistance of his students, include the following.

  1. Using ODETLAP, an overdetermined extension of a Laplacian PDE, to compress the terrain about a factor of 100 while minimizing the elevation error. This technique has several other applications, such as fitting a surface from a set of nested curved contours so that the contours are not visible in the surface, and so that local maxima can be inferred.
    ODETLAP builds on Franklin's Triangulated Irregular Network (TIN) program, which can process a grid of 10,000x10,000 elevations to a piecewise triangular approximation on a laptop. This method, like everything listed here, operates in memory, usually on a laptop. This makes these programs much faster than those requiring secondary storage. Unlike some other TIN programs, Franklin's is incremental, and therefore sorts the points in order of importance. Therefore they can be used to progressively transmit the surface. This current TIN program is an extension Franklin's 1973 version, which was the first TIN implementation in cartography or GIS.
  2. Siting hundreds of observers, e.g., border guards, to cover the terrain, then planning a minimal cost smuggler's path to avoid them.

His current big problem, assigned by DARPA, is this:

to extend the terrain compression algorithm so that the slope is accurate to within 2°. That is, the slope computed on the restored terrain should match the slope of original terrain within 2°. That means that if the elevation posts are on a 30 meter grid, then the elevation deltas should be accurate within 1 meter, altho the elevations themselves might drift somewhat. A secondary goal is that, in addition to RMS elevation error, "features" of the terrain should be preserved.

A good first paper is #10, presented at 2007 ACM-GIS in Seattle.

Public Publications / Presentations

1 Two Novel Surface Representation Techniques, W. Randolph Franklin, Metin Inanc, and Zhongyi Xie, Autocarto 2006, June 2006.
2 Tradeoffs When Multiple Observer Siting on Large Terrain Cells, W. Randolph Franklin and Christian Vogt, 12th International Symposium on Spatial Data Handling, July 2006.
3 Alternative sculpting hypotheses for terrain data compression, Caroline Westort and W. Randolph Franklin, Proceedings of SPIE Vol. 6313 Advanced Architectures, and Implementations XVI, 15-16 August 2006, International Society for Optical Engineering, San Diego CA, paper 6313-16, Session 4.
4

Compressing terrain datasets using segmentation, W. Randolph Franklin and Metin Inanc, Proceedings of SPIE Vol. 6313 Advanced Architectures, and Implementations XVI, 15-16 August 2006, International Society for Optical Engineering, San Diego CA, paper 6313-17, Session 4.

5 Terrain Representation Using Tessellation of Irregular Planar Tiles, Metin Inanc and W Randolph Franklin, 16th Fall Workshop on Computational Geometry, 10-11 Nov 2006, Smith College, Northampton MA, (poster presentation) poster, extended abstract
6 Multiple Observer Siting on a Compressed Terrain, Daniel Tracy, W Randolph Franklin and Franklin Luk, 16th Fall Workshop on Computational Geometry, 10-11 Nov 2006, Smith College, Northampton MA, (poster presentation) poster, extended abstract
7 An Improved LLL Algorithm, Franklin T Luk and Daniel M Tracy, Linear Algebra and its Applications, 2007.
8 Surface compression using over-determined Laplacian approximation, Zhongyi Xie, W. Randolph Franklin, Barbara Cutler, Marcus A Andrade, Metin Inanc and Daniel M Tracy, Proceedings of SPIE Vol. 6697 Advanced Signal Processing Algorithms, Architectures, and Implementations XVII, 27 August 2007, International Society for Optical Engineering, San Diego CA, paper 6697-15.
9

Path planning on lossily compressed terrain, Dan Tracy and W. Randolph Franklin, Proceedings of SPIE Vol. 6697 Advanced Signal Processing Algorithms, Architectures, and Implementations XVII, 27 August 2007, International Society for Optical Engineering, San Diego CA, paper 6697-16.

10 Smugglers and Border Guards - The GeoStar Project at RPI, W Randolph Franklin, Metin Inanc, Zhongyi Xie, Daniel M Tracy, Barbara Cutler, Marcus V A Andrade and Franklin Luk, 15th ACM International Symposium on Advances in Geographic Information Systems (ACM GIS 2007), Nov 2007, Seattle, WA, USA.

talk (The talk is much more recent than the paper.)

11

Drainage Network and Watershed Reconstruction on Simplified Terrain. Jonathan Muckell, Marcus Andrade, W. Randolph Franklin, Barbara Cutler, Metin Inanc, Zhongyi Xie and Daniel M. Tracy. 17th Fall Workshop on Computational Geometry, IBM TJ Watson Research Center, Hawthorne NY, 2-3 Nov 2007. Poster, 2 page abstract, Oahu video.

12

Approximating Terrain with Over-Determined Laplacian PDEs. Zhongyi Xie, Marcus A. Andrade, W. Randolph Franklin, Barbara Cutler, Metin Inanc, Daniel M. Tracy and Jonathan Muckell. 17th Fall Workshop on Computational Geometry, IBM TJ Watson Research Center, Hawthorne NY, 2-3 Nov 2007. Poster, 2 page abstract.

13

Path Planning on a Compressed Terrain Daniel M. Tracy, W. Randolph Franklin, Barbara Cutler, Marcus Andrade, Franklin T. Luk, Metin Inanc, and Zhongyi Xie. (submitted, June 2008).

14

Slope accuracy and path planning on compressed terrain. W. Randolph Franklin, Daniel M. Tracy, Marcus Andrade, Jonathan Muckell, Metin Inanc, Zhongyi Xie and Barbara Cutler. 13th International Symposium on Spatial Data Handling 2008 (SDH08) June 2008, Montpelier, FR.

15

Preserving the hydrology on simplified terrain. Jonathan Muckell, Marcus Andrade, W. Randolph Franklin, Barbara Cutler, Metin Inanc, and Zhongyi Xie. (submitted, June 2008).

16

Lossy compression for progressive transmission of digital terrain models. Marcus Andrade, Zhongyi Xie, W. Randolph Franklin, Barbara Cutler, Metin Inanc, Jonathan Muckell and Daniel M Tracy. (draft, Jan 2008).

17

Parallel ODETLAP for terrain compression and reconstruction. Zhongyi Xie, Jared Stookey, Barbara Cutler, W. Randolph Franklin, Daniel M Tracy, and Marcus VA Andrade. (draft, Jan 2008).

18

Efficient viewshed computation on terrains in external memory. Marcus Andrade, Salles V. G. Magalhães, W. Randolph Franklin, Barb Cutler, Mirella A. Magalhães, .... (submitted, Jan 2008).

Status Report

  1. Summary of the RPI GeoStar project, Oct 2007, powerpoint or pdf.

Video

  1. Video by Dan Tracy showing the path planning


<< | Research Page List | >>