W Randolph Franklin

Electrical, Computer, and Systems Engineering
JEC 6026

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,


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.

Focus Area

efficient parallel and GPU algorithms for large geometric and spatial datasets

Selected Scholarly Works

Marcelo de Matos Menezes, Salles Viana Gomes Magalhães, Matheus Aguilar de Oliveira, W. Randolph Franklin, and Rodrigo Eduardo de Oliveira Bauer Chichorro. Fast parallel evaluation of exact geometric predicates on GPUs. J. Computer Aided Design, September 2022. Special Issue: 28th International Meshing Roundtable: Mesh Modeling for Simulations and Visualization. , doi: 10.1016/j.cad.2022.103285.

W. Randolph Franklin and Salles Viana Gomes de Magalhães. Minimal representations of polygons and polyhedra. In John Krumm, Andreas Züfle, and Cyrus Shahabi, editors, Spatial Gems, volume 1, chapter 5. ACM, 2022

Marcelo de Matos Menezes, Salles Viana Gomes de Magalhães, Matheus Aguilar, W. Randolph Franklin, and Bruno Coelho. Employing GPUs to accelerate exact geometric predicates for 3D geospatial processing. In John Krumm, Andreas Züfle, and Cyrus Shahabi, editors, Spatial Gems, volume 1, chapter 11. ACM, 2022.

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.

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

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/

Max J Egenhofer, Keith C Clarke, Song Gao, Teriitutea Quesnot, W. Randolph Franklin, May Yuan and David Coleman. Contributions of GIScience over the Past Twenty Years. In Harlan Onsrud and Werner Kuhn, editor, Advancing Geographic Information Science: The Past and Next Twenty Years, chapter 1, pages 9-34. GSDI association press. 978-0-9852444-4-6, 2016.

Mehrad Kamalzare, Thomas F. Zimmie, Barbara Cutler and W. Randolph Franklin. A New Visualization Method to Evaluate Sediment Transport and Erosion. Geotechnical Testing Journal, 39(3). doi: 10.1520/GTJ20140226, May 2016.