(in WR Franklin → Research)
My research interests since high school have centered on geometry, including graphics, cartography, and efficient implementations thereof. A recent major theme was GeoStar, a DARPA-funded project for representing and operating on terrain, that is, elevation. Recent successes, with the assistance of my students and collaborators, include the following.
- 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 built on my 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, mine 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 my 1973 version, which was the first TIN implementation in cartography or GIS.
- Siting hundreds of observers, e.g., border guards, to cover the terrain, then planning a minimal cost smuggler's path to avoid them.
My big Geo* problem, assigned by DARPA, was this:
A good first paper is #10, presented at 2007 ACM-GIS in Seattle.
Here is a good summary Geo* talk (7/2010); Videos in talk: 1, 2, 3.
Public Publications / Presentations
(:row:) (:celli# align=right:)
| Two Novel Surface Representation Techniques, W. Randolph Franklin, Metin Inanc, and Zhongyi Xie, Autocarto 2006, June 2006.
(:row:) (:celli# align=right:) | Tradeoffs When Multiple Observer Siting on Large Terrain Cells, W. Randolph Franklin and Christian Vogt, 12th International Symposium on Spatial Data Handling, July 2006.
(:row:) (:celli# align=right:) | 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.
(:row:) (:celli# align=right:) | 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.
(:row:) (:celli# align=right:) | 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
(:row:) (:celli# align=right:) | 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
(:row:) (:celli# align=right:) | An improved LLL algorithm. Franklin T Luk and Daniel M Tracy, Linear Algebra and its Applications, 2007.
(:row:) (:celli# align=right:) | 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.
(:row:) (:celli# align=right:) | 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.
(:row:) (:celli# align=right:) | 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 (much more recent than the paper.)
(:row:) (:celli# align=right:) | 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, Video demoing Oahu dataset.
(:row:) (:celli# align=right:) | 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.
(:row:) (:celli# align=right:) | 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.
(:row:) (:celli# align=right:) | Progressive transmission of lossily compressed terrain. Zhongyi Xie, Marcus A. Andrade, W Randolph Franklin, Barbara Cutler, Metin Inanc, Jonathan Muckell and Daniel M. Tracy. Conferencia Latinoamericana de Informática (CLEI 2008), Santa Fe, Argentina. 8--12 Sep 2008. paper.
(:row:) (:celli# align=right:) | Efficient viewshed computation on terrain in external memory. Marcus Andrade, Salles V. G. Magalhães, Mirella A. Magalhães, W. Randolph Franklin, Barbara M. Cutler, (conditionally accepted, Oct 2008).
(:row:) (:celli# align=right:) | Path planning on complex terrain. Dan Tracy, W Randolph Franklin, Barb Cutler, Franklin Luk, Marcus Andrade and Jared Stookey. 18th Fall Workshop on Computational Geometry (FWCG 2008), Rensselaer Polytechnic Institute, Troy NY, 31 Oct - 1 Nov 2008. 2 page abstract, talk, poster.
(:row:) (:celli# align=right:) | Operating on large geometric datasets. W. Randolph Franklin. 18th Fall Workshop on Computational Geometry (FWCG 2008), Rensselaer Polytechnic Institute, Troy NY, 31 Oct - 1 Nov 2008. 2 page abstract, talk.
(:row:) (:celli# align=right:) | Parallel ODETLAP for terrain compression and reconstruction. Jared Stookey, Zhongyi Xie, Barbara Cutler, W. Randolph Franklin, Dan Tracy and Marcus V.A. Andrade. 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS 2008), Walid G. Aref et al (editors). paper, talk.
(:row:) (:celli# align=right:) | Path planning on a compressed terrain. Daniel M. Tracy, W. Randolph Franklin, Barbara Cutler, Franklin T. Luk, Marcus Andrade and Jared Stookey. 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS 2008), Walid G. Aref et al (editors). poster, talk.
(:row:) (:celli# align=right:) | Evaluating hydrology preservation of simplified terrain representations. Christopher Stuetzle, W. Randolph Franklin, Barbara Cutler, Jonathan Muckell, Marcus Andrade, Jared Stookey, Metin Inanc and Zhongyi Xie. 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS 2008), Walid G. Aref et al (editors). poster, talk. (Winner of a best poster presentation award.) |
Student theses
(:row:) (:celli# align=right:)
| Compressing terrain elevation datasets, Metin Inanc, PhD, Computer Science, May 2008. Thesis.
(:row:) (:celli# align=right:) | Parallel terrain compression and reconstruction, Jared Stookey, Master of Science, Computer and System Engineering, Dec 2008. Thesis.
(:row:) (:celli# align=right:) | Representation, compression and progressive transmission of digital terrain data using over-determined Laplacian partial differential equations Zhongyi Xie, Master of Science, Computer Science, May 2008. Thesis.
(:row:) (:celli# align=right:) | Evaluating and compressing hydrology on simplified terrain, Jon Muckell, Masters, Computer and Systems Engineering, April 2008. Thesis.
(:row:) (:celli# align=right:) | Path planning and slope representation on compressed terrain, Dan Tracy, PhD, Computer Science, May 2009. Thesis. |
Personnel
Faculty
| Who | What |
|---|---|
| Dr Marcus A V Andrade, Universidade Federal de Viçosa, Brazil | Visited RPI from April 2007 to April 2008 sponsored by the government of Brazil. Continuing to collaborate. |
| Dr Barbara M Cutler | Computer Graphics, assistant director of GeoStar project at RPI |
| Dr W Randolph Franklin | PI |
| Dr Frank Luk | Numerical analysis; moved to Hong Kong to be Vice-President (Academic) of Hong Kong Baptist University |
Students
| Who | What |
|---|---|
| Dr Metin Inanc | ODETLAP etc. |
| You Li | bathymetry |
| Jon Muckell | Hydrology |
| Jake Stookey | Adapting ODETLAP to the massively parallel IBM BG/L machine in RPI's CCNI. |
| Chris Stuetzle | Fitting slopes with ODETLAP. Transitioned to our newer CDI project. |
| Dr Dan Tracy | Path planning and siting |
| Zhongyi Xie | ODETLAP etc. Graduated, May 2008 with M.Sc. |
| Eddie Lau Tsz Yam | bathymetry |
Video
- Video by Dan Tracy showing the path planning
Press and Blog Mentions
(Links may sometimes go stale.)
Inside RPI
(:row:) (:celli# align=right:)
| RPI Press release, 10/31/2005
(:row:) (:celli# align=right:) | RPI School of Engineering Press Release
(:row:) (:celli# align=right:) | Rensselaer School of Engineering News
(:row:) (:celli# align=right:) | Improving Terrain Maps, Rensselaer Alumni Magazine Winter 2005-06 |
Outside RPI
(:row:) (:celli# align=right:)
| Better terrain maps of Earth... and beyond, in Roland Piquepaille's Technology Trends, 5 nov 2005
(:row:) (:celli# align=right:) | ZDNet, 11/5/2005
(:row:) (:celli# align=right:) | Surfwax Government News
(:row:) (:celli# align=right:) | Defence Talk, 11/1/2005
(:row:) (:celli# align=right:) | Advanced Imaging (no longer online)
(:row:) (:celli# align=right:) | ACM Technews 7(862), 11/2/2005
(:row:) (:celli# align=right:) | Interview on WGY AM-810 radio, 11/3/2005 |
Commercialization
In 2007.2, two SBIRs hit the street that were clearly based on my research.
(:row:) (:celli# align=right:)
|
A07-123 Novel Representations of Elevation Data. That led to two phase I awards:
(:row:) (:celli# align=right:) |
A07-126 Optimal Intervisibility Site Selection. The solicitiation cited me four times. That led to the phase I award W9132V-08-C-0005 Optimal Intervisibility Site Selection to Toyon Research Corp. |
(Unfortunately) I have no connection to any of those companies.
The fact that someone in the ARO considers this work important enough to issue solicitations to extend it says that DARPA is succeeding in having Geo* research transition to the Army.