W. Randolph Franklin

Professor, Electrical, Computer, and Systems Engineering

W. Randolph Franklin  develops and implements fast parallel algorithms on very large geometric datasets in CAD and GIS.   He's also modeled and processed large terrain databases, e.g., to compress, to compute hydrography and visibility, and to site observers, and compressed 5D environmental data sets.    The algorithms are the fastest in their class.

His current research hobby is designing and implementing small, simple, and fast data structures and algorithms for large geometric datasets.  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.

He is now currently studying parallel CAD operations, such as overlaying 3D triangulations (tetrahedrulations).  3D-EPUG-Overlay is an algorithm for exactly computing the intersection (it can also compute general overlays) of pairs of 3D triangulated meshes. Each input mesh may represent a single solid or a more complex polygonal subdivision (representing multiple solids, each one identified by a label). 3D-EPUG-Overlay employs a combination of several techniques to ensure its correctness and efficiency.

His  last major NSF research project was to understand the mathematics of terrain.   Another recent NSF project, together with Cutler and Zimmie, was analyzing how levees erode when overtopped, and testing models in a geotechnical centrifuge.  Subprojects include compressing terrain while preserving slope, compressing multidimensional environmental data, and extending partial hydrological data to a complete and consistent river network.

Another major project compressed and operated on terrain for DARPA/DSO/GeoStar.  The operations included multiple observer siting and path planning.  His longterm uneachable goal is to establish terrain modeling
on a proper formal foundation that respects its physical properties.

Previous positions include: Visitor at Georgia Tech, spring 2016, Program Director, Numeric, Symbolic, and Geometric Computation Program, CISE, National Science Foundation, 2000—2002, visiting positions at Genoa, Laval, CSIRO Canberra, National University of Singapore, 1992—1993, and Visiting Professor, UC Berkeley,
1985—1986.

 

Education

Ph.D. Applied Mathematics (Harvard University, 1978), A.M. Applied Mathematics (Harvard University, 1975), B.Sc. Computer Science (University of Toronto, 1973), 3 short courses from the Government Affairs Institute at Georgetown University, 2001-2002.

Research Focus
  • parallel computing
  • computational geometry
  • geographic information science
  • computer aided design
  • efficient algorithms for large geometric datasets
  • modeling terrain
Select Works
  • W. Randolph Franklin and Salles V. G. Magalhães. Parallel intersection detection in massive sets of cubes. In Proceedings of BigSpatial’17: 6th ACM SIGSPATIAL Workshop on Analytics for Big Geospatial Data, Los Angeles Area, CA, USA, 7-10 Nov 2017.
  • Salles V. G. Magalhães, W. Randolph Franklin and Marcus V. A. Andrade. Fast exact parallel 3D mesh intersection algorithm using only orientation predicates. In 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL 2017), Los Angeles Area, CA, USA, 7-10 Nov 2017.
  • W. Randolph Franklin, Salles V. G. Magalhães and Marcus V. A. Andrade. An exact and efficient 3D mesh intersection algorithm using only orientation predicates. In S3PM-2017: International Convention onShape, Solid, Structure, & Physical Modeling, Shape Modeling International (SMI-2017) Symposium, Berkeley, California, USA, 19-23 June 2017.
  • Salles V. G. Magalhães, Marcus V. A. Andrade, W. Randolph Franklin, Wenli Li and Maurício G. Gruppi. Exact intersection of 3D geometric models. In Geoinfo 2016, XVII Brazilian Symposium on GeoInformatics, Campos do Jordão, SP, Brazil, Nov 2016.
  • Salles Viana Gomes de Magalhães , W. Randolph Franklin, Wenli Li and Marcus Vinicius Alvim Andrade. An efficient map-reduce algorithm for spatio-temporal analysis using Spark (GIS Cup). In 5th GIS-focused algorithm competition, GISCup 2016, co-located with ACM SIGSPATIAL GIS, 2016. Winner (2nd place).
  • Wenli Li and W. Randolph Franklin. GPU--Accelerated Multiple Observer Siting. Photogrammetric Engineering & Remote Sensing, 83(6):439-446. doi: 10.14358/PERS.83.6.439, Jun 2017
  • David Hedin and W. Randolph Franklin. NearptD: A Parallel Implementation of Exact Nearest Neighbor Search using a Uniform Grid. In Canadian Conference on Computational Geometry, Vancouver Canada, Aug 2016.
  • Salles V. G. Magalhães, Marcus V. A. Andrade , W. Randolph Franklin and Wenli Li. PinMesh -- Fast and exact 3D point location queries using a uniform grid. Computer & Graphics Journal, special issue on Shape Modeling International 2016, 58:1-11. doi: 10.1016/j.cag.2016.05.017, Aug 2016. (http://www.sciencedirect.com/science/article/pii/S0097849316300607 online 17 May). Awarded a reproducibility stamp, http://www.reproducibilitystamp.com/