W. Randolph Franklin, Professor

Electrical, Computer, and Systems Engineering Dept.,
6026 JEC,
Rensselaer Polytechnic Institute,
110 Eighth St,
Troy NY, 12180
USA

Communication

Vcards         How To Email Me         GPG key
phone: +1.518.276.6077 (let it ring many times)
Travel Directions to RPI

        


Snowshoeing, Feb 2009

Amazonian rainforest, July 2009

Professional       Brief Bio       Long resume

  • BSc (Toronto), AM, PhD, Applied Math (Harvard).
  • Program Director, Numeric, Symbolic, and Geometric Computation Program, CISE, National Science Foundation, 2000-2002.
  • Visiting Professor, UC Berkeley, 1985-1986.
  • Visiting positions at Genoa, Laval, CSIRO Canberra, National University of Singapore, 1992-1993.
  • supervised 13 PhD and 65 masters graduates.
          

Teaching, students Detailed teaching page

Research

Geo* accomplishments:

  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.

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" 1. The Geo in geometry is from the Greek Γη meaning, ''earth, ground, land''. 2. My major recently concluded project was Geo*, a DARPA-funded project for representing and operating on terrain, that is, elevation.

My current project, NSF/CDI Fundamental Terrain Representations and Operations 3, attempts to predict how erosion occurs in levee failure by overtopping, and, after a failure, to reverse-simulate what happened.

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

Here are various details: strategy · computational cartography · computational geometry · other topics · proposal writing notes · misc notes · former masters (65) and doctoral (13) students · new topics.


(submitted)

Salles V. G. de Magalhães, Marcus V. A. Andrade, and W. Randolph Franklin. Siting observers in huge terrains stored in external memory

Abstract: We present an algorithm and implementation for EmSite, which sites multiple (perhaps hundreds) of observers on a DEM terrain that is too large to store in internal memory. EmSite has been implemented in C++. Tests show it to use a median of 19% fewer observers to obtain the same joint visibility index (coverage) on huge terrains, compared to a naive partitioning of the terrain into subregions. This will permit more efficient positioning of facilities such as mobile phone towers, fire observation towers, and vigilance systems. paper.

(submitted)

W. R. Franklin, '''Parallel Volume Computation of the Union of Many Cubes'''

We present an algorithm and implementation for computing volumes and areas of the union of many congruent axis-aligned cubes. Its expected execution time is linear. It has been tested to 100M cubes. The ideas extend to any mass property of the union of any polyhedra, and to online computations as more inputs are added. The algorithm is mostly a series of map-reduce operations and so parallelizes quite well. Inserting a new cube and recomputing takes constant expected time.

The algorithm combines local topological formulae with a uniform grid. It does not build a computation tree of height log(N), but rather computes all the possibly relevant intersections in one step. It is an exact computation, not a sampling or cellular decomposition technique. Most of the operations are a map-reduce, and so they parallelize quite well, better than more complicated data structures. paper.

FWCG2009

Christopher S. Stuetzle, Zhongxian Chen, Katrina Perez, Jared Gross, Barbara Cutler, W. Randolph Franklin, and Thomas Zimmie. Segmented height field and smoothed particle hydrodynamics in erosion simulation. extended abstract.

ACM SIGSPATIAL GIS2009

Tsz-Yam Lau, You Li, Zhongyi Xie, and W. Randolph Franklin. Sea floor bathymetry trackline surface fitting without visible artifacts using ODETLAP. paper, poster: pptx|pdf, fast forward talk. video. Awarded the best fast forward presentation.

FWCG2008

Operating on large geometric datasets, Fall Workshop in Computational Geometry (FWCG) 2008, 1 Nov 2008, extended abstract, talk, (11/2/2008). Longer papers and talks on the same topic:

  1. Analysis of mass properties of the union of millions of polygedra
  2. Mass properties of the union of millions of identical cubes]
  3. related talk
  4. earlier but more detailed talk

ACMGIS2008

3 presentations by my students at 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS 2008), Irvine CA, 5-7 Nov 2008.

  1. Parallel ODETLAP for terrain compression and reconstruction. paper, talk.
  2. Path planning on a compressed terrain. poster.
  3. Evaluating hydrology preservation of simplified terrain representations. PhD student poster (won a best poster award), fast forward presentation.

Recent additions

  • AllNearPairs - program to report all pairs of points nearer than a given distance, from a fixed set of points in E3.
  • Parallel Volume Computation of the Union of Many Cubes paper online; see abstract above. (2/24/2010)
  • IDEA student surveys of my courses for the last 3 semesters online. (1/28/2010)
  • Siting observers in huge terrains stored in external memory paper online; see abstract above. (1/27/2010)
  • NSF/CDI Fundamental Terrain Representations and Operations project site linked in. (1/27/2010)
  • Updated page on algorithm to compute area and perimeter of the union of circles, with test code. (1/1/2010)
  • ACM SIGSPATIAL GIS 2009 and FWCG 2009 presentations, detailed above. (11/2009).
  • HTML version of my resume including links to most of my papers and talks. (6/22/2009)
  • Reorganization and updating of my Research pages. (6/17/2009)
  • My letter to the Albany (NY) Times Union recommending Pres. Jackson to replace Sen Clinton. (1/4/2009)
  • New Workshop Organizers Cheat Sheet. (12/13/2008)
  • Updated Proposal Writers Cheat Sheet. (10/30/2008)
  • Reorganized web site, (10/19/2008)
  • The Fall Workshop in Computational Geometry 2008 (FWCG2008) is at RPI on Fri Oct 31 and Sat Nov 1, 2008. The local arrangements chair is Barb Cutler. The accepted abstracts are online. (10/30/2008)
  • Updated resume-franklin.pdf with links to most papers and some talks. (5/5/2008)
  • Update home page; new page: GeoStar. (4/26/2008)
  • My letter to the Albany NY Times Union on state support of private higher education, (12/28/2007)
  • reorganized home page, (12/13/2007)
  • NSF And DARPA - talk at RPI, (12/10/2007)
  • Misc points for my advisees (started 3/13/2007)

 

     

Locations of visitors to this page

Things that don't fit anywhere else

 

1 (Merriam-Webster dictionary) ⇑

2 The American Heritage® Book of English Usage ⇑

3 Cutler, Zimmie,Franklin. NSF CMMI-0835762: CDI-Type I: Fundamental Terrain Representations and Operations ⇑

This page looks best in Firefox, Mozilla, Safari, or Epiphany, and worst in Explorer (since Explorer, even IE8, doesn't implement the relevant parts of CSS3) .