I develop and implement fast parallel algorithms on very large geometric datasets in CAD and GIS. I've 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; awards are listed below.

Recent papers and talks:
2018
 W. Randolph Franklin, Salles V. G. Magalhães, and Marcus V. A. Andrade.
Data structures for parallel spatial algorithms on large datasets (vision paper).
In Proceedings of BigSpatial’18: 7th ACM SIGSPATIAL Workshop on Analytics for Big Geospatial Data. Seattle, USA, 6 Nov 2018.
[abstract▼] [details] [full text] [slides]
[BibTeX▼]
This paper describes data structures and algorithms for efficient implementation of GIS operations for large datasets on multicore Intel CPUs and on NVIDA GPUs. Typical operations are boolean combinations of polygons and map overlay. Efficient parallelization prefers simple regular data structures, such as structures of arrays of plain old datatypes. Warps of 32 threads are required to execute the same instruction (or be idle). Ideally, the data used by adjacent threads is adjacent in memory. Minimizing storage is important, as is accessing it in a regular pattern. That disparages pointers, linked lists, and trees. That implies that explicitly representing global topology is bad. If using only local topological formulae is sufficient, then it will be much faster. E.g., for many operations on a 2D map (aka planar graph), the set of oriented edges suffices. Each edge knows the locations of its endpoints and the ids of its adjacent polygons. Any mass operation, such as area computation or point location, can be implemented as a mapreduce. All these techniques also apply in 3D to CAD/CAM and additive manufacturing. Indeed they are more important there.
@inproceedings{pardsbigspatial2018,
author = "Franklin, W. Randolph and Magalhães, Salles V. G. and Andrade, Marcus V. A.",
title = "Data Structures for Parallel Spatial Algorithms on Large Datasets (Vision paper)",
address = "Seattle, {USA}",
month = "6 Nov",
booktitle = "Proceedings of {BigSpatial’18}: 7th {ACM SIGSPATIAL} Workshop on Analytics for Big Geospatial Data",
year = "2018",
href = "\bibhrefpt{227pardsbigspatial2018}{227pardsbigspatial2018talk.pdf}",
customlinkslides = "https://wrf.ecse.rpi.edu/p/227pardsbigspatial2018talk.pdf",
mykey = "parallel"
}
 W. Randolph Franklin, Salles V. G. Magalhães, and Marcus V. A. Andrade.
Exact fast parallel intersection of large 3D triangular meshes (extended abstract).
In 28th Annual Fall Workshop on Computational Geometry. Queens College, CUNY, New York City, 26–27 Oct 2018.
[abstract▼] [details] [full text]
[BibTeX▼]
We present 3DEPUGOverlay, a fast, exact, parallel, memoryefficient, algorithm for computing the intersection between two large 3D triangular meshes with geometric degeneracies. Applications include CAD/CAM, CFD, GIS, and additive manufacturing. 3DEPUGOverlay combines 5 separate techniques: multiple precision rational numbers to eliminate roundoff errors during the computations; Simulation of Simplicity to properly handle geometric degeneracies; simple data representations and only local topological information to simplify the correct processing of the data and make the algorithm more parallelizable; a uniform grid to efficiently index the data, and accelerate testing pairs of triangles for intersection or locating points in the mesh; and parallel programming to exploit current hardware. 3DEPUGOverlay is up to 101 times faster than LibiGL, and comparable to QuickCSG, a parallel inexact algorithm. 3DEPUGOverlay is also more memory efficient. In all test cases 3DEPUGOverlay's result matched the reference solution. It is freely available for nonprofit research and education at https://github.com/sallesviana/MeshIntersection . The full version of this paper is being presented at the 2018 International Meshing Roundtable; it is currently online at https://project.inria.fr/imr27/files/2018/09/1035.pdf.
@inproceedings{exactfastparallelfwcg2018,
author = "Franklin, W. Randolph and Magalhães, Salles V. G. and Andrade, Marcus V. A.",
title = "Exact fast parallel intersection of large 3{D} triangular meshes (extended abstract)",
booktitle = "28th Annual Fall Workshop on Computational Geometry",
address = "Queens College, {CUNY}, New York City",
year = "2018",
month = "2627 Oct",
href = "\bibhref{229exactfastparallelfwcg2018}",
mykey = "parallel"
}
 W. Randolph Franklin, Salles V. G. Magalhães, and Marcus V. A. Andrade.
Exact fast parallel intersection of large 3D triangular meshes.
In 27th International Meshing Roundtable. Alberqueque, New Mexico, 2 Oct 2018.
[abstract▼] [details] [full text] [slides]
[BibTeX▼]
We present 3DEPUGOverlay, a fast, exact, parallel, memoryefficient, algorithm for computing the intersection between two large 3D triangular meshes with geometric degeneracies. Applications include CAD/CAM, CFD, GIS, and additive manufacturing. 3DEPUGOverlay combines 5 separate techniques: multiple precision rational numbers to eliminate roundoff errors during the computations; Simulation of Simplicity to properly handle geometric degeneracies; simple data representations and only local topological information to simplify the correct processing of the data and make the algorithm more parallelizable; a uniform grid to efficiently index the data, and accelerate testing pairs of triangles for intersection or locating points in the mesh; and parallel programming to exploit current hardware. 3DEPUGOverlay is up to 101 times faster than LibiGL, and comparable to QuickCSG, a parallel inexact algorithm. 3DEPUGOverlay is also more memory efficient. In all test cases 3DEPUGOverlay's result matched the reference solution. It is freely available for nonprofit research and education.
@inproceedings{exactfastparallelimr2018,
author = "Franklin, W. Randolph and Magalhães, Salles V. G. and Andrade, Marcus V. A.",
title = "Exact fast parallel intersection of large 3{D} triangular meshes",
booktitle = "27th International Meshing Roundtable",
address = "Alberqueque, New Mexico",
year = "2018",
month = "2 Oct",
href = "\bibhrefpt{222exactfastparallelimr2018}{222exactfastparallelimr2018talk.pdf}",
mykey = "parallel",
customlinkslides = "https://wrf.ecse.rpi.edu/p/222exactfastparallelimr2018talk.pdf"
}

Professional summary
 Professor, ECSE Dept, RPI
 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.
 Visitor at Georgia Tech, 2016.
 GPG key
 Vcard
 Email: frankwrATSIGNrpiONEDOTedu

Brief Bio

Long resume — (Education  Professional Career  Publications  Presentations  Synergistic Activities and Service  Grad Students  Teaching or Course Development  Hardware Used  Professional Memberships  Major Research Grants), including postal address, email (GPG welcomed), phone

Google scholar profile.

Recent grants.

Research

Software

Publications

Awards

RPI Articles

Teaching

Past students

Advice

Misc