Source: https://wrf.ecse.rpi.edu/nikola/pages/index.html
Timestamp: 2019-04-21 00:26:18+00:00

Document:
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.
Salles Viana Gomes de Magalhães, W. Randolph Franklin, and Ricardo dos Santos Ferreira. Fast analysis of upstream features on spatial networks (GIS Cup). In Proceedings of the 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, SIGSPATIAL '18, 622–625. New York, NY, USA, 2018. ACM. Winner (1st place). doi:10.1145/3274895.3276474.
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.
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 2-D 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 map-reduce. All these techniques also apply in 3D to CAD/CAM and additive manufacturing. Indeed they are more important there.
W. Randolph Franklin, Salles V. G. Magalhães, and Marcus V. A. Andrade. Exact fast parallel intersection of large 3-D triangular meshes (extended abstract). In 28th Annual Fall Workshop on Computational Geometry. Queens College, CUNY, New York City, 26–27 Oct 2018.
We present 3D-EPUG-Overlay, a fast, exact, parallel, memory-efficient, algorithm for computing the intersection between two large 3-D triangular meshes with geometric degeneracies. Applications include CAD/CAM, CFD, GIS, and additive manufacturing. 3D-EPUG-Overlay 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. 3D-EPUG-Overlay is up to 101 times faster than LibiGL, and comparable to QuickCSG, a parallel inexact algorithm. 3D-EPUG-Overlay is also more memory efficient. In all test cases 3D-EPUG-Overlay'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.
W. Randolph Franklin, Salles V. G. Magalhães, and Marcus V. A. Andrade. Exact fast parallel intersection of large 3-D triangular meshes. In 27th International Meshing Roundtable. Alberqueque, New Mexico, 2 Oct 2018.
We present 3D-EPUG-Overlay, a fast, exact, parallel, memory-efficient, algorithm for computing the intersection between two large 3-D triangular meshes with geometric degeneracies. Applications include CAD/CAM, CFD, GIS, and additive manufacturing. 3D-EPUG-Overlay 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. 3D-EPUG-Overlay is up to 101 times faster than LibiGL, and comparable to QuickCSG, a parallel inexact algorithm. 3D-EPUG-Overlay is also more memory efficient. In all test cases 3D-EPUG-Overlay's result matched the reference solution. It is freely available for nonprofit research and education.
W. Randolph Franklin. Applications of geometry. In Kenneth H Rosen, editor, Handbook of Discrete and Combinatorial Mathematics, Discrete Mathematics and Its Applications, chapter 13.8, pages 998–1022. CRC Press, 2nd edition, 1 Dec 2017.
Geometry overlays the entire computing spectrum, having applications in almost every area of science and engineering, including astrophysics, molecular biology, mechanical design, fluid mechanics, computer graphics, computer vision, geographic information systems, robotics, multimedia, and mechanical engineering. The growing availability of large geometric databases is a major driver of the increase in applications. GIS mapping databases containing most of the world's roads enable route planning applications. Airborne LIDAR creates terrain elevation databases. That enables observer visibility computation, with applications ranging from radio tower siting to visual nuisance mitigation. Laser scanners produce 3D point clouds recording the surfaces of objects from buildings down to sculptures and even people. The ensuing applications include deducing the structure of those objects' surfaces.
Visiting positions at Genoa, Laval, CSIRO Canberra, National University of Singapore, 1992—1993.
Visitor at Georgia Tech, 2016.

References: V. 
 V. 
 V. 
 V. 
 V. 
 V.