WRF Bibliography · W. Randolph Franklin

My publications, talks, and other public material

2026

W. Randolph Franklin. The Quantum Geometry® grand challenge: a multiyear prize and benchmark program for quantum computing in geometry, CAD, GIS, and meshing. In The 2nd ACM SIGSPATIAL International Workshop on Quantum Computing and Quantum-Inspired Technologies for Spatial Data Systems and Applications (Q-Spatial ’26). 3 Nov 2026. doi:https://doi.orrg/10.1145/3849728.3849841.
[details] [full text]
Abstract
This paper proposes the Quantum Geometry® Grand Challenge, a five-year prize and benchmark program for quantum and hybrid quantum--classical methods in computational geometry, computer-aided design (CAD), geographic information science (GIS), and meshing. The central question is where, if anywhere, quantum computation improves a complete geometric workflow. Comparisons would include data preparation, encoding, execution, and output validation. The program would begin by defining benchmarks, without requiring an initial demonstration of quantum advantage. A proposed 2027 pilot would select a small number of spatial-optimization and mesh-partitioning problems and publish classical reference solvers and independent validators. Separate award categories would recognize reproducible positive and negative findings. Two illustrative problems show how the evaluation would work. The paper sets out submission requirements, comparison metrics, judging safeguards, and a staged expansion to CAD, geometric algorithms, and data representations. Quantum Geometry® LLC would initially administer the program and offer conditional founding matching support of up to \$100,000 over five years. Expansion would depend on secured resources and independently reproducible pilot results. The contribution is a research-program design that can be tested and evaluation resources that others can reuse; it is not a claim of demonstrated quantum advantage.
BibTeX
```
@inproceedings{quantgeom-challenge-2026,
    author = "Franklin, W. Randolph",
    title = "The {Quantum Geometry®} Grand Challenge: A multiyear prize and benchmark program for quantum computing in geometry, {CAD}, {GIS}, and meshing",
    year = "2026",
    month = "3 Nov",
    booktitle = "The 2nd ACM SIGSPATIAL International Workshop on Quantum Computing and Quantum-Inspired Technologies for Spatial Data Systems and Applications (Q-Spatial ’26)",
    location = "Riverside CA USA",
    href = "\bibhrefpt{248-quantgeom-challenge-2026}{248-quantgeom-challenge-2026-talk.pdf}",
    mykey = "quantum geometry 2026 recent homepage-selected",
    doi = "https://doi.orrg/10.1145/3849728.3849841"
}
```

2024

Salles V. G. Magalhães, W. Randolph Franklin, and Marcelo Menezes. Employing GPUs to accelerate exact 3D geometric computation (poster). 5–8 March 2024. SIAM International Meshing Roundtable.
[details]

BibTeX

@misc{imr24-gpu-geom-poster-2024,
    author = "Magalhães, Salles V. G. and Franklin, W. Randolph and Menezes, Marcelo",
    title = "Employing {GPU}s to accelerate exact {3D} geometric computation (poster)",
    note = "{SIAM} International Meshing Roundtable",
    year = "2024",
    month = "5--8 March",
    href = "\bibhreftp{246-imr24-gpu-geom-slide.pdf}{246-imr24-gpu-geom-poster.pdf}",
    mykey = "recent salles parallel topology marcelo homepage-selected"
}

2022

W. Randolph Franklin and Salles Viana Gomes de Magalhães. Implementing simulation of simplicity for geometric degeneracies. In 4th ACM SIGSPATIAL International Workshop on Spatial Gems (SpatialGems 2022). 1 Nov 2022.
[details] [full text]
Abstract
We describe how to implement Simulation of Simplicity (SoS). SoS removes geometric degeneracies in point-in-polygon queries, polyhedron intersection, map overlay, and other 2D and 3D geometric and spatial algorithms by determining the effect of adding non-Archimedian infinitesimals of different orders to the coordinates. Then it modifies the geometric predicates to emulate that, and evaluates them in the usual arithmetic. A geometric degeneracy is a coincidence, such as a vertex of one polygon on an edge of another polygon, that would have probability approaching zero if the objects were distributed i.i.d. uniformly. However, in real data, they can occur often. Especially in 3D, there are too many types of degeneracies to reliably enumerate. But, if they are not handled, then predicates evaluate wrong, and the output topology may be wrong. We describe the theory of SoS, and how several algorithms and programs were successfully modified, including volume of the union of many cubes, point location in a 3D mesh, and intersecting 3D meshes.
BibTeX
```
@inproceedings{implementing-sos-2022,
    author = "Franklin, W. Randolph and de Magalhães, Salles Viana Gomes",
    title = "Implementing Simulation of Simplicity for geometric degeneracies",
    year = "2022",
    month = "1 Nov",
    booktitle = "4th {ACM SIGSPATIAL} International Workshop on Spatial Gems ({SpatialGems} 2022)",
    location = "Seattle, Washington",
    href = "\bibhref{234-implementing-sos-2022}",
    mykey = "recent salles parallel overlay homepage-selected"
}
```
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. URL: https://www.sciencedirect.com/science/article/abs/pii/S0010448522000616, doi:https://doi.org/10.1016/j.cad.2022.103285.
[details] [full text]
Abstract
This paper presents a technique for employing high-performance computing for accelerating the exact evaluation of geometric predicates. Arithmetic filters are implemented using interval arithmetic to reduce the necessity of exact arithmetic while ensuring the results of the predicates are still exact. Furthermore, the computation with interval arithmetic is offloaded to a CUDA-enabled GPU. If the GPU detects that some results cannot be trusted, the corresponding predicates are re-evaluated in parallel on the CPU using arbitrary-precision rational numbers. As a case study, a red-blue 3D triangle intersection algorithm has been implemented. Since the intervals are implemented using floating-point numbers, the parallel computing power of GPUs for processing these numbers led to a speedup of up to 1936 times (when compared against a similar sequential implementation) in the evaluation of these predicates (and up to 414 times if the entire runnning-time of the algorithm is considered). The excellent performance associated to the exactness makes this technique suitable for accelerating geometric operations in fields such as CAD, GIS and 3D modeling.
BibTeX
```
@article{marcelo-gpu-predicates-2021,
    author = "de Matos Menezes, Marcelo and Magalhães, Salles Viana Gomes and de Oliveira, Matheus Aguilar and Franklin, W. Randolph and de Oliveira Bauer Chichorro, Rodrigo Eduardo",
    editor = "Peiro, Joaquim and Shontz, Suzanne and Viertel, Ryan",
    title = "Fast parallel evaluation of exact geometric predicates on {GPU}s",
    month = "September",
    year = "2022",
    number = "103285",
    note = "Special Issue: 28th International Meshing Roundtable: Mesh Modeling for Simulations and Visualization",
    journal = "J. Computer Aided Design",
    doi = "https://doi.org/10.1016/j.cad.2022.103285",
    href = "\bibhref{239-marcelo-gpu-predicates-2021}",
    mykey = "recent salles marcelo matheus rodrigo parallel topology homepage-selected",
    url = "https://www.sciencedirect.com/science/article/abs/pii/S0010448522000616"
}
```
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. URL: https://www.spatialgems.net/.
[details] [full text]
Abstract
This paper presents a technique to use GPUs to accelerate the computation of 3D geometric predicates. A common predicate is computing the orientation of four 3D points, which is a subproblem in applications such as intersecting two 3D meshes. Since the higher level application may require billions of evaluations, efficiency is important. Accuracy is required since floating roundoff errors can cause topological impossibilities. One solution is to compute with rational numbers, but that is difficult to implement on a GPU because rationals' sizes vary. Our solution is to compute on the GPU with interval arithmetic, but fall back to using rationals on the CPU if the interval computed on the GPU includes the origin; i.e., its sign is unknown. Our experiment with a dataset of hard rock mining drill holes show that this fallback to the CPU is rarely necessary; so that our technique gave a 17 times speedup compared to a sequential implementation.
BibTeX
```
@incollection{marcelo-employing-gem-2022,
    author = "de Matos Menezes, Marcelo and de Magalhães, Salles Viana Gomes and Aguilar, Matheus and Franklin, W. Randolph and Coelho, Bruno",
    editor = "Krumm, John and Züfle, Andreas and Shahabi, Cyrus",
    title = "Employing {GPU}s to accelerate exact geometric predicates for {3D} geospatial PROCESSING",
    booktitle = "Spatial Gems",
    publisher = "ACM",
    year = "2022",
    volume = "1",
    chapter = "11",
    mykey = "recent salles marcelo matheus bruno parallel topology",
    url = "https://www.spatialgems.net/",
    href = "\bibhref{242-marcelo-employing-gem-2022}"
}
```
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. URL: https://www.spatialgems.net/.
[details] [full text]
Abstract
We present several simple representations of polygon and polyhedra that permit the efficient parallel computation of area and volume. They are particularly useful for computing the areas of the nonempty intersections between pairs of faces in two overlapping planar graphs in GIS, or the volumes of nonempty intersections between pairs of tetrahedra in two overlapping triangulations of a polyhedron in CAD. Both applications have been implemented on multicore Intel Xeons and tested on large datasets. The representations store the minimal types of information required for computation, and never need to store edge loops and face shells, or even most adjacency relations. The representations are sets of tuples or small fixed-size sets, and can be processed in parallel with map-reduce operations.
BibTeX
```
@incollection{minrep-gem-2022,
    author = "Franklin, W. Randolph and de Magalhães, Salles Viana Gomes",
    editor = "Krumm, John and Züfle, Andreas and Shahabi, Cyrus",
    title = "Minimal representations of polygons and polyhedra",
    booktitle = "Spatial Gems",
    publisher = "ACM",
    year = "2022",
    volume = "1",
    chapter = "5",
    mykey = "recent salles overlay topology",
    url = "https://www.spatialgems.net/",
    href = "\bibhref{241-minrep-gem-2022}"
}
```

W. Randolph Franklin. Quantum ECSE-4964/6964 quantum computer programming, fall 2021, rensselaer polytechnic institute. June 2022. URL: https://wrfranklin.org/nikola/Teaching/quantum-f2021/.
[details]

BibTeX

@online{quantum-course,
    author = "Franklin, W. Randolph",
    title = "Quantum {ECSE}-4964/6964 Quantum Computer Programming, Fall 2021, Rensselaer Polytechnic Institute",
    url = "https://wrfranklin.org/nikola/Teaching/quantum-f2021/",
    month = "June",
    year = "2022",
    lastaccessed = "Aug 11, 2026"
}

2021

W. Randolph Franklin, Salles Viana Gomes de Magalhães, and Eric N Landis. Fast 3-D Euclidean connected components. In John Krumm, editor, 3rd ACM SIGSPATIAL International Workshop on Spatial Gems (SpatialGems 2021). ACM, 2 Nov 2021. URL: https://www.spatialgems.net/.
[details] [full text]
Abstract
We present an efficient algorithm, with implementations, for computing the connected components within a 3-D cube of voxels, also known as the Euclidean union-find problem. There may be over $10^9$ voxels. The components may be 8-connected or 26-connected. Computing connected components has applications ranging from material failure in concrete under increasing stress to electrical conductivity in complex metal objects to elasticity in 3D printed parts. On key to efficiency is representing voxels by 1-D \emphruns of adjacent voxels. As a special case, 2-D connected components of images may easily be computed.
BibTeX
```
@incollection{connect-gem-2021,
    author = "Franklin, W. Randolph and de Magalhães, Salles Viana Gomes and Landis, Eric N",
    editor = "Krumm, John",
    title = "Fast {3-D} {Euclidean} connected components",
    booktitle = "3rd {ACM SIGSPATIAL} International Workshop on Spatial Gems (SpatialGems 2021)",
    publisher = "ACM",
    year = "2021",
    month = "2 Nov",
    location = "Beijing, China (virtual)",
    mykey = "recent salles landis connect topology 2021",
    url = "https://www.spatialgems.net/",
    href = "\bibhref{240-connect-gem-2021}"
}
```

2020

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, editor, 2nd ACM SIGSPATIAL International Workshop on Spatial Gems (SpatialGems 2020). ACM, Nov 2020. URL: https://www.spatialgems.net/.
[details] [full text]
Abstract
This paper presents a technique to use GPUs to accelerate the computation of 3D geometric predicates. A common predicate is computing the orientation of four 3D points, which is a subproblem in applications such as intersecting two 3D meshes. Since the higher level application may require billions of evaluations, efficiency is important. Accuracy is required since floating roundoff errors can cause topological impossibilities. One solution is to compute with rational numbers, but that is difficult to implement on a GPU because rationals' sizes vary. Our solution is to compute on the GPU with interval arithmetic, but fall back to using rationals on the CPU if the interval computed on the GPU includes the origin; i.e., its sign is unknown. Our experiment with a dataset of hard rock mining drill holes show that this fallback to the CPU is rarely necessary; so that our technique gave a 17 times speedup compared to a sequential implementation.
BibTeX
```
@incollection{marcelo-employing-gem-2020,
    author = "de Matos Menezes, Marcelo and de Magalhães, Salles Viana Gomes and Aguilar, Matheus and Franklin, W. Randolph and Coelho, Bruno",
    editor = "Krumm, John",
    title = "Employing {GPU}s to accelerate exact geometric predicates for {3D} geospatial PROCESSING",
    booktitle = "2nd {ACM SIGSPATIAL} International Workshop on Spatial Gems (SpatialGems 2020)",
    publisher = "ACM",
    year = "2020",
    month = "Nov",
    mykey = "salles marcelo matheus bruno parallel topology",
    url = "https://www.spatialgems.net/",
    href = "\bibhref{238-marcelo-employing-gem-2020}",
    note = "Best paper award."
}
```
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, editor, 2nd ACM SIGSPATIAL International Workshop on Spatial Gems (SpatialGems 2020). ACM, Nov 2020. URL: https://www.spatialgems.net/.
[details] [full text]
Abstract
This paper presents a technique to use GPUs to accelerate the computation of 3D geometric predicates. A common predicate is computing the orientation of four 3D points, which is a subproblem in applications such as intersecting two 3D meshes. Since the higher level application may require billions of evaluations, efficiency is important. Accuracy is required since floating roundoff errors can cause topological impossibilities. One solution is to compute with rational numbers, but that is difficult to implement on a GPU because rationals' sizes vary. Our solution is to compute on the GPU with interval arithmetic, but fall back to using rationals on the CPU if the interval computed on the GPU includes the origin; i.e., its sign is unknown. Our experiment with a dataset of hard rock mining drill holes show that this fallback to the CPU is rarely necessary; so that our technique gave a 17 times speedup compared to a sequential implementation.
BibTeX
```
@incollection{marcelo-employing-gem-2020-nonote,
    author = "de Matos Menezes, Marcelo and de Magalhães, Salles Viana Gomes and Aguilar, Matheus and Franklin, W. Randolph and Coelho, Bruno",
    editor = "Krumm, John",
    title = "Employing {GPU}s to accelerate exact geometric predicates for {3D} geospatial PROCESSING",
    booktitle = "2nd {ACM SIGSPATIAL} International Workshop on Spatial Gems (SpatialGems 2020)",
    publisher = "ACM",
    year = "2020",
    month = "Nov",
    mykey = "nonote salles marcelo matheus bruno parallel topology",
    url = "https://www.spatialgems.net/",
    href = "\bibhref{238-marcelo-employing-gem-2020}"
}
```
W. Randolph Franklin, Salles Viana Gomes de Magalhães, and Wenli Li. Siting thousands of radio transmitter towers on terrains with billions of points. 2020. arXiv 2006.16783. arXiv:2006.16783.
[details] [full text]
Abstract
This paper presents a system that sites (finds optimal locations for) thousands of radio transmitter towers on terrains of up to two billion elevation posts. Applications include cellphone towers, camera systems, or even mitigating environmental visual nuisances. The transmitters and receivers may be situated above the terrain. The system has been parallelized with OpenMP to run on a multicore CPU.
BibTeX
```
@misc{siting-thousands-2020,
    author = "Franklin, W. Randolph and de Magalhães, Salles Viana Gomes and Li, Wenli",
    title = "Siting thousands of radio transmitter towers on terrains with billions of points",
    year = "2020",
    eprint = "2006.16783",
    archivePrefix = "arXiv",
    primaryClass = "eess.SP",
    note = "arXiv 2006.16783",
    href = "\bibhref{237-siting-thousands-2020}",
    mykey = "recent salles parallel visibility visviewshedsiting wenlili homepage-selected"
}
```
Salles V. G. de Magalhães, W. Randolph Franklin, and Marcus V. A. Andrade. An efficient and exact parallel algorithm for intersecting large 3-d triangular meshes using arithmetic filters. J. Computer Aided Design, March 2020. online 2019-12-19. doi:https://doi.org/10.1016/j.cad.2019.102801.
[details] [full text]
Abstract
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 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.
BibTeX
```
@article{salles-exact-cad-2019,
    author = "de Magalhães, Salles V. G. and Franklin, W. Randolph and Andrade, Marcus V. A.",
    title = "An efficient and exact parallel algorithm for intersecting large 3-D triangular meshes using arithmetic filters",
    journal = "J. Computer Aided Design",
    note = "online 2019-12-19",
    year = "2020",
    month = "March",
    volume = "120",
    doi = "https://doi.org/10.1016/j.cad.2019.102801",
    href = "\bibhref{232-salles-exact-cad-2019}",
    mykey = "recent marcus salles parallel overlay"
}
```

2019

W. Randolph Franklin and Salles Viana Gomes de Magalhães. Minimal representations of polygons and polyhedra. In John Krumm, editor, 1st ACM SIGSPATIAL International Workshop on Spatial Gems (SpatialGems 2019). ACM, Nov 2019. URL: https://www.spatialgems.net/.
[details] [full text]
Abstract
We present several simple representations of polygon and polyhedra that permit the efficient parallel computation of area and volume. They are particularly useful for computing the areas of the nonempty intersections between pairs of faces in two overlapping planar graphs in GIS, or the volumes of nonempty intersections between pairs of tetrahedra in two overlapping triangulations of a polyhedron in CAD. Both applications have been implemented on multicore Intel Xeons and tested on large datasets. The representations store the minimal types of information required for computation, and never need to store edge loops and face shells, or even most adjacency relations. The representations are sets of tuples or small fixed-size sets, and can be processed in parallel with map-reduce operations.
BibTeX
```
@incollection{minrep-gem-2019,
    author = "Franklin, W. Randolph and de Magalhães, Salles Viana Gomes",
    editor = "Krumm, John",
    title = "Minimal representations of polygons and polyhedra",
    booktitle = "1st {ACM SIGSPATIAL} International Workshop on Spatial Gems (SpatialGems 2019)",
    publisher = "ACM",
    year = "2019",
    month = "Nov",
    mykey = "recent salles overlay topology",
    url = "https://www.spatialgems.net/",
    href = "\bibhref{236-minrep-gem-2019}"
}
```
Marcelo de Matos Menezes, Salles Viana Gomes Magalhães, W. Randolph Franklin, Matheus Aguilar de Oliveira, and Rodrigo E. O. Bauer Chichorro. Accelerating the exact evaluation of geometric predicates with GPUs. In Suzanne Shontz, Joaquim Peiró, and Ryan Viertel, editors, 28th International Meshing Roundtable. Buffalo, NY, USA, 16 Oct 2019. doi:10.5281/zenodo.3653101.
[details] [full text] [slides]
Abstract
This paper presents a technique for employing high-performance computing for accelerating the exact evaluation of geometric predicates. Arithmetic filters are implemented using interval arithmetic to reduce the necessity of exact arithmetic while ensuring the results of the predicates are still exact. Furthermore, the computation with interval arithmetic is offloaded to a CUDA-enabled GPU. If the GPU detects that some results cannot be trusted, the corresponding predicates are re-evaluated in parallel on the CPU using arbitrary-precision rational numbers. As a case study, a red-blue segment intersection algorithm has been implemented. Since the intervals are implemented using floating-point numbers, the parallel computing power of GPUs for processing these numbers led to a speedup of up to 289 times (when compared against a similar sequential implementation) in the evaluation of these predicates (and up to 40 times if the entire running-time of the algorithm is considered). The excellent performance associated to the exactness makes this technique suitable for accelerating geometric operations in fields such as CAD, GIS, VLSI design and meshing.
BibTeX
```
@inproceedings{marcelo-gpu-geometry-imr-2019,
    author = "de Matos Menezes, Marcelo and Magalhães, Salles Viana Gomes and Franklin, W. Randolph and de Oliveira, Matheus Aguilar and Chichorro, Rodrigo E. O. Bauer",
    editor = "Shontz, Suzanne and Peiró, Joaquim and Viertel, Ryan",
    title = "Accelerating the exact evaluation of geometric predicates with {GPU}s",
    booktitle = "28th International Meshing Roundtable",
    month = "16 Oct",
    address = "Buffalo, NY, USA",
    year = "2019",
    isbn = "978-1-7334890-0-3",
    doi = "10.5281/zenodo.3653101",
    href = "\bibhrefpt{235-marcelo-gpu-geometry-imr-2019}{235-marcelo-gpu-geometry-imr-2019-talk.pdf}",
    mykey = "recent salles parallel",
    customlinkslides = "https://wrfranklin.org/p/235-marcelo-gpu-geometry-imr-2019-talk.pdf"
}
```
W. Randolph Franklin and Salles V. G. de Magalhães. Computing intersection areas of overlaid 2d meshes. In IGS2019 International Geometry Summit Posters' proceedings. Vancouver, Canada, 17–21 June 2019. Solid Modeling Association.
[details] [full text] [poster] [fastforward]
Abstract
Parover2 is a parallel algorithm and preliminary implementation to compute the area of every nonempty intersection of any face of one 2D mesh with any face from another mesh over an overlapping domain. This is the hard part of cross-interpolating data from one mesh to another, for when the faces one mesh have an attribute that would be useful for the faces of the other mesh. Parover2, implemented using a map-reduce paradigm in Thrust, can quickly process millions of faces. The expected execution time is linear in the number of intersections, which is usually linear in the number of input faces. A uniform grid quickly determines the pairs of input edges that might intersect. Local topological formulae compute the areas of the output faces from the sets of their (vertex, edge) adjacencies w/o needing to compute the faces' global topologies.
BibTeX
```
@inproceedings{parover2-vancouver-2019,
    author = "Franklin, W. Randolph and de Magalhães, Salles V. G.",
    title = "Computing intersection areas of overlaid 2D meshes",
    booktitle = "{IGS2019} International Geometry Summit Posters' proceedings",
    month = "17--21 June",
    address = "Vancouver, Canada",
    year = "2019",
    publisher = "{Solid Modeling Association}",
    href = "\bibhrefpp{231-parover2-vancouver-2019}{231-parover2-vancouver-2019-poster.pdf}",
    puburl = "\url{https://igs2019.org/IGS2019-POSTER-PROCEEDINGS-LR.pdf}",
    mykey = "recent parallel salles overlay",
    customlinkposter = "https://wrfranklin.org/p/231-parover2-vancouver-2019-poster.pdf",
    customlinkfastforward = "https://wrfranklin.org/p/231-parover2-vancouver-2019-ff.mp4"
}
```

2018

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:https://doi.org/10.1145/3274895.3276474.
[details] [full text] [slides]

Abstract

We present a fast linear time algorithm that uses a block-cut tree for identifying upstream features from a set of starting points in a network. Our implementation has been parallelized and it can process a dataset with 32 million features in less than 8 seconds on a 8-core workstation. This problem is the 2018 ACM SIGSPATIAL CUP challenge and presents several applications mainly on the field of utility networks. Our code is freely available for nonprofit research and education at https://github.com/sallesviana/FastUpstream

BibTeX

@inproceedings{salles-giscup-2018,
    author = "de Magalhães, Salles Viana Gomes and Franklin, W. Randolph and dos Santos Ferreira, Ricardo",
    title = "Fast Analysis of Upstream Features on Spatial Networks {(GIS Cup)}",
    note = "Winner (1st place)",
    booktitle = "Proceedings of the 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems",
    series = "SIGSPATIAL '18",
    year = "2018",
    isbn = "978-1-4503-5889-7",
    location = "Seattle, Washington",
    pages = "622--625",
    numpages = "4",
    acmid = "3276474",
    publisher = "ACM",
    address = "New York, NY, USA",
    keywords = "GISCUP, graph algorithms, parallel programming, spatial networks",
    href = "\bibhrefpt{228-salles-giscup-2018}{228-salles-giscup-2018-talk.pdf}",
    customlinkslides = "https://wrfranklin.org/p/228-salles-giscup-2018-talk.pdf",
    mykey = "recent salles parallel sallesgiscup2018",
    doi = "https://doi.org/10.1145/3274895.3276474"
}

W. Randolph Franklin, Salles V. G. de 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.
[details] [full text] [slides]
Abstract
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.
BibTeX
```
@inproceedings{par-ds-bigspatial-2018,
    author = "Franklin, W. Randolph and de 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{227-par-ds-bigspatial-2018}{227-par-ds-bigspatial-2018-talk.pdf}",
    customlinkslides = "https://wrfranklin.org/p/227-par-ds-bigspatial-2018-talk.pdf",
    mykey = "recent marcus salles topology parallel"
}
```
W. Randolph Franklin, Salles V. G. de 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.
[details] [full text]
Abstract
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.
BibTeX
```
@inproceedings{exact-fast-parallel-fwcg-2018,
    author = "Franklin, W. Randolph and de 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 = "26--27 Oct",
    href = "\bibhref{229-exact-fast-parallel-fwcg-2018}",
    mykey = "recent marcus salles overlay parallel topology"
}
```
W. Randolph Franklin, Salles V. G. de Magalhães, and Marcus V. A. Andrade. Exact fast parallel intersection of large 3-D triangular meshes. In 27th International Meshing Roundtable. Albuquerque, New Mexico, 2 Oct 2018.
[details] [full text] [slides]
Abstract
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.
BibTeX
```
@inproceedings{exact-fast-parallel-imr-2018,
    author = "Franklin, W. Randolph and de 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 = "Albuquerque, New Mexico",
    year = "2018",
    month = "2 Oct",
    href = "\bibhrefpt{222-exact-fast-parallel-imr-2018}{222-exact-fast-parallel-imr-2018-talk.pdf}",
    mykey = "recent marcus salles overlay parallel",
    customlinkslides = "https://wrfranklin.org/p/222-exact-fast-parallel-imr-2018-talk.pdf"
}
```
W. Randolph Franklin and Carlos Varela. Intelligent cognitive assistant for emergency landings using gpu geometric computing and online statistical reasoning. unpublished, 2018.
[details] [full text]
Abstract
This white paper will describe a new capability (powerful GPUs and massive memory), and then an important new use case (an intelligent cognitive assistant for emergency landings using GPU geometric computing and online statistical reasoning).
BibTeX
```
@unpublished{intell-cog-asst-2018,
    author = "Franklin, W. Randolph and Varela, Carlos",
    title = "Intelligent Cognitive Assistant for Emergency Landings using GPU Geometric Computing and Online Statistical Reasoning",
    year = "2018",
    note = "unpublished",
    href = "\bibhref{226-intell-cog-asst-2018}"
}
```

2017

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.
[details] [full text]
Abstract
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.
BibTeX
```
@incollection{handbook-geoapps-2017,
    author = "Franklin, W. Randolph",
    editor = "Rosen, Kenneth H",
    title = "Applications of Geometry",
    booktitle = "Handbook of Discrete and Combinatorial Mathematics",
    edition = "2nd",
    series = "Discrete Mathematics and Its Applications",
    pages = "998--1022",
    publisher = "{CRC} Press",
    year = "2017",
    month = "1 Dec",
    chapter = "13.8",
    mykey = "recent",
    isbn = "9781584887805",
    href = "\bibhref{230-handbook-geoapps-2017}",
    puburl = "https://www.crcpress.com/Handbook-of-Discrete-and-Combinatorial-Mathematics-Second-Edition/Rosen/p/book/9781584887805"
}
```
W. Randolph Franklin and Salles V. G. de Magalhães. Parallel intersection detection in massive sets of cubes. In 27th Fall Workshop on Computational Geometry. Stony Brook University, New York, USA, 3–4 Nov 2017. (talk).
[details] [slides]
Abstract
We present ParCube, a very fast parallel algorithm and implementation for finding the pairwise intersections in a set of millions of congruent cubes. This operation is required when computing boolean combinations of meshes or polyhedra in CAD/CAM and additive manufacturing, and in determining close points in a 3D set. ParCube expresses a 3D uniform grid using functional programming concepts in Nvidia Thrust. The underlying HW can be either regular single-threaded C++, an Nvidia GPU with CUDA, or a multicore Intel Xeon with OpenMP or TBB. ParCube can intersect 10M i.i.d. cubes with 6M intersections in 0.32 elapsed seconds, which is 131x faster than CGAL. Even running single threaded on the CPU, ParCube ran this case three times as fast as CGAL. ParCube can also find bipartite intersections without expensive preprocessing.
BibTeX
```
@inproceedings{parcube-fwcg-2017,
    author = "Franklin, W. Randolph and de Magalhães, Salles V. G.",
    title = "Parallel intersection detection in massive sets of cubes",
    booktitle = "27th Fall Workshop on Computational Geometry",
    year = "2017",
    month = "3--4 Nov",
    address = "{Stony Brook University, New York, USA}",
    note = "(talk)",
    href = "\bibhrefat{225-parcube-fwcg-2017-abs}{225-parcube-fwcg-2017-talk.pdf}",
    mykey = "salles parcube parallel",
    customlinkslides = "https://wrfranklin.org/p/225-parcube-fwcg-2017-talk.pdf"
}
```
W. Randolph Franklin and Salles V. G. de 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. doi:https://doi.org/10.1145/3150919.3150921.
[details] [full text] [slides]
Abstract
We present ParCube, which finds the pairwise intersections in a set of millions of congruent cubes. This operation is required when computing boolean combinations of meshes or polyhedra in CAD/CAM and additive manufacturing, and in determining close points in a 3D set. ParCube is very compact because it is uses a uniform grid with a functional programming API. ParCube is very fast; even single threaded it usually beats CGAL's elapsed time, sometimes by a factor of 3. Also because it is FP, ParCube parallelizes very well. On an Nvidia GPU, processing 10M cubes to find 6M intersections, it took 0.33 elapsed seconds, beating CGAL by a factor of 131. ParCube is independent of the specific parallel architecture, whether shared memory multicore Intel Xeon using either OpenMP or TBB, or Nvidia GPUs with thousands of cores. We expect the principles used in ParCube to apply to other computational geometry problems. Efficiently finding all bipartite intersections would be an easy extension.
BibTeX
```
@inproceedings{parcube-bigspatial-2017,
    author = "Franklin, W. Randolph and de Magalhães, Salles V. G.",
    title = "Parallel intersection detection in massive sets of cubes",
    booktitle = "Proceedings of {BigSpatial'17}: 6th {ACM SIGSPATIAL} Workshop on Analytics for Big Geospatial Data",
    year = "2017",
    month = "7-10 Nov",
    address = "{Los Angeles Area, CA, USA}",
    doi = "https://doi.org/10.1145/3150919.3150921",
    href = "\bibhrefpt{224-parcube-bigspatial-2017}{224-parcube-bigspatial-2017-talk.pdf}",
    mykey = "parcube salles parallel",
    customlinkslides = "https://wrfranklin.org/p/224-parcube-bigspatial-2017-talk.pdf"
}
```
Salles V. G. de 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.
[details] [full text] [slides]
Abstract
We present an algorithm to compute the intersection of two 3D triangulated meshes. It has applications in GIS, CAD and Additive Manufacturing, and was developed to process big datasets quickly and correctly. The speed comes from simple regular data structures that parallelize very well. The correctness comes from using multiple-precision rational arithmetic to prevent roundoff errors and the resulting topological inconsistencies, and symbolic perturbation (simulation of simplicity) to handle special cases (geometric degeneracies). To simplify the symbolic perturbation, the algorithm employs only orientation predicates. This paper focuses on the challenges and solutions of the implementing symbolic perturbation. Our preliminary implementation has intersected two objects totalling 8M triangles in 11 elapsed seconds on a dual 8-core Xeon. The competing LibiGL took 248 seconds and CGAL took 2726 seconds. Our software is freely available for nonprofit research.
BibTeX
```
@inproceedings{salles-parallel-mesh-sigspatial-2017,
    author = "de Magalhães, Salles V. G. and Franklin, W. Randolph and Andrade, Marcus V. A.",
    title = "Fast exact parallel {3D} mesh intersection algorithm using only orientation predicates",
    year = "2017",
    month = "7--10 Nov",
    booktitle = "25th {ACM SIGSPATIAL} International Conference on Advances in Geographic Information Systems {(ACM SIGSPATIAL 2017)}",
    address = "{Los Angeles Area, CA, USA}",
    href = "\bibhrefpt{223-salles-parallel-mesh-sigspatial-2017}{223-salles-parallel-mesh-sigspatial-2017-talk.pdf}",
    mykey = "salles marcus parallel",
    customlinkslides = "https://wrfranklin.org/p/223-salles-parallel-mesh-sigspatial-2017-talk.pdf"
}
```
W. Randolph Franklin, Salles V. G. de Magalhães, and Marcus V. A. Andrade. 3D-EPUG-Overlay: intersecting very large 3D triangulations in parallel. In 2017 SIAM conference on industrial and applied geometry. Pittsburgh PA USA, 10–12 July 2017. (talk).
[details] [slides]
Abstract
We present 3D-EPUG-Overlay, an algorithm and preliminary implementation for intersecting (aka overlaying) two 3D triangulations. This operation is important in processing large geometry datasets in additive manufacturing. Much of our algorithm is a sequence of map-reduce operations, and so is easily parallelizable. We completely avoid roundoff errors and the associated topological problems by computing with rational numbers. We will handle geometric degeneracies with Simulation of Simplicity (SoS). Our target architecture is an inexpensive workstation. We have a complete 2D implementation, which has overlaid two 2D maps maps, with a total of 54,000,000 vertices and 739,000 faces, in only 322 elapsed seconds (excluding I/O) on a dual 8-core 3.4GHz Intel Xeon workstation. That time is using 16 cores, and is 11x faster than using one core. Our 3D implementation is complete except for SoS. It processes two 3D objects with a total of 6,000,000 face triangles and 3,000,000 tetrahedra in 180 elapsed seconds on 16 cores. The parallel speedup for 16 cores is a factor of 13. The execution time is almost linear in the data size, and could process much larger datasets, perhaps billions of triangles. We anticipate being able to process much larger datasets than competing SW can, and for datasets small enough for others to process, that we will be much faster and more robust on special cases.
BibTeX
```
@inproceedings{x3d-epug-siam-2017,
    author = "Franklin, W. Randolph and de Magalhães, Salles V. G. and Andrade, Marcus V. A.",
    title = "{3D-EPUG-Overlay}: Intersecting very large {3D} triangulations in parallel",
    booktitle = "2017 {SIAM} conference on industrial and applied geometry",
    year = "2017",
    month = "10--12 July",
    address = "Pittsburgh PA USA",
    note = "(talk)",
    href = "\bibhrefat{219-3d-epug-siam-2017-abs}{219-3d-epug-siam-2017.pdf}",
    mykey = "overlay parallel marcus salles epug-overlay",
    customlinkslides = "https://wrfranklin.org/p/219-3d-epug-siam-2017.pdf"
}
```
W. Randolph Franklin, Salles V. G. de Magalhães, and Marcus V. A. Andrade. An exact and efficient 3D mesh intersection algorithm using only orientation predicates. In S3PM-2017: International Convention on Shape, Solid, Structure, & Physical Modeling, Shape Modeling International (SMI-2017) Symposium. Berkeley, California, USA, 19–23 June 2017. (poster).
[details] [poster]
Abstract
We present an algorithm to compute the intersection of two 3D triangulated meshes. It has applications in CAD and Additive Manufacturing, and was developed to process the largest datasets quickly and correctly. The speed comes from simple regular data structures that parallelize very well. The correctness comes from using multiple-precision rational arithmetic to prevent roundoff errors and the resulting topological inconsistencies, and symbolic perturbation (simulation of simplicity) to handle special cases (geometric degeneracies). To simplify the symbolic perturbation, the algorithm employs only orientation predicates. This paper focuses on the challenges and solutions of the implementing symbolic perturbation.
BibTeX
```
@inproceedings{mesh-orientation-s3pm-2017,
    author = "Franklin, W. Randolph and de Magalhães, Salles V. G. and Andrade, Marcus V. A.",
    title = "An exact and efficient {3D} mesh intersection algorithm using only orientation predicates",
    booktitle = "{S3PM-2017}: International Convention on Shape, Solid, Structure, \\& Physical Modeling, Shape Modeling International {(SMI-2017)} Symposium",
    month = "19--23 June",
    address = "Berkeley, California, USA",
    host = "International Computer Science Institute",
    year = "2017",
    note = "(poster)",
    href = "\bibhrefap{}{220-mesh-orientation-s3pm-2017.pdf}",
    mykey = "parallel marcus salles overlay epug-overlay",
    customlinkposter = "https://wrfranklin.org/p/220-mesh-orientation-s3pm-2017.pdf"
}
```
Wenli Li and W. Randolph Franklin. GPU–accelerated multiple observer siting. Photogrammetric Engineering & Remote Sensing, 83(6):439–446, June 2017. doi:https://doi.org/10.14358/PERS.83.6.439.
[details] [full text]
Abstract
We present two fast parallel implementations of the Franklin-Vogt multiple observer siting algorithm, using either OpenMP or CUDA. In this problem, the objective is to site observers on a raster terrain such that the joint area visible by them is maximized. On a terrain with 16385×16385 cells, assuming that observers can see out to a radius-of-interest of 100 cells, finding the approximately 15000 observers that have the greatest coverage takes only 17s in CUDA. That is a factor of 70 speedup from the sequential version. The OpenMP version exhibits a factor of 17 speedup on a 16 core system. Applications for the multiple observer siting problem include radio transmission towers, environmental monitoring sites, and path planning for surveillance drones. The algorithm has four steps: finding the visibility indices of all points, selecting a candidate subset of potential top observers, finding each one's viewshed, and greedily constructing the final solution.
BibTeX
```
@article{wenli-gpu-siting-2016,
    author = "Li, Wenli and Franklin, W. Randolph",
    title = "{GPU}--Accelerated Multiple Observer Siting",
    journal = "Photogrammetric Engineering \\& Remote Sensing",
    year = "2017",
    month = "June",
    volume = "83",
    number = "6",
    pages = "439--446",
    href = "\bibhref{213-wenli-gpu-siting-2016}",
    doi = "https://doi.org/10.14358/PERS.83.6.439",
    mykey = "wenlili visviewshedsiting gpusiting parallel"
}
```

2016

Maurício Gouvêa Gruppi, Salles V. G. de Magalhães, Marcus V. A. Andrade, W. Randolph Franklin, and Wenli Li. Using rational numbers and parallel computing to efficiently avoid round-off errors on map simplification. RBC. Revista Brasileira de Cartografia (Online), 68:1221–1230, 2016. online at \url http://www.lsie.unb.br/rbc/index.php/rbc/article/view/1857.
[details] [full text]
Abstract
This paper presents EPLSimp, an algorithm for map generalization that avoids the creation of topological inconsistencies. EPLSimp is based on Visvalingam-Whyatt's (VW) algorithm on which least “important” points are removed first. Unlike VW's algorithm, when a point is deleted a verification is performed in order to check if this deletion would create topological inconsistencies. This was done by using arbitrary precision rational numbers to completely avoid errors caused by floating-point arithmetic. EPLSimp was carefully implemented to be efficient, although using rational numbers adds an overhead to the computation. This efficiency was achieved by using a uniform grid for indexing the geometric data and parallel computing to speed up the process. As result, simplified models completely free of topologically inconsistent results and round-off errors due to the use of multiple precision rational numbers. In addition, there was a considerable speedup arising from the use of parallel computing.
BibTeX
```
@article{mauricio-rational-rbc-2016,
    author = "Gruppi, Maurício Gouvêa and de Magalhães, Salles V. G. and Andrade, Marcus V. A. and Franklin, W. Randolph and Li, Wenli",
    title = "Using Rational Numbers and Parallel Computing to Efficiently Avoid Round-Off Errors on Map Simplification",
    journal = "RBC. Revista Brasileira de Cartografia (Online)",
    year = "2016",
    volume = "68",
    pages = "1221-1230",
    note = "online at \url{http://www.lsie.unb.br/rbc/index.php/rbc/article/view/1857}",
    href = "\bibhref{221-mauricio-rational-rbc-2016}",
    mykey = "wenlili marcus salles parallel"
}
```

W. Randolph Franklin. Efficient parallel GIS and CAD operations on very large data sets. 31 Oct 2016. Invited keynote talk at ACM SIGSPATIAL GIS PhD Workshop.
[details] [slides]

BibTeX

@misc{efficient-large-acmgis-2016,
    author = "Franklin, W. Randolph",
    title = "Efficient parallel {GIS} and {CAD} operations on very large data sets",
    month = "31 Oct",
    year = "2016",
    note = "Invited keynote talk at ACM SIGSPATIAL GIS PhD Workshop",
    href = "\bibhreft{218-efficient-large-acmgis-2016.pdf}",
    customlinkslides = "https://wrfranklin.org/p/218-efficient-large-acmgis-2016.pdf",
    mykey = "parallel"
}

Salles V. G. de Magalhães, Marcus V. A. Andrade, W. Randolph Franklin, Wenli Li, and Maurício Gouvêa Gruppi. Exact intersection of 3D geometric models. In Geoinfo 2016, XVII Brazilian Symposium on GeoInformatics. Campos do Jordão, SP, Brazil, November 2016. Instituto Nacional de Pesquisas Espaciais (Brasil).
[details] [full text] [slides]
Abstract
This paper presents 3D-EPUG-OVERLAY , an exact and parallel algorithm for computing the intersection of 3D triangulated meshes, a problem with applications in several fields such as GIS and CAD. 3D-EPUG-OVERLAY presents several innovations: it employs exact arithmetic and, thus, the computations are completely exact, which avoids topological impossibilities that are often created by floating point arithmetic. Also, it uses a uniform grid to index the geometric data and was designed to be easily parallelizable. Furthermore, we propose the use of Simulation of Simplicity to effectively ensure that all the special cases are properly handled by the algorithm.
BibTeX
```
@inproceedings{salles-xsect-3d-geoinfo-2016,
    author = "de Magalhães, Salles V. G. and Andrade, Marcus V. A. and Franklin, W. Randolph and Li, Wenli and Gruppi, Maurício Gouvêa",
    title = "Exact intersection of {3D} geometric models",
    booktitle = "Geoinfo 2016, {XVII Brazilian} Symposium on GeoInformatics",
    year = "2016",
    month = "November",
    address = "Campos do Jordão, SP, Brazil",
    puburl = "\url{http://www.geoinfo.info/geoinfo\_series.htm}",
    publisher = "Instituto Nacional de Pesquisas Espaciais (Brasil)",
    mykey = "wenlili marcus salles parallel overlay epug-overlay",
    href = "\bibhrefpt{217-salles-xsect-3d-geoinfo-2016}{217-salles-xsect-3d-geoinfo-2016-talk.pdf}",
    customlinkslides = "https://wrfranklin.org/p/217-salles-xsect-3d-geoinfo-2016-talk.pdf"
}
```

Wenli Li, W. Randolph Franklin, and Salles V. G. de Magalhães. Computing approximate horizons on a GPU. In 26th Fall Workshop on Computational Geometry. CUNY Graduate Center, New York, USA, 27-28 Oct 2016. (extended abstract).
[details] [full text] [slides]

Abstract

We use an O(n log(n)) quadtree-forest algorithm to compute approximate horizons at all points of a DEM, and achieve more than 30 times speedup on a GPU. The result of the algorithm is very close to that of the brute-force algorithm.

BibTeX

@inproceedings{wenli-gpu-horizons-fwcg-2016,
    author = "Li, Wenli and Franklin, W. Randolph and de Magalhães, Salles V. G.",
    title = "Computing approximate horizons on a {GPU}",
    booktitle = "26th Fall Workshop on Computational Geometry",
    year = "2016",
    month = "27-28 Oct",
    address = "{CUNY} Graduate Center, New York, USA",
    note = "(extended abstract)",
    href = "\bibhrefpt{216-wenli-gpu-horizons-fwcg-2016}{216-wenli-gpu-horizons-fwcg-2016-talk.pdf}",
    customlinkslides = "https://wrfranklin.org/p/216-wenli-gpu-horizons-fwcg-2016-talk.pdf",
    mykey = "visviewshedsiting wenlili salles"
}

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).
[details] [full text] [slides]
Abstract
We present an efficient parallel algorithm for performing spatio-temporal analysis in a Spark cluster. It divides the spatio-temporal cube into partitions and uses these partitions as the elements of the Spark Resilient Distributed Datasets (RDDs). As a result, data presents a better locality and the overheads are smaller than the overheads observed when single cells are used as elements of the RDDs. When used to find hotspots in the NYC Yellowcab data, our algorithm is up to 52 times faster than algorithms using single cells RDDs.
BibTeX
```
@inproceedings{salles-giscup-2016,
    author = "de Magalhães, Salles Viana Gomes and Franklin, W. Randolph and Li, Wenli and Andrade, Marcus Vinicius Alvim",
    title = "An efficient map-reduce algorithm for spatio-temporal analysis using Spark ({GIS Cup})",
    note = "Winner (2nd place)",
    booktitle = "5th {GIS}-focused algorithm competition, {GISCup} 2016, co-located with {ACM SIGSPATIAL GIS}",
    year = "2016",
    href = "\bibhrefpt{215-salles-giscup-2016}{215-salles-giscup-2016-talk.pdf}",
    customlinkslides = "https://wrfranklin.org/p/215-salles-giscup-2016-talk.pdf",
    mykey = "marcus wenlili salles parallel sallesgiscup2016"
}
```
Wenli Li, W. Randolph Franklin, Salles V. G. de Magalhães, Marcus V. A. Andrade, and David L. Hedin. 3D segmented ODETLAP compression. 2016.
[details] [full text]
Abstract
We propose a segmented ODETLAP compression algorithm to increase speed, and show that it is usually better in the maximum absolute error than JP3D for 3D datasets. Overdetermined Laplacian partial differential equations (ODETLAP) is a spatial approximation and data compression method. We use the CUSP library to accelerate ODETLAP approximation and the speedup is about 7 times on a GPU over a CPU core. Segmented ODETLAP compression is faster and uses less memory than unsegmented ODETLAP compression. We use the algorithm to compress several atmospheric datasets and an MRI dataset. For evaluation, we also compress the datasets using JPEG 2000 Part 10 JP3D. The results show that the compressed size of the algorithm is about 60\% that of JP3D for the same maximum absolute error.
BibTeX
```
@misc{wenli-odetlap-2016,
    author = "Li, Wenli and Franklin, W. Randolph and de Magalhães, Salles V. G. and Andrade, Marcus V. A. and Hedin, David L.",
    title = "{3D} Segmented {ODETLAP} Compression",
    booktitle = "(unpublished)",
    year = "2016",
    href = "\bibhref{212-wenli-odetlap-2016}",
    mykey = "wenlili marcus salles odetlap"
}
```
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, August 2016.
[details] [full text] [slides]
Abstract
We present NearptD, a very fast parallel nearest neighbor algorithm and implementation, which has processed 10M points in E6 and 184M6 points in E3. It uses 1/5 the space and as little as 1/100 the preprocessing time FLANN (a well-known approximate nearest neighbor 4program). Up to E4, its query time is also faster, by up to a factor of 100. NearptD uses Nvidia Thrust and CUDA in C++ to perform parallel preprocessing and querying of large point cloud data. Nearest neighbor searching is needed by many applications, such as collision detection, computer vision or machine learning. This implementation is an extension of the Nearpt3 algorithm performed in parallel on the GPU for a variable number of dimensions. NearptD shows that a uniform grid can outperform a kd-tree for preprocessing and searching large datasets.
BibTeX
```
@inproceedings{hedin-nearptd-2016,
    author = "Hedin, David and Franklin, W. Randolph",
    title = "NearptD: A Parallel Implementation of Exact Nearest Neighbor Search using a Uniform Grid",
    booktitle = "Canadian Conference on Computational Geometry",
    year = "2016",
    month = "August",
    address = "Vancouver Canada",
    href = "\bibhrefpt{211-hedin-nearptd-2016}{211-hedin-nearptd-2016-talk.pdf}",
    customlinkslides = "https://wrfranklin.org/p/211-hedin-nearptd-2016-talk.pdf",
    mykey = "nearpt parallel"
}
```
W. Randolph Franklin. Minimum spatial representations. 2016. (unpublished).
[details] [full text]
Abstract
This paper argues for representing geometric objects like polygons and planar graphs (maps) using no global topology, and using only the minimal local topology. Good representations include the set of directed labeled edges, and the set of vertex-edge incidences. Operations such as unions and intersections are easier to implement, are very fast, and parallelize.
BibTeX
```
@misc{minspatial-2016,
    author = "Franklin, W. Randolph",
    title = "Minimum spatial representations",
    note = "(unpublished)",
    year = "2016",
    href = "\bibhref{210-minspatial-2016}"
}
```
Salles V. G. de 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, August 2016. (online 17 May). Awarded a reproducibility stamp, \url http://www.reproducibilitystamp.com/. URL: http://www.sciencedirect.com/science/article/pii/S0097849316300607, doi:https://doi.org/10.1016/j.cag.2016.05.017.
[details] [full text] [slides]
Abstract
This paper presents PinMesh, a very fast algorithm with implementation to preprocess a polyhedral mesh, also known as a multimaterial mesh, in order to perform 3D point location queries. PinMesh combines several innovative components to efficiently handle the largest available meshes. Because of a 2-level uniform grid, the expected preprocessing time is linear in the input size, and the code parallelizes well on a shared memory machine. Querying time is almost independent of the dataset size. PinMesh uses exact arithmetic with rational numbers to prevent roundoff errors, and symbolic perturbation with Simulation of Simplicity (SoS) to handle geometric degeneracies or special cases. PinMesh is intended to be a subroutine in more complex algorithms. It can preprocess a dataset and perform 1 million queries up to 27 times faster than RCT (Relative Closest Triangle), the current fastest algorithm. Preprocessing a sample dataset with 50 million triangles took only 14 elapsed seconds on a 16-core Xeon processor. The mean query time was 0.6 microseconds.
BibTeX
```
@article{salles-pinmesh-smi-2016,
    author = "de Magalhães, Salles V. G. and Andrade, Marcus V. A. and Franklin, W. Randolph and Li, Wenli",
    title = "{PinMesh} -- {Fast} and exact {3D} point location queries using a uniform grid",
    journal = "{Computer \\& Graphics Journal}, special issue on {Shape Modeling International} 2016",
    year = "2016",
    volume = "58",
    pages = "1--11",
    month = "August",
    doi = "https://doi.org/10.1016/j.cag.2016.05.017",
    url = "http://www.sciencedirect.com/science/article/pii/S0097849316300607",
    href = "\bibhrefpt{209-salles-smi-pinmesh-2016}{209-salles-smi-pinmesh-2016-talk.pptx}",
    note = "(online 17 May). Awarded a reproducibility stamp, \url{http://www.reproducibilitystamp.com/}.",
    customlinkslides = "https://wrfranklin.org/p/209-salles-smi-pinmesh-2016-talk.pptx",
    mykey = "salles marcus wenlili pinmesh parallel sallespinmeshsmi2016"
}
```
Chaulio R. Ferreira, Marcus V. A. Andrade, Salles V. G. de Magalhães, and W. Randolph Franklin. An efficient external memory algorithm for terrain viewshed computation. ACM Trans. on Spatial Algorithms and Systems, 2016. doi:https://doi.org/10.1145/2903206.
[details] [full text]
Abstract
This paper presents TiledVS, a fast external algorithm and implementation for computing viewsheds. TiledVS is intended for terrains that are too large for internal memory, even over 100 000 × 100 000 points. It subdivides the terrain into tiles that are stored compressed on disk and then paged into memory with a custom cache data structure and LRU algorithm. If there is sufficient available memory to store a whole row of tiles, which is easy, then this specialized data management is faster than relying on the operating system's virtual memory management. Applications of viewshed computation include siting radio transmitters, surveillance, and visual environmental impact measurement. TiledVS runs a rotating line of sight from the observer to points on the region boundary. For each boundary point, it computes the visibility of all the terrain points close to the line of sight. The running time is linear in the number of points. No terrain tile is read more than twice. TiledVS is very fast, for instance, processing a 104000 x 104000 terrain on a modest computer with only 512MB of RAM took only 1 2 1 hours. On large datasets, TiledVS was several times faster than competing algorithms such as the ones included in GRASS. The source code of TiledVS is freely available for nonprofit researchers to study, use, and extend. A preliminary version of this algorithm appeared in a 4-page ACM SIGSPATIAL GIS 2012 conference paper “More efficient terrain viewshed computation on massive datasets using external memory”. This more detailed version adds the fast lossless compression stage that reduces the time by 30\% to 40\%, and many more experiments and comparisons.
BibTeX
```
@article{chaulio-tiledvs-tsas-2016,
    author = "Ferreira, Chaulio R. and Andrade, Marcus V. A. and de Magalhães, Salles V. G. and Franklin, W. Randolph",
    title = "An efficient external memory algorithm for terrain viewshed computation",
    href = "\bibhref{197-chaulio-tiledvs-tsas-2016}",
    journal = "{ACM} Trans. on Spatial Algorithms and Systems",
    year = "2016",
    volume = "2",
    number = "2",
    doi = "https://doi.org/10.1145/2903206",
    mykey = "salles marcus visviewshedsiting tiledvs visibility"
}
```

W. Randolph Franklin and Salles Viana Gomes de Magalhães. Local topology and parallel overlaying large planar graphs. 15 Feb 2016. Talk at Georgia Tech, School of Interactive Computing. Also given at IBM Haifa, Microsoft Haifa, Ben Gurion U, and Tel Aviv U in Dec 2015.
[details] [slides]

BibTeX

@misc{local-talk-gatech-2016,
    author = "Franklin, W. Randolph and de Magalhães, Salles Viana Gomes",
    title = "Local topology and parallel overlaying large planar graphs",
    note = "Talk at Georgia Tech, School of Interactive Computing. Also given at IBM Haifa, Microsoft Haifa, Ben Gurion U, and Tel Aviv U in Dec 2015",
    month = "15 Feb",
    year = "2016",
    href = "\bibhreft{208-local-talk-gatech-2016.pdf}",
    customlinkslides = "https://wrfranklin.org/p/208-local-talk-gatech-2016.pdf",
    mykey = "salles overlay topology parallel"
}

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, editors, Advancing Geographic Information Science: The Past and Next Twenty Years, chapter 1, pages 9–34. GSDI association press, 2016.
[details] [full text]
Abstract
This paper summarizes the discussions related to the panel “Contributions of GIScientists (or GIScience) over the past Twenty Years” at the 2015 Vespucci Institute. Reflections about the past not only provide an account of what occurred, but also may serveas a basis for comparison when in the future somehow related scenarios arise. Such histories may be detailed enumerations of chronological events or, more analytically, analyses of interactions that enabled or caused specific developments. The purpose of this paper is to account for some key developments in the academic field of geographic information science over the past twenty years (i.e., since 1995) and to assess some of the impact of these developments. The panel in Bar Harbor, moderated by David Coleman, included two invited presentations (by Max Egenhofer and Keith Clarke), and responses by two early career panelists (Song Gao and Teriitutea Quesnot), and by two senior panelists (Randolph Franklin and May Yuan).Keywords: Emergence of GIScience; short recent history; outlets of GIScience research; publication ranking; selected highlights of GIScience research; contributions to other disciplines; research topics that have disappeared; recently emerging topics.
BibTeX
```
@incollection{egenhofer-advancing-2016,
    author = "Egenhofer, Max J and Clarke, Keith C and Gao, Song and Quesnot, Teriitutea and Franklin, W. Randolph and Yuan, May and Coleman, David",
    editor = "Onsrud, Harlan and Kuhn, Werner",
    title = "Contributions of {GIScience} over the Past Twenty Years",
    booktitle = "Advancing Geographic Information Science: The Past and Next Twenty Years",
    publisher = "{GSDI} association press",
    year = "2016",
    chapter = "1",
    pages = "9--34",
    isbn = "978-0-9852444-4-6",
    mykey = "visviewshedsiting",
    href = "\bibhref{206-egenhofer-advancing-maine-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, May 2016. doi:https://doi.org/10.1520/GTJ20140226.
[details] [full text]
Abstract
The objective of this research is to develop tools that would improve the understanding of the process of levee failure because of erosion and reduce the risk of failure. Hydraulic erosion is a complicated phenomenon and depends on many different parameters. To improve design criteria for levees, embankments, and earthen structures, the development of realistic computer models that can simulate the erosion process is necessary. Verification of these computer simulations, as with any simulation, is a necessity. In this research, a large number of physical levee erosion tests were performed at 1g and at high g's using a geotechnical centrifuge. Centrifuge tests were performed to simulate real (prototype) size levees, and thus to obtain a more realistic model. The erosion was modeled physically in detail. Conventional three-dimensional scanning was used to precisely verify the calculated dimensions of initial and final computer model geometries, but did not yield interim data or measurements of the quantity of eroded soil during the tests. A Kinect device was used to scan and evaluate the volume of eroded soil and variation of the shape of the channels as a function of time. Three-dimensional images were obtained, and variations of different parameters were plotted. Various quantities were measured as a function of time. Based on recorded videos and pictures taken during the tests, it was discovered that the Kinect results agreed well with the physical models. The Kinect is a low-cost sensor, and enables the measurement of the rate of soil erosion, which, if done at all, usually requires expensive equipment. The Kinect device was also used in the centrifuge experiments, and functioned well in the high genvironment. It is believed to be the first use of a Kinect device in a centrifuge. The application of this method in other laboratory experiments was also investigated.
BibTeX
```
@article{kamalzare-gtj-2016,
    author = "Kamalzare, Mehrad and Zimmie, Thomas F. and Cutler, Barbara and Franklin, W. Randolph",
    title = "A New Visualization Method to Evaluate Sediment Transport and Erosion",
    journal = "Geotechnical Testing Journal",
    year = "2016",
    volume = "39",
    number = "3",
    month = "May",
    href = "\bibhref{189-kamalzare-gtj2014-kinect}",
    doi = "https://doi.org/10.1520/GTJ20140226",
    mykey = "levee"
}
```

2015

Mauricio G. Gruppi, Salles V. G. de Magalhães, Marcus V. A. Andrade, W. Randolph Franklin, and Wenli Li. An efficient and topologically correct map generalization heuristic. In Proceedings of the 17th International Conference on Enterprise Information Systems (ICEIS), 516–525, paper 236. 2015. URL: http://www.iceis.org/Abstracts/2015/ICEIS_2015_Abstracts.htm, doi:https://doi.org/10.5220/0005398105160525.
[details] [full text]
Abstract
We present TopoVW, an efficient heuristic for map simplification that deals with a variation of the generalization problem where the idea is to simplify the polylines of a map without changing the topological relationships between these polylines or between the lines and control points. This process is important for maintaining clarity of cartographic data, avoiding situations such as high density of map features, inappropriate intersections. In practice, high density of features may be represented by cities condensed into a small space on the map, inappropriate intersections may produce intersections between roads, rivers, and buildings. TopoVW is a strategy based on the Visvalingam-Whyatt algorithm to create simplified geometries with shapes similar to the original map, preserving topological consistency between features in the output. It uses a point ranking strategy, in which line points are ranked by their effective area, a metric that determines the impact a point will cause to the geometry if removed from the line. Points with inferior effective area are eliminated from the original line. The method was able to process a map with 4 million line points and 10 million control points in less than 2 minutes on a Intel Core 2 Duo processor.
BibTeX
```
@inproceedings{mauricio-iceis-2015,
    author = "Gruppi, Mauricio G. and de Magalhães, Salles V. G. and Andrade, Marcus V. A. and Franklin, W. Randolph and Li, Wenli",
    title = "An Efficient and Topologically Correct Map Generalization Heuristic",
    booktitle = "Proceedings of the 17th International Conference on Enterprise Information Systems (ICEIS)",
    year = "2015",
    pages = "516-525, paper 236",
    doi = "https://doi.org/10.5220/0005398105160525",
    isbn = "978-989-758-096-3",
    mykey = "wenlili marcus salles",
    href = "\bibhref{214-mauricio-iceis-2015}",
    url = "http://www.iceis.org/Abstracts/2015/ICEIS\_2015\_Abstracts.htm"
}
```

W. Randolph Franklin and Salles Viana Gomes de Magalhães. Global properties from local topology. 10 Nov 2015. Talk at UC Santa Barbara, Center for Spatial Studies.
[details] [slides]

BibTeX

@misc{local-talk-ucsb-2015,
    author = "Franklin, W. Randolph and de Magalhães, Salles Viana Gomes",
    title = "Global properties from local topology",
    note = "Talk at {UC Santa Barbara}, Center for Spatial Studies",
    month = "10 Nov",
    year = "2015",
    mykey = "salles topology",
    href = "\bibhreft{207-local-talk-ucsb-2015.pdf}",
    customlinkslides = "https://wrfranklin.org/p/207-local-talk-ucsb-2015.pdf"
}

Mehrad Kamalzare, Thomas F. Zimmie, Zhongxian Chen, Christopher Stuetzle, Barbara Cutler, and W Randolph Franklin. Computer erosion modeling considering soil hydraulic conductivity. Journal of Geotechnical and Transportation Engineering, 22 June 2015.
[details] [full text]

BibTeX

@article{kamalzare-jgtte-2015,
    author = "Kamalzare, Mehrad and Zimmie, Thomas F. and Chen, Zhongxian and Stuetzle, Christopher and Cutler, Barbara and Franklin, W Randolph",
    title = "Computer Erosion Modeling Considering Soil Hydraulic Conductivity",
    journal = "Journal of Geotechnical and Transportation Engineering",
    year = "2015",
    volume = "1",
    number = "1",
    month = "22 June",
    issn = "2379-8777 (Online)",
    mykey = "stuetzle levee",
    href = "\bibhref{205-kamalzare-jgtte-2015}"
}

Maurício Gouvêa Gruppi, Salles V. G. de Magalhães, Marcus V. A. Andrade, W. Randolph Franklin, and Wenli Li. Using rational numbers and parallel computing to efficiently avoid round-off errors on map simplification. In Geoinfo 2015, XVI Brazilian Symposium on GeoInformatics. Campos do Jordão, SP, Brazil, 29 Nov – 2 Dec 2015.
[details] [full text] [slides]
Abstract
This paper presents EPLSimp, an algorithm for map generalization that avoids the creation of topological inconsistencies. EPLSimp is based on Visvalingam-Whyatt's (VW) algorithm on which least “important” points are removed first. Unlike VW's algorithm, when a point is deleted a verification is performed in order to check if this deletion would create topological inconsistencies. This was done by using arbitrary precision rational numbers to completely avoid errors caused by floating-point arithmetic. EPLSimp was carefully implemented to be efficient, although using rational numbers adds an overhead to the computation. This efficiency was achieved by using a uniform grid for indexing the geometric data and parallel computing to speedup the process.
BibTeX
```
@inproceedings{mauricio-rational-geoinfo-2015,
    author = "Gruppi, Maurício Gouvêa and de Magalhães, Salles V. G. and Andrade, Marcus V. A. and Franklin, W. Randolph and Li, Wenli",
    title = "Using Rational Numbers and Parallel Computing to Efficiently Avoid Round-Off Errors on Map Simplification",
    booktitle = "Geoinfo 2015, {XVI Brazilian} Symposium on GeoInformatics",
    year = "2015",
    month = "29 Nov -- 2 Dec",
    address = "Campos do Jordão, SP, Brazil",
    mykey = "marcus wenlili salles visviewshedsiting",
    href = "\bibhrefpt{198-mauricio-rational-geoinfo-2015}{198-mauricio-rational-geoinfo-2015-talk.pdf}",
    customlinkslides = "https://wrfranklin.org/p/198-mauricio-rational-geoinfo-2015-talk.pdf"
}
```

Salles V. G. de Magalhães, Marcus V. A. Andrade, W. Randolph Franklin, and Wenli Li. Fast path planning under polygonal obstacle constraints. In 4th GIS-focused algorithm competition, GISCUP 2015, co-located with ACM SIGSPATIAL GIS. Bellevue WA USA, 4 Nov 2015. Winner (2nd place).
[details] [full text]

BibTeX

@inproceedings{salles-giscup-2015,
    author = "de Magalhães, Salles V. G. and Andrade, Marcus V. A. and Franklin, W. Randolph and Li, Wenli",
    title = "Fast path planning under polygonal obstacle constraints",
    booktitle = "4th {GIS}-focused algorithm competition, {GISCUP} 2015, co-located with {ACM SIGSPATIAL GIS}",
    year = "2015",
    month = "4 Nov",
    address = "Bellevue WA USA",
    note = "Winner (2nd place)",
    mykey = "wenlili marcus salles pathplan sallesgiscup2015 uplan",
    href = "\bibhref{203-salles-giscup-2015}"
}

BibTeX

@inproceedings{salles-giscup-2015-nonote,
    author = "de Magalhães, Salles V. G. and Andrade, Marcus V. A. and Franklin, W. Randolph and Li, Wenli",
    title = "Fast path planning under polygonal obstacle constraints",
    booktitle = "4th {GIS}-focused algorithm competition, {GISCUP} 2015, co-located with {ACM SIGSPATIAL GIS}",
    year = "2015",
    month = "4 Nov",
    address = "Bellevue WA USA",
    href = "\bibhref{203-salles-giscup-2015}",
    mykey = "nonote marcus salles wenlili pathplan"
}

Salles V. G. de Magalhães, Marcus V. A. Andrade, W. Randolph Franklin, and Wenli Li. Fast exact parallel map overlay using a two-level uniform grid. In 4th ACM SIGSPATIAL International Workshop on Analytics for Big Geospatial Data (BigSpatial). Bellevue WA USA, 3 Nov 2015. doi:https://doi.org/10.1145/2835185.2835188.
[details] [full text]
Abstract
We present EPUG-Overlay (Exact Parallel Uniform Grid Overlay), an algorithm to overlay two maps that is fast and parallel, has no roundoff errors, and is freely available. EPUG-Overlay combines several novel aspects. It represents coordinates with rational numbers, thereby ensuring exact computations with no roundoff errors and the ensuing sliver problems and topological impossibilities. For efficiency, EPUG-Overlay performs the map overlay in parallel, thereby utilizing the ubiquitous multicore architecture. Our application goes beyond merely using existing packages, which are inefficient when used in parallel on large problems. Indeed, overlaying two maps with 53,000,000 edges and 730,000 faces took only 322 elapsed seconds (plus 116 seconds for I/O) on a dual 8-core 3.1 GHz Intel Xeon E5-2687 workstation. In contrast, GRASS, executing sequentially and generating roundoff errors, takes 5300 seconds. The overlay operation combines two input maps (planar graphs) containing faces (polygons) separated by polyline edges (chains), into a new map, each of whose faces is the intersection of one face from each input map. Floating point roundoff errors can cause an edge intersection to be missed or the computed intersection point be in a wrong face, leading to a topological inconsistency. Thus, a program might fail to compute a valid output map at all, using any amount of time. This gets worse when the inputs are bigger or have slivers. Heuristics can ameliorate this problem, but only to an extent. By representing each coordinate as a vulgar fraction, with multiprecision numerator and denominator, the computation is exact. EPUG-Overlay also executes various useful subproblems very quickly, such as locating a set of points in a planar graph and finding all the intersections among a large set of small edges. EPUG-Overlay is built on our earlier sequential floating-point algorithm that found the areas of the overlay polygons, without finding the polygons themselves.
BibTeX
```
@inproceedings{salles-overlay-bigspatial-2015,
    author = "de Magalhães, Salles V. G. and Andrade, Marcus V. A. and Franklin, W. Randolph and Li, Wenli",
    title = "Fast exact parallel map overlay using a two-level uniform grid",
    booktitle = "4th {ACM SIGSPATIAL} International Workshop on Analytics for Big Geospatial Data (BigSpatial)",
    year = "2015",
    month = "3 Nov",
    address = "Bellevue WA USA",
    href = "\bibhref{196-salles-overlay-bigspatial-2015}",
    doi = "https://doi.org/10.1145/2835185.2835188",
    mykey = "wenlili marcus salles overlay parallel"
}
```

Wenli Li, W. Randolph Franklin, and Salles V. G. de Magalhães. Segmented ODETLAP compression. In 25th Fall Workshop on Computational Geometry. U. Buffalo, New York, USA, 23-24 Oct 2015. (extended abstract).
[details] [full text]

BibTeX

@inproceedings{wenli-segment-fwcg-2015,
    author = "Li, Wenli and Franklin, W. Randolph and de Magalhães, Salles V. G.",
    title = "Segmented {ODETLAP} Compression",
    booktitle = "25th Fall Workshop on Computational Geometry",
    year = "2015",
    month = "23-24 Oct",
    address = "U. Buffalo, New York, USA",
    note = "(extended abstract)",
    mykey = "wenlili salles odetlap",
    href = "\bibhref{202-wenli-segment-fwcg-2015}"
}

Salles V. G. de Magalhães, W. Randolph Franklin, Marcus V. A. Andrade, and Wenli Li. An efficient algorithm for computing the exact overlay of triangulations. In 25th Fall Workshop on Computational Geometry. U. Buffalo, New York, USA, 23-24 Oct 2015. (extended abstract).
[details] [full text]

BibTeX

@inproceedings{salles-overlay-fwcg-2015,
    author = "de Magalhães, Salles V. G. and Franklin, W. Randolph and Andrade, Marcus V. A. and Li, Wenli",
    title = "An efficient algorithm for computing the exact overlay of triangulations",
    booktitle = "25th Fall Workshop on Computational Geometry",
    year = "2015",
    month = "23-24 Oct",
    address = "U. Buffalo, New York, USA",
    note = "(extended abstract)",
    mykey = "wenlili marcus salles overlay",
    href = "\bibhref{201-salles-overlay-fwcg-2015}"
}

W. Randolph Franklin, Marcus Andrade, Wenli Li, and Salles de Magalhães. Changing problems, databases, and tools in spatial search. 24 Aug 2015. Talk at U. Zürich, Dept of Geography.
[details] [slides]

BibTeX

@misc{changing-talk-zurich-2015,
    author = "Franklin, W. Randolph and Andrade, Marcus and Li, Wenli and de Magalhães, Salles",
    title = "Changing problems, databases, and tools in spatial search",
    note = "Talk at {U. Zürich}, {Dept} of {Geography}",
    month = "24 Aug",
    year = "2015",
    href = "\bibhreft{204-changing-talk-zurich-2015.pdf}",
    customlinkslides = "https://wrfranklin.org/p/204-changing-talk-zurich-2015.pdf",
    mykey = "wenlili marcus salles parallel"
}

W. Randolph Franklin. Algorithms, libraries, and development environments to process huge geoinformatic databases on modern hardware. Talk at CCNY, 15 April 2015.
[details] [slides]

BibTeX

@misc{algorithms-ccny-2015,
    author = "Franklin, W. Randolph",
    title = "Algorithms, libraries, and development environments to process huge geoinformatic databases on modern hardware",
    howpublished = "Talk at CCNY",
    month = "15 April",
    year = "2015",
    href = "\bibhreft{195-algorithms-ccny-2015.pdf}",
    customlinkslides = "https://wrfranklin.org/p/195-algorithms-ccny-2015.pdf",
    mykey = "parallel"
}

Marcus Andrade, Salles de Magalhães, W. Randolph Franklin, and Wenli Li. Research topics in GIS. Talk at CCNY, 15 April 2015.
[details] [slides]

BibTeX

@misc{salles-ccny-2015,
    author = "Andrade, Marcus and de Magalhães, Salles and Franklin, W. Randolph and Li, Wenli",
    title = "Research topics in {GIS}",
    howpublished = "Talk at CCNY",
    month = "15 April",
    year = "2015",
    href = "\bibhreft{194-salles-ccny-2015.pdf}",
    customlinkslides = "https://wrfranklin.org/p/194-salles-ccny-2015.pdf",
    mykey = "marcus wenlili salles parallel"
}

Wenli Li, W. Randolph Franklin, Marcus Andrade, and Salles de Magalhães. Research summary: siting and ODETLAP. Talk at CCNY, 15 April 2015.
[details] [slides]

BibTeX

@misc{wenli-ccny-2015,
    author = "Li, Wenli and Franklin, W. Randolph and Andrade, Marcus and de Magalhães, Salles",
    title = "Research Summary: Siting and {ODETLAP}",
    howpublished = "Talk at CCNY",
    month = "15 April",
    year = "2015",
    mykey = "wenlili marcus salles odetlap",
    customlinkslides = "https://wrfranklin.org/p/193-wenli-ccny-2015.pdf",
    href = "\bibhreft{193-wenli-ccny-2015.pdf}"
}

Thiago L. Gomes, Salles V. G. de Magalhães, Marcus V. A. Andrade, W. Randolph Franklin, and Guilherme C. Pena. Efficiently computing the drainage network on massive terrains with an external memory flooding process. Geoinformatica, April 2015. \url http://link.springer.com/article/10.1007/s10707-015-0225-y. doi:https://doi.org/10.1007/s10707-015-0225-y.
[details] [full text]

BibTeX

@article{gomes-emflow-2015,
    author = "Gomes, Thiago L. and de Magalhães, Salles V. G. and Andrade, Marcus V. A. and Franklin, W. Randolph and Pena, Guilherme C.",
    title = "Efficiently computing the drainage network on massive terrains with an external memory flooding process",
    href = "\bibhref{163-gomes-emflow-2015}",
    journal = "Geoinformatica",
    doi = "https://doi.org/10.1007/s10707-015-0225-y",
    note = "\url{http://link.springer.com/article/10.1007/s10707-015-0225-y}",
    mykey = "marcus salles hydro emflow",
    month = "April",
    year = "2015"
}

2014

W. Randolph Franklin and Marcus Andrade. The changing problems, databases, and tools in spatial search. In University of California at Santa Barbara, Spatial Search Specialist Workshop. 8–9 Dec 2014.
[details] [full text] [slides]

BibTeX

@inproceedings{ucsb-2014,
    author = "Franklin, W. Randolph and Andrade, Marcus",
    title = "The changing problems, databases, and tools in spatial search",
    booktitle = "{University of California at Santa Barbara, Spatial Search Specialist Workshop}",
    year = "2014",
    month = "8--9 Dec",
    customlinkslides = "https://wrfranklin.org/p/186-ucsb2014-spatial-probs-talk.pdf",
    mykey = "marcus",
    href = "\bibhrefpt{186-ucsb2014-spatial-probs}{186-ucsb2014-spatial-probs-talk.pdf}"
}

Salles V. G. de Magalhães, W. Randolph Franklin, Wenli Li, and Marcus V. A. Andrade. Fast map generalization heuristic with a uniform grid. In 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL 2014). Dallas, Texas, USA, 4–7 Nov 2014.
[details] [full text] [poster] [slides]

BibTeX

@inproceedings{giscup-2014,
    author = "de Magalhães, Salles V. G. and Franklin, W. Randolph and Li, Wenli and Andrade, Marcus V. A.",
    title = "Fast map generalization heuristic with a uniform grid",
    booktitle = "22nd {ACM SIGSPATIAL} International Conference on Advances in Geographic Information Systems {(ACM SIGSPATIAL 2014)}",
    year = "2014",
    month = "4--7 Nov",
    address = "Dallas, Texas, USA",
    href = "\bibhrefptp{185-acmgis2014-cup}{185-acmgis2014-cup-talk.ppt}{185-acmgis2014-cup-poster.pdf}",
    customlinkposter = "https://wrfranklin.org/p/185-acmgis2014-cup-poster.pdf",
    customlinkslides = "https://wrfranklin.org/p/185-acmgis2014-cup-talk.ppt",
    mykey = "wenlili marcus salles gridgen"
}

Wenli Li, W. Randolph Franklin, Daniel N. Benedetti, and Salles V. G. de Magalhães. Parallel multiple observer siting on terrain. In 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL 2014). Dallas, Texas, USA, 4–7 Nov 2014.
[details] [full text] [poster]
Abstract
This paper presents the optimization and parallelization of the multiple observer siting program, originally developed by Franklin and Vogt. Siting is a compute-intensive application with a large amount of inherent parallelism. The advantage of parallelization is not only a faster program but also the ability to solve bigger problems. We have parallelized the program using two different techniques: OpenMP, using multi-core CPUs, and CUDA, using a general purpose graphics processing unit (GPGPU). Experiment results show that both techniques are very effective. Using the OpenMP program, we are able to site tens of thousands of observers on a 16385 × 16385 terrain in less than 2 minutes, on our workstation with two CPUs and one GPU. The CUDA program achieves the same in about 30 seconds.
BibTeX
```
@inproceedings{li-acmgis-2014,
    author = "Li, Wenli and Franklin, W. Randolph and Benedetti, Daniel N. and de Magalhães, Salles V. G.",
    title = "Parallel Multiple Observer Siting on Terrain",
    booktitle = "22nd {ACM SIGSPATIAL} International Conference on Advances in Geographic Information Systems {(ACM SIGSPATIAL 2014)}",
    year = "2014",
    month = "4--7 Nov",
    href = "\bibhrefpp{182-acmgis2014-par-siting}{182-acmgis2014-par-siting-poster.pdf}",
    address = "Dallas, Texas, USA",
    customlinkposter = "https://wrfranklin.org/p/182-acmgis2014-par-siting-poster.pdf",
    mykey = "benedetti salles wenlili visviewshedsiting gpusiting parallelsiting parallel"
}
```
Guilherme Pena, Salles de Magalhães, Marcus Andrade, Randolph Franklin, Chaulio Ferreira, Wenli Li, and Daniel Benedetti. An efficient GPU multiple-observer siting method based on sparse-matrix multiplication. In 3rd ACM SIGSPATIAL International Workshop on Analytics for Big Geospatial Data (BigSpatial) 2014. Dallas TX USA, 4 Nov 2014.
[details] [full text] [slides]
Abstract
This paper proposes an efficient parallel heuristic for siting observers on raster terrains. More specifically, the goal is to choose the smallest set of points on a terrain such that observers located in these points are able to visualize at least a given percentage of the terrain. This problem is NP-Hard and has several applications such as determining the best places to position (site) communication or monitoring towers on a terrain. Since siting observers is a massive operation, its solution requires a huge amount of processing time even to obtain an approximate solution using a heuristic. This is still more evident when processing high resolution terrains that have become available due to modern data acquiring technologies such as LIDAR and IFSAR. Our new implementation uses dynamic programming and CUDA to accelerate the swap local search heuristic, which was proposed in previous works. Also, to efficiently use the parallel computing resources of GPUs, we adapted some techniques previously developed for sparse-dense matrix multiplication. We compared this new method with previous parallel implementations and the new method is much more efficient than the previous ones. It can process much larger terrains (the older methods are restrictive about terrain size) and it is faster.
BibTeX
```
@inproceedings{bigspatial-2014,
    author = "Pena, Guilherme and de Magalhães, Salles and Andrade, Marcus and Franklin, Randolph and Ferreira, Chaulio and Li, Wenli and Benedetti, Daniel",
    title = "An efficient {GPU} multiple-observer siting method based on sparse-matrix multiplication",
    booktitle = "3rd {ACM SIGSPATIAL} International Workshop on Analytics for Big Geospatial Data (BigSpatial) 2014",
    year = "2014",
    month = "4 Nov",
    address = "Dallas TX USA",
    href = "\bibhrefpt{191-bigspatial-sparse-siting-2014}{191-bigspatial-sparse-siting-2014-talk.pdf}",
    customlinkslides = "https://wrfranklin.org/p/191-bigspatial-sparse-siting-2014-talk.pdf",
    mykey = "visviewshedsiting benedetti marcus wenlili salles parallel"
}
```

Salles V. G. de Magalhães, W. Randolph Franklin, Marcus V. A. Andrade, and Wenli Li. An efficient map generalization heuristic based on the Visvalingam–Whyatt algorithm. In 24th Fall Workshop on Computational Geometry. U. Connecticut, Storrs CT, USA, 31 Oct – 1 Nov 2014. (extended abstract).
[details] [full text] [slides]

BibTeX

@inproceedings{salles-fwcg-2014,
    author = "de Magalhães, Salles V. G. and Franklin, W. Randolph and Andrade, Marcus V. A. and Li, Wenli",
    title = "An efficient map generalization heuristic based on the {V}isvalingam--{Whyatt} algorithm",
    booktitle = "24th Fall Workshop on Computational Geometry",
    year = "2014",
    month = "31 Oct -- 1 Nov",
    address = "U. Connecticut, Storrs CT, USA",
    note = "(extended abstract)",
    mykey = "wenlili marcus salles",
    customlinkslides = "https://wrfranklin.org/p/188-fwcg2014-salles-mapgen-talk.pdf",
    href = "\bibhrefpt{188-fwcg2014-salles-mapgen}{188-fwcg2014-salles-mapgen-talk.pdf}"
}

Wenli Li, W. Randolph Franklin, Salles V. G. de Magalhães, and Marcus V. A. Andrade. Restricted bathymetric tracklines interpolation. In 24th Fall Workshop on Computational Geometry. U. Connecticut, Storrs CT, USA, 31 Oct – 1 Nov 2014. (extended abstract).
[details] [full text] [slides]
Abstract
In this paper, we propose a method to interpolate a small bathymetry with long and thin sand bars as distinctive features. Underwater terrain, or bathymetry, is measured by a single beam or multibeam echosounder attached under a boat. Measurement points are distributed along the a track of the boat and their positions and values constitute a trackline. Although full coverage is possible in multibeam surveys, tracklines are often sparse and thin, especially in single beam surveys, and it is expected to interpolate the bathymetry from tracklines. There are dozens of existing spatial interpolation methods with their strengths and weaknesses, and some are more widely used than others. One of the methods, overdetermined laplacian partial differentiation equations (ODETLAP), has been successfully used in bathymetry data interpolation and shown to be better than some of the popular methods. However, it is more suited for large-scale bathymetry without significant linear or continuous features.
BibTeX
```
@inproceedings{li-fwcg-2014,
    author = "Li, Wenli and Franklin, W. Randolph and de Magalhães, Salles V. G. and Andrade, Marcus V. A.",
    title = "Restricted Bathymetric Tracklines Interpolation",
    booktitle = "24th Fall Workshop on Computational Geometry",
    year = "2014",
    month = "31 Oct -- 1 Nov",
    address = "U. Connecticut, Storrs CT, USA",
    note = "(extended abstract)",
    mykey = "marcus wenlili salles bathy",
    customlinkslides = "https://wrfranklin.org/p/187-fwcg2014-li-bathy-talk.pdf",
    href = "\bibhrefpt{187-fwcg2014-li-bathy}{187-fwcg2014-li-bathy-talk.pdf}"
}
```

Salles V. G. de Magalhães and W. Randolph Franklin. Exactly computing map overlays using rational numbers. In Autocarto 2014. Pittsburgh PA, 5–7 Oct 2014. Cartography and Geographic Information Society. (abstract only).
[details] [full text] [slides]

BibTeX

@inproceedings{autocarto-ratover-2014,
    author = "de Magalhães, Salles V. G. and Franklin, W. Randolph",
    title = "Exactly computing map overlays using rational numbers",
    month = "5--7 Oct",
    year = "2014",
    booktitle = "Autocarto 2014",
    organization = "Cartography and Geographic Information Society",
    address = "Pittsburgh PA",
    note = "(abstract only)",
    customlinkslides = "https://wrfranklin.org/p/178-autocarto-ratover-2014-talk.pdf",
    href = "\bibhrefpt{178-autocarto-ratover-2014}{178-autocarto-ratover-2014-talk.pdf}",
    mykey = "salles overlay"
}

Chaulio R. Ferreira, Marcus V. A. Andrade, Salles V. G. de Magalhães, W. R. Franklin, and Guilherme C. Pena. A parallel algorithm for viewshed computation on grid terrains. Journal of information and data management, 2014. invited.
[details] [full text]
Abstract
Viewshed (or visibility map) computation is an important component in many GIScience applications and, as nowadays there are huge volume of terrain data available at high resolutions, it is important to develop efficient algorithms to process these data. Since the main improvements on modern processors come from multi-core architectures, parallel programming provides a promising means for developing faster algorithms. In this paper, we describe a new parallel algorithm based on the model proposed by Van Kreveld. Our algorithm uses the shared memory model, which is relatively cheap and supported by most current processors. Experiments have shown that, with 16 parallel cores,was up to 12 times faster than the serial implementation, and up to 3.9 times using four parallel cores, which isalmost optimal speedup.
BibTeX
```
@article{chaulio-jidm-2014,
    author = "Ferreira, Chaulio R. and Andrade, Marcus V. A. and de Magalhães, Salles V. G. and Franklin, W. R. and Pena, Guilherme C.",
    title = "A parallel algorithm for viewshed computation on grid terrains",
    journal = "Journal of information and data management",
    year = "2014",
    volume = "5",
    number = "1",
    note = "invited",
    href = "\bibhref{180-jidm2014-chaulio-parallel-viewshed}",
    mykey = "visviewshedsiting marcus salles parallel"
}
```

Salles V. G. de Magalhães, Marcus V. A. Andrade, W. Randolph Franklin, and Guilherme C. Pena. A linear time algorithm to compute the drainage network on grid terrains. J. Hydroinformatics, 16(6):1227–1234, 2014. Update of the winner of the Best Paper Award (2nd place) at AGILE 2012. doi:https://doi.org/10.2166/hydro.2013.068.
[details] [full text]

BibTeX

@article{salles-hydroinformatics-2014,
    author = "de Magalhães, Salles V. G. and Andrade, Marcus V. A. and Franklin, W. Randolph and Pena, Guilherme C.",
    title = "A linear time algorithm to compute the drainage network on grid terrains",
    journal = "J. Hydroinformatics",
    year = "2014",
    volume = "16",
    number = "6",
    pages = "1227--1234",
    href = "\bibhref{166-hydroinformatics-maghalaes-rwflood}",
    doi = "https://doi.org/10.2166/hydro.2013.068",
    note = "Update of the winner of the Best Paper Award (2nd place) at AGILE 2012",
    mykey = "marcus salles rwflood hydro sallesagile2012"
}

Guilherme C. Pena, Marcus V.A. Andrade, Salles V.G. de Magalhães, W. R. Franklin, and Chaulio R. Ferreira. An improved parallel algorithm using GPU for siting observers on terrain. In 16th International Conference on Enterprise Information Systems (ICEIS 2014), 367–375. Lisbon, 27–30 April 2014. doi:https://doi.org/10.5220/0004884303670375.
[details] [full text] [slides]
Abstract
This paper presents an efficient method to determine a set of observers (that is, where to site them) such that a given percentage of a terrain is visually covered. Our method extends the method proposed in (Franklin, 2002) including a local search heuristic efficiently implemented using dynamic programming and GPU parallel programming. This local search strategy allows to achieve a higher coverage using the same number of observers as the original method and thus it is possible to obtain a given coverage using a smaller number of observers. It can be an important improvement since an observer can represent an expensive facility such as a telecommunication tower. The proposed method performance was compared with that of other methods and the tests showed that it can be more than 1200 times faster than the sequential implementation (with no use of dynamic programming and no GPU parallel programmming) and, also, more than 20 times faster than a previous parallel method presented in (de Magalhaes et al., 2011).
BibTeX
```
@inproceedings{iceis-2014,
    author = "Pena, Guilherme C. and Andrade, Marcus V.A. and de Magalhães, Salles V.G. and Franklin, W. R. and Ferreira, Chaulio R.",
    title = "An Improved Parallel Algorithm using {GPU} for Siting Observers on Terrain",
    booktitle = "16th International Conference on Enterprise Information Systems ({ICEIS} 2014)",
    year = "2014",
    month = "27--30 April",
    address = "Lisbon",
    pages = "367--375",
    doi = "https://doi.org/10.5220/0004884303670375",
    href = "\bibhrefpt{177-ICEIS2014-pena-site-gpu}{177-ICEIS2014-pena-site-gpu-talk.pdf}",
    customlinkslides = "https://wrfranklin.org/p/177-ICEIS2014-pena-site-gpu-talk.pdf",
    mykey = "visviewshedsiting gpusiting marcus salles parallel"
}
```

2013

W. Randolph Franklin. Algorithms, libraries, and development environments to process huge geoinformatic databases on modern hardware. Geoinfo 2013, XIV Brazilian Symposium on GeoInformatics, 26 Nov 2013. Keynote talk, \url http://www.geoinfo.info/geoinfo2013/index.php.
[details] [slides]
Abstract
This talk will survey specialized algorithms, libraries, and development environments to facilitate processing huge geoinformatic databases on modern hardware. Modern hardware is generally parallel, with the most economical platform, with the cheapest entry point, being NVidia GPUs. Desktop computers with current graphics cards, and even most laptop computers sold today, contain this platform, which was intended for realistic graphics, but which is also accessible by a programmer. Now, almost anyone can access a platform running thousands of parallel threads; the major problem being, "now what?"
BibTeX
```
@misc{geoinfo-2013,
    author = "Franklin, W. Randolph",
    title = "Algorithms, libraries, and development environments to process huge geoinformatic databases on modern hardware",
    howpublished = "Geoinfo 2013, {XIV Brazilian} Symposium on GeoInformatics",
    month = "26 Nov",
    year = "2013",
    note = "Keynote talk, \url{http://www.geoinfo.info/geoinfo2013/index.php}",
    href = "\bibhreft{176-geoinfo2013-algorithms-talk.pdf}",
    customlinkslides = "https://wrfranklin.org/p/176-geoinfo2013-algorithms-talk.pdf",
    mykey = "parallel"
}
```

Randolph Franklin. Adaptive grids then and now. In Barry Wellar, editor, AutoCarto Six Retrospective, pages 119–124. Information Research Board Inc., 2013.
[details] [full text]

BibTeX

@incollection{ac6-retro-2013,
    author = "Franklin, Randolph",
    editor = "Wellar, Barry",
    title = "Adaptive grids then and now",
    booktitle = "AutoCarto Six Retrospective",
    year = "2013",
    pages = "119--124",
    publisher = "Information Research Board Inc.",
    href = "\bibhref{175-autocarto-retrospective-adaptive-grids}",
    isbn = "978-0-99211435-0-3"
}

Chaulio R. Ferreira, Marcus V. A. Andrade, Salles V. G. de Magalhães, W. R. Franklin, and Guilherme C. Pena. A parallel sweep line algorithm for visibility computation. In Geoinfo 2013, XIV Brazilian Symposium on GeoInformatics. Campos do Jordão, SP, Brazil, 24–27 Nov 2013. Winner of best paper award, \url http://www.geoinfo.info/geoinfo2013/index.php.
[details] [full text]
Abstract
This paper describes a new parallel raster terrain visibility (or viewshed) algorithm, based on the sweep-line model of [Van Kreveld 1996]. Computing the terrain visible from a given observer is required for many GIS applications, with applications ranging from radio tower siting to aesthetics. Processing the newly available higher resolution terrain data requires faster architectures and algorithms. Since the main improvements on modern processors come from multi-core architectures, parallel programming provides a promising means for developing faster algorithms. Our algorithm uses the economical and widely available shared memory model with OpenMP. Experimentally, our parallel speedup is almost linear. On 16 parallel processors, our algorithm is up to 12 times faster than the serial implementation.
BibTeX
```
@inproceedings{chaulio-geoinfo-2013,
    author = "Ferreira, Chaulio R. and Andrade, Marcus V. A. and de Magalhães, Salles V. G. and Franklin, W. R. and Pena, Guilherme C.",
    title = "A Parallel Sweep Line Algorithm for Visibility Computation",
    booktitle = "Geoinfo 2013, {XIV Brazilian} Symposium on GeoInformatics",
    year = "2013",
    month = "24--27 Nov",
    address = "Campos do Jordão, SP, Brazil",
    href = "\bibhref{174-geoinfo2013-chaulio-sweep}",
    note = "Winner of best paper award, \url{http://www.geoinfo.info/geoinfo2013/index.php}",
    mykey = "marcus salles visviewshedsiting parallel chauliogeoinfo2013"
}
```

Chaulio R. Ferreira, Marcus V. A. Andrade, Salles V. G. de Magalhães, W. R. Franklin, and Guilherme C. Pena. A parallel sweep line algorithm for visibility computation. In Geoinfo 2013, XIV Brazilian Symposium on GeoInformatics. Campos do Jordão, SP, Brazil, 24–27 Nov 2013.
[details] [full text]

BibTeX

@inproceedings{chaulio-geoinfo-2013-nonote,
    author = "Ferreira, Chaulio R. and Andrade, Marcus V. A. and de Magalhães, Salles V. G. and Franklin, W. R. and Pena, Guilherme C.",
    title = "A Parallel Sweep Line Algorithm for Visibility Computation",
    booktitle = "Geoinfo 2013, {XIV Brazilian} Symposium on GeoInformatics",
    year = "2013",
    month = "24--27 Nov",
    address = "Campos do Jordão, SP, Brazil",
    href = "\bibhref{174-geoinfo2013-chaulio-sweep}",
    mykey = "nonote marcus salles"
}

Wenli Li, W. Randolph Franklin, and Daniel Benedetti. Parallel multiple observer siting on terrain. In 23rd Fall Workshop on Computational Geometry. City College, New York City, USA, 25–26 Oct 2013. (extended abstract).
[details] [full text] [slides]

Abstract

Multiple observer siting has much inherent parallelism. We have parallelized the siting package using OpenMP and CUDA. The results show that both methods are effective for parallelizing the program. Although the overall speedups of the two methods are similar, which are about 16, the speedups of the constituent parts of the program are quite different.

BibTeX

@inproceedings{li-fwcg-2013,
    author = "Li, Wenli and Franklin, W. Randolph and Benedetti, Daniel",
    title = "Parallel Multiple Observer Siting on Terrain",
    booktitle = "23rd Fall Workshop on Computational Geometry",
    year = "2013",
    month = "25--26 Oct",
    address = "City College, New York City, USA",
    note = "(extended abstract)",
    href = "\bibhrefpt{173-fwcg2013-li-parallel-siting}{173-fwcg2013-li-parallel-siting-talk.pdf}",
    customlinkslides = "https://wrfranklin.org/p/173-fwcg2013-li-parallel-siting-talk.pdf",
    mykey = "benedetti wenlili parallelsiting gpusiting parallel"
}

Daniel Benedetti, W. Randolph Franklin, and Wenli Li. CUDA-accelerated ODETLAP: a parallel lossy compression implementation. In 23rd Fall Workshop on Computational Geometry. City College, New York City, USA, 25–26 Oct 2013. (extended abstract).
[details] [full text] [slides]
Abstract
We present an implementation of Overdetermined Laplacian Partial Differentiation Equations (ODETLAP) that uses CUDA directly. This lossy compression technique approximates a solution to an overdetermined system of equations in order to reconstruct gridded, correlated data. ODETLAP can be used to compress a dataset or to reconstruct missing data. Parallelism in CUDA provides speed performance improvements over other implementation methods. ODETLAP is inspired by the Laplacian Partial Differential Equation, though it is capable of preserving local extrema. Typical compression techniques are limited to viewing data as being one dimensional. The ODETLAP algorithm instead utilizes the autocorrelation of data in multiple dimensions to perform compression. This allows for improved compression of higher dimensional datasets, as can be found in geographical and environmental data[1, 2]. ODETLAP requires the construction and solution approximation of a sparse over-determined linear system of equations. As a result, the algorithm is quite compute-intensive. Parallelization techniques offer means of improving performance of this algorithm. The CUDA libraries, Thrust and CUSP, will be utilized in this parallel implementation of ODETLAP The Thrust library provides means for construction of the overdetermined system matrix, while the CUSP library contains solvers for such systems.
BibTeX
```
@inproceedings{benedetti-fwcg-2013,
    author = "Benedetti, Daniel and Franklin, W. Randolph and Li, Wenli",
    title = "{CUDA}-Accelerated {ODETLAP}: A Parallel Lossy Compression Implementation",
    booktitle = "23rd Fall Workshop on Computational Geometry",
    year = "2013",
    month = "25--26 Oct",
    address = "City College, New York City, USA",
    note = "(extended abstract)",
    href = "\bibhrefpt{172-fwcg2013-benedetti-cuda-odetlap}{172-fwcg2013-benedetti-cuda-odetlap-talk.pdf}",
    customlinkslides = "https://wrfranklin.org/p/172-fwcg2013-benedetti-cuda-odetlap-talk.pdf",
    mykey = "benedetti wenlili odetlap parallel"
}
```
W. Randolph Franklin. Parallel volume computation of massive polyhedron union. In 23rd Fall Workshop on Computational Geometry. City College, New York City, USA, 25–26 Oct 2013. (extended abstract).
[details] [full text] [slides]
Abstract
We present a parallel implementation of UNION3, an algorithm for computing the volume, surface area, center of mass, or similar properties of a boolean combination of many polyhedra. UNION3 has been implemented on the special case of the union of congruent isothetic cubes, and tested on 100, 000, 000 cubes. The algorithm uses a volume formula that does not require first computing the explicit union. All that is needed is the set of output vertices, including each vertex's position and neighborhood. UNION3's computation does not use randomization or sampling, and its output is exact. The implementation is parallel, using OpenMP. When using 32 threads, UNION3's elapsed time is only a few minutes, and the speedup, compared to using one thread, is a factor of ten. When executed on uniform random i.i.d input, UNION3's execution time is linear in the number of output vertices. UNION3 is intended as an example of a parallel geometry algorithm whose techniques should be broadly applicable.
BibTeX
```
@inproceedings{fwcg-2013,
    author = "Franklin, W. Randolph",
    title = "Parallel Volume Computation of Massive Polyhedron Union",
    booktitle = "23rd Fall Workshop on Computational Geometry",
    year = "2013",
    month = "25--26 Oct",
    address = "City College, New York City, USA",
    note = "(extended abstract)",
    href = "\bibhrefpt{171-fwcg2013-parallel-union}{171-fwcg2013-parallel-union-talk.pdf}",
    customlinkslides = "https://wrfranklin.org/p/171-fwcg2013-parallel-union-talk.pdf",
    mykey = "union3 topology parallel"
}
```

W. Randolph Franklin. Research summary slides. September 2013.
[details] [full text]

BibTeX

@misc{research-summary-2013,
    author = "Franklin, W. Randolph",
    title = "Research Summary Slides",
    month = "September",
    year = "2013",
    href = "\bibhref{170-research-summary-2013}"
}

W. Randolph Franklin. Geometric operations on millions of objects. (talk), 24 July 2013.
[details] [full text]

BibTeX

@misc{millions-2013,
    author = "Franklin, W. Randolph",
    title = "Geometric Operations on Millions of Objects",
    howpublished = "(talk)",
    month = "24 July",
    year = "2013",
    href = "\bibhref{169-millions-talk}"
}

Mehrad Kamjaalzare, Thomas F. Zimmie, Tianning Steven Han, Matt McMullan, Barbara Cutler, and W. Randolph Franklin. Computer simulation of levee's erosion and overtopping. In The 18th international conference on soil mechanics and geotechnical engineering, 743–746. Paris, France, 2–6 Sept 2013. \url http://www.issmge2013.org/.
[details] [full text]

BibTeX

@inproceedings{kalamzare-icsmge-2013,
    author = "Kamjaalzare, Mehrad and Zimmie, Thomas F. and Han, Tianning Steven and McMullan, Matt and Cutler, Barbara and Franklin, W. Randolph",
    title = "Computer Simulation of Levee's Erosion and Overtopping",
    booktitle = "The 18th international conference on soil mechanics and geotechnical engineering",
    year = "2013",
    month = "2--6 Sept",
    address = "Paris, France",
    pages = "743--746",
    href = "\bibhref{167-icsmge2013-overtopping}",
    mykey = "levee",
    note = "\url{http://www.issmge2013.org/}"
}

W. Randolph Franklin, You Li, Tsz-Yam Lau, and Peter Fox. CUDA-accelerated HD-ODETLAP: lossy high dimensional gridded data compression. In Xuan Shi, Volodymyr Kindratenko, and Chaowei Yang, editors, Modern Accelerator Technologies for Geographic Information Science. Springer, 2013.
[details] [full text]
Abstract
We present High-dimensional Overdetermined Laplacian Partial Differential Equations (HD-ODETLAP), an algorithm and implementation for lossy compression of high-dimensional arrays of data. HD-ODETLAP exploits autocorrelations in the data in any dimension. It also adapts to regions in the data with varying value ranges, resulting in the maximum error being closer to the RMS error. HD-ODETLAP compresses a data array by iteratively selecting a representative set of points from the array. That set of points, efficiently coded, is the compressed dataset. The compressed dataset is uncompressed by solving an overdetermined sparse system of linear equations for an approximation to the original array. HD-ODETLAP uses NVIDIA CUDA called from MATLAB to exploit GPU parallel processing to achieve considerable speedup compared to execution on a CPU. In addition, HD-ODETLAP compresses much better than JPEG2000 and 3D-SPIHT, when fixing either the average or the maximum error. An application is to facilitate storage and transmission of voluminous datasets for better climatological and environmental analysis and prediction.
BibTeX
```
@incollection{hdodetlap-2013,
    author = "Franklin, W. Randolph and Li, You and Lau, Tsz-Yam and Fox, Peter",
    editor = "Shi, Xuan and Kindratenko, Volodymyr and Yang, Chaowei",
    title = "{CUDA}-accelerated {HD-ODETLAP}: Lossy high dimensional gridded data compression",
    booktitle = "Modern Accelerator Technologies for Geographic Information Science",
    year = "2013",
    isbn = "978-1-4614-8744-9",
    publisher = "Springer",
    href = "\bibhref{165-2013-hdodetlap}",
    mykey = "youli lau odetlap parallel"
}
```
Tsz-Yam Lau and W. Randolph Franklin. River network completion without height samples using geometry-based induced terrain. Cartography and Geographic Information Science, 40(2):316–325, 29 Apr 2013. arXiv:http://www.tandfonline.com/doi/pdf/10.1080/15230406.2013.780785, doi:https://doi.org/10.1080/15230406.2013.780785.
[details] [full text]
Abstract
We present an improved method for connecting broken river segments by incorporating segment geometry into the induced terrain approach. The reconnection problem is important in aerial photography. Canopies and clouds cover parts of rivers, and a complete river network is necessary for transportation, land-use planning, and floodplain control. Our previously presented induced terrain approach guarantees that the global network topology is hydrologically consistent. However, it assumes many reliable height samples, which may be unavailable because of extensive view obstacles or gentle surfaces, to reconstruct the induced terrain surface. In this paper, we exploit river segment geometries to generate the induced terrain. We assign lowest heights to the known river locations, and higher and higher heights for locations further and further away. Since areas radiating from segment tips tend to be where a river is broken, we assign relatively small heights to these areas, so as to favor water flow toward them in the subsequent river derivation. On average, such a tip-biased model improves reconnection accuracy by five percentage points (which is 40\% of what we would have been corrected if we had had rich height samples covering 10\% of the terrain cells) over the intuitive baseline model in which the height of a location increases with its distance from the respective nearest river location, without considering the potential effect of segment tips as the tip-biased approach.
BibTeX
```
@article{lau-cagis-2013,
    author = "Lau, Tsz-Yam and Franklin, W. Randolph",
    title = "River network completion without height samples using geometry-based induced terrain",
    journal = "Cartography and Geographic Information Science",
    volume = "40",
    number = "2",
    pages = "316-325",
    year = "2013",
    month = "29 Apr",
    doi = "https://doi.org/10.1080/15230406.2013.780785",
    eprint = "http://www.tandfonline.com/doi/pdf/10.1080/15230406.2013.780785",
    href = "\bibhref{164-cagis2013-better-completion}",
    mykey = "hydro lau"
}
```

Mehrad Kamalzare, Tianning Steven Han, Matt McMullan, Chris Stuetzle, Thomas F. Zimmie, Barbara Cutler, and W. Randolph Franklin. Computer simulation of levee erosion and overtopping. In Christopher Meehan, Daniel Pradel, Miguel A. Pando, and Joseph F. Labuz, editors, Proceeding: Geo-Congress 2013: Stability and Performance of Slopes and Embankments, 1851–1860. San Diego, California, USA, 3–7 Mar 2013. American Society of Civil Engineers. doi:https://doi.org/10.1061/9780784412787.186.
[details] [full text]

BibTeX

@inproceedings{kalamzare-geocongress-2013,
    author = "Kamalzare, Mehrad and Han, Tianning Steven and McMullan, Matt and Stuetzle, Chris and Zimmie, Thomas F. and Cutler, Barbara and Franklin, W. Randolph",
    editor = "Meehan, Christopher and Pradel, Daniel and Pando, Miguel A. and Labuz, Joseph F.",
    title = "Computer Simulation of Levee Erosion and Overtopping",
    booktitle = "Proceeding: {Geo-Congress} 2013: Stability and Performance of Slopes and Embankments",
    publisher = "American Society of Civil Engineers",
    pages = "1851--1860",
    year = "2013",
    month = "3--7 Mar",
    address = "San Diego, California, USA",
    doi = "https://doi.org/10.1061/9780784412787.186",
    isbn = "978-0-7844-1278-7",
    href = "\bibhref{181-geocongress2013-erosion}",
    mykey = "levee stuetzle"
}

2012

Thiago L. Gomes, Salles V. G. de Magalhães, Marcus V. A. Andrade, W. Randolph Franklin, and Guilherme C. Pena. Computing the drainage network on huge grid terrains. In 1st ACM SIGSPATIAL International Workshop on Analytics for Big Geospatial Data (BigSpatial-2012). Redondo Beach, CA, 6 Nov 2012.
[details] [full text] [slides]

BibTeX

@inproceedings{gomes-acmgis-2012,
    author = "Gomes, Thiago L. and de Magalhães, Salles V. G. and Andrade, Marcus V. A. and Franklin, W. Randolph and Pena, Guilherme C.",
    title = "Computing the drainage network on huge grid terrains",
    address = "Redondo Beach, CA",
    month = "6 Nov",
    customlinkslides = "https://wrfranklin.org/p/162-bigspatial2012-drainage-talk.pdf",
    href = "\bibhrefpt{162-bigspatial2012-drainage}{162-bigspatial2012-drainage-talk.pdf}",
    booktitle = "1st {ACM SIGSPATIAL} International Workshop on Analytics for Big Geospatial Data {(BigSpatial-2012)}",
    mykey = "marcus salles hydro emflow",
    year = "2012"
}

Tsz-Yam Lau and W. Randolph Franklin. Automated artifact-free seafloor surface reconstruction with two-step ODETLAP (Ph.D. showcase). In 20th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS 2012). Redondo Beach, CA, 6–9 Nov 2012.
[details] [full text] [poster]

BibTeX

@inproceedings{lau-acmgis-2012,
    author = "Lau, Tsz-Yam and Franklin, W. Randolph",
    title = "Automated artifact-free seafloor surface reconstruction with two-step {ODETLAP} ({Ph.D.} Showcase)",
    booktitle = "20th {ACM} {SIGSPATIAL} International Conference on Advances in Geographic Information Systems ({ACM SIGSPATIAL GIS} 2012)",
    year = "2012",
    address = "Redondo Beach, CA",
    month = "6--9 Nov",
    mykey = "lau odetlap",
    customlinkposter = "https://wrfranklin.org/p/160-acmgis2012-seafloor-poster.pdf",
    href = "\bibhrefpp{160-acmgis2012-seafloor}{160-acmgis2012-seafloor-poster.pdf}"
}

Chaulio R. Ferreira, Salles V. G. de Magalhães, Marcus V. A. Andrade, W. Randolph Franklin, and André M. Pompermayer. More efficient terrain viewshed computation on massive datasets using external memory. In 20th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS 2012). Redondo Beach, CA, 6–9 Nov 2012.
[details] [full text] [poster]
Abstract
We present a better algorithm and implementation for external memory viewshed computation. It is about four times faster than the most recent and most efficient published methods. Ours is also much simpler. Since processing large datasets can take hours, this improvement is significant. To reduce the total number of I/O operations, our method is based on subdividing the terrain into blocks which are stored in a special data structure managed as a cache memory. The viewshed is that region of the terrain that is visible by a fixed observer, who may be on or above the terrain. Its applications range from visual nuisance abatement to radio transmitter siting and surveillance.
BibTeX
```
@inproceedings{ferreira-acmgis-2012,
    author = "Ferreira, Chaulio R. and de Magalhães, Salles V. G. and Andrade, Marcus V. A. and Franklin, W. Randolph and Pompermayer, André M.",
    title = "More efficient terrain viewshed computation on massive datasets using external memory",
    booktitle = "20th {ACM} {SIGSPATIAL} International Conference on Advances in Geographic Information Systems ({ACM SIGSPATIAL GIS} 2012)",
    year = "2012",
    address = "Redondo Beach, CA",
    month = "6--9 Nov",
    href = "\bibhrefpp{159-acmgis2012-viewshed}{159-acmgis2012-viewshed-poster.pdf}",
    customlinkposter = "https://wrfranklin.org/p/159-acmgis2012-viewshed-poster.pdf",
    mykey = "visviewshedsiting marcus salles"
}
```

W. Randolph Franklin, You Li, Tsz-Yam Lau, and Peter Fox. CUDA-accelerated HD-ODETLAP: lossy high dimensional gridded data compression. In 2012 International Workshop on Modern Accelerator Technologies for GIScience (MAT4GIScience 2012). Columbus OH, 18 Sep 2012.
[details] [full text] [slides]

BibTeX

@inproceedings{giscience-hdodetlap-2012,
    author = "Franklin, W. Randolph and Li, You and Lau, Tsz-Yam and Fox, Peter",
    title = "{CUDA}-accelerated {HD-ODETLAP}: Lossy high dimensional gridded data compression",
    booktitle = "2012 International Workshop on Modern Accelerator Technologies for {GIScience} ({MAT4GIScience} 2012)",
    year = "2012",
    address = "Columbus OH",
    month = "18 Sep",
    mykey = "youli lau odetlap",
    customlinkslides = "https://wrfranklin.org/p/156-mat4giscience2012-hdodetlap-talk.pdf",
    href = "\bibhrefpt{156-mat4giscience2012-hdodetlap}{156-mat4giscience2012-hdodetlap-talk.pdf}"
}

Christopher Stuetzle and W. Randolph Franklin. Representation of terrain data by drilling process. In 2012 AutoCarto International Symposium on Automated Cartography. Columbus OH, 16–18 Sep 2012. abstract.
[details] [full text] [slides]

BibTeX

@inproceedings{stuetzle-autocarto-2012,
    author = "Stuetzle, Christopher and Franklin, W. Randolph",
    title = "Representation of terrain data by drilling process",
    booktitle = "2012 AutoCarto International Symposium on Automated Cartography",
    year = "2012",
    address = "Columbus OH",
    month = "16--18 Sep",
    note = "abstract",
    mykey = "terrain stuetzle",
    customlinkslides = "https://wrfranklin.org/p/155-autocarto2012-rep-terrain-talk.pdf",
    href = "\bibhrefat{155-autocarto2012-rep-terrain-abs}{155-autocarto2012-rep-terrain-talk.pdf}"
}

Tsz-Yam Lau and W. Randolph Franklin. Improving river network completion under absence of height samples using geometry-based induced terrain approach. In 2012 AutoCarto International Symposium on Automated Cartography. Columbus OH, 16–18 Sep 2012.
[details] [full text] [slides]

BibTeX

@inproceedings{lau-autocarto-2012,
    author = "Lau, Tsz-Yam and Franklin, W. Randolph",
    title = "Improving river network completion under absence of height samples using geometry-based induced terrain approach",
    booktitle = "2012 AutoCarto International Symposium on Automated Cartography",
    year = "2012",
    address = "Columbus OH",
    month = "16--18 Sep",
    customlinkslides = "https://wrfranklin.org/p/154-autocarto2012-better-completion-talk.pptx",
    href = "\bibhrefpt{154-autocarto2012-better-completion}{154-autocarto2012-better-completion-talk.pptx}",
    mykey = "lau hydro"
}

Christopher Stuetzle and W. Randolph Franklin. Representing terrain with mathematical operators. In 15th International Symposium on Spatial Data Handling. Bonn, Germany, 22–24 Aug 2012.
[details] [full text] [slides] [video]

BibTeX

@inproceedings{stuetzle-sdh-2012,
    author = "Stuetzle, Christopher and Franklin, W. Randolph",
    title = "Representing terrain with mathematical operators",
    booktitle = "15th International Symposium on Spatial Data Handling",
    year = "2012",
    address = "Bonn, Germany",
    month = "22--24 Aug",
    customlinkslides = "https://wrfranklin.org/p/153-sdh2012-representing-talk.pdf",
    customlinkvideo = "https://wrfranklin.org/p/153-sdh2012-representing-video.mp4",
    mykey = "terrain stuetzle",
    href = "\bibhrefpt{153-sdh2012-representing}{153-sdh2012-representing-talk.pdf}"
}

Tsz-Yam Lau and W. Randolph Franklin. Better completion of fragmentary river networks with the induced terrain approach by using known non-river locations. In 15th International Symposium on Spatial Data Handling. Bonn, Germany, 22–24 Aug 2012.
[details] [full text] [slides]

BibTeX

@inproceedings{lau-sdh-2012,
    author = "Lau, Tsz-Yam and Franklin, W. Randolph",
    title = "Better completion of fragmentary river networks with the induced terrain approach by using known non-river locations",
    booktitle = "15th International Symposium on Spatial Data Handling",
    year = "2012",
    address = "Bonn, Germany",
    month = "22--24 Aug",
    customlinkslides = "https://wrfranklin.org/p/157-sdh2012-completion-talk.ppt",
    mykey = "lau hydro",
    href = "\bibhrefpt{157-sdh2012-completion}{157-sdh2012-completion-talk.ppt}"
}

Mehrad Kamalzare, Thomas F. Zimmie, Christopher Stuetzle, Barbara Cutler, and W. Randolph Franklin. Computer simulation of levee's erosion and overtopping. In International Symposium on Environmental Geotechnology, Energy and Global Sustainable Development. Los Angeles, California, USA, June 2012.
[details] [full text]

BibTeX

@inproceedings{kalamzare-envir-2012,
    author = "Kamalzare, Mehrad and Zimmie, Thomas F. and Stuetzle, Christopher and Cutler, Barbara and Franklin, W. Randolph",
    title = "Computer simulation of levee's erosion and overtopping",
    booktitle = "International Symposium on Environmental Geotechnology, Energy and Global Sustainable Development",
    year = "2012",
    address = "Los Angeles, California, USA",
    month = "June",
    mykey = "levee stuetzle",
    href = "\bibhref{161-envirogeotech2012}"
}

Mehrad Kamalzare, Christopher Stuetzle, Zhongxian Chen, Thomas F. Zimmie, Barbara Cutler, and W. Randolph Franklin. Validation of erosion modeling: physical and numerical. In Geo-Congress 2012: Annual congress of the geo-institute of ASCE. Oakland, California, USA, 25–29 Mar 2012. \url http://www.geocongress2012.org/.
[details] [full text]

BibTeX

@inproceedings{kalamzare-geo-2012,
    author = "Kamalzare, Mehrad and Stuetzle, Christopher and Chen, Zhongxian and Zimmie, Thomas F. and Cutler, Barbara and Franklin, W. Randolph",
    title = "Validation of erosion modeling: physical and numerical",
    booktitle = "Geo-Congress 2012: Annual congress of the geo-institute of {ASCE}",
    year = "2012",
    address = "Oakland, California, USA",
    month = "25--29 Mar",
    note = "\url{http://www.geocongress2012.org/}",
    mykey = "levee stuetzle",
    href = "\bibhref{152-geocongress2012}"
}

Salles V. G. de Magalhães, Marcus V. A. Andrade, W. Randolph Franklin, and Guilherme C. Pena. A new method for computing the drainage network based on raising the level of an ocean surrounding the terrain. In Jérome Gensel, Didier Josselin, and Danny Vandenbroucke, editors, Bridging the Geographic Information Sciences: International AGILE'2012 Conference, pages 391–407. Springer, Avignon (France), 24–27 April 2012. URL: http://agile2012.imag.fr/.
[details] [full text] [slides]

BibTeX

@incollection{salles-agile-2012,
    author = "de Magalhães, Salles V. G. and Andrade, Marcus V. A. and Franklin, W. Randolph and Pena, Guilherme C.",
    editor = "Gensel, Jérome and Josselin, Didier and Vandenbroucke, Danny",
    title = "A new method for computing the drainage network based on raising the level of an ocean surrounding the terrain",
    booktitle = "Bridging the Geographic Information Sciences: International {AGILE'2012} Conference",
    publisher = "Springer",
    pages = "391--407",
    isbn = "978-3-642-29062-6",
    year = "2012",
    address = "Avignon (France)",
    month = "24--27 April",
    note = "Winner of the Best Paper Award (2nd place)",
    url = "http://agile2012.imag.fr/",
    customlinkslides = "https://wrfranklin.org/p/151-agile2012-rwflood-talk.pdf",
    href = "\bibhrefpt{151-agile2012-rwflood}{151-agile2012-rwflood-talk.pdf}",
    mykey = "salles marcus hydro rwflood sallesagile2012"
}

BibTeX

@incollection{salles-agile-2012-nonote,
    author = "de Magalhães, Salles V. G. and Andrade, Marcus V. A. and Franklin, W. Randolph and Pena, Guilherme C.",
    editor = "Gensel, Jérome and Josselin, Didier and Vandenbroucke, Danny",
    title = "A new method for computing the drainage network based on raising the level of an ocean surrounding the terrain",
    booktitle = "Bridging the Geographic Information Sciences: International {AGILE'2012} Conference",
    publisher = "Springer",
    pages = "391--407",
    isbn = "978-3-642-29062-6",
    year = "2012",
    address = "Avignon (France)",
    month = "24--27 April",
    url = "http://agile2012.imag.fr/",
    customlinkslides = "https://wrfranklin.org/p/151-agile2012-rwflood-talk.pdf",
    href = "\bibhrefpt{151-agile2012-rwflood}{151-agile2012-rwflood-talk.pdf}",
    mykey = "nonote salles marcus rwflood hydro"
}

2011

Tsz-Yam Lau, You Li, and W. Randolph Franklin. Joining fragmentary river segments with elevations and water flow directions using induced terrain (extended abstract). In 21st Fall Workshop on Computational Geometry. City College, New York City, USA, 4–5 Nov 2011.
[details] [full text]

BibTeX

@inproceedings{lau-fwcg-2011,
    author = "Lau, Tsz-Yam and Li, You and Franklin, W. Randolph",
    title = "Joining fragmentary river segments with elevations and water flow directions using induced terrain (extended abstract)",
    booktitle = "21st Fall Workshop on Computational Geometry",
    year = "2011",
    month = "4--5 Nov",
    address = "City College, New York City, USA",
    mykey = "youli lau hydro",
    href = "\bibhref{150-fwcg2011-lau}"
}

Christopher Stuetzle, Barbara Cutler, Zhongxian Chen, W. Randolph Franklin, Mehrad Kamalzare, and Thomas Zimmie. Ph.d. showcase: measuring terrain distances through extracted channel networks. In 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS 2011). Chicago USA, 1–4 Nov 2011.
[details] [full text] [poster]

BibTeX

@inproceedings{stuetzle-acmgis-2011,
    author = "Stuetzle, Christopher and Cutler, Barbara and Chen, Zhongxian and Franklin, W. Randolph and Kamalzare, Mehrad and Zimmie, Thomas",
    title = "Ph.D. showcase: Measuring terrain distances through extracted channel networks",
    booktitle = "19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS 2011)",
    year = "2011",
    month = "1--4 Nov",
    address = "Chicago USA",
    mykey = "terrain stuetzle levee",
    href = "\bibhrefpp{149-acmgis2011-stuetzle}{149-acmgis2011-stuetzle-poster.pdf}",
    customlinkposter = "https://wrfranklin.org/p/149-acmgis2011-stuetzle-poster.pdf"
}

Tsz-Yam Lau and W. Randolph Franklin. Completing fragmentary river networks via induced terrain. Cartography and Geographic Information Science, 38(2):162–174, April 2011. URL: https://www.tandfonline.com/doi/abs/10.1559/15230406382161a, doi:https://doi.org/10.1559/15230406382161a.
[details] [full text]
Abstract
Fragmentary river segments have to be reconnected before addressing various routing and tracking problems. Elevation determines drainage directions, so the partial heights available through LiDAR may provide useful hints on how the segments should be joined. However, it is not trivial how this information can be applied. This paper bridges this gap by proposing the induced structure approach, which first approximates a terrain compatible with those observations, and then derives a river network from that induced terrain. Since the network is derived from an induced terrain that honors the partial observations, we expect that the derived river network will enforce most restrictions imposed by the partial observations. This paper also provides specifics on the implementation. In the first step regarding terrain reconstruction, we find that the optimal scheme depends on the height sample distribution. If the samples are sparsely yet evenly distributed, natural neighbor interpolation with stream burning (NN-SB) is the most cost-effective. If the samples are offered only at the given river locations, the hydrology-aware version of Over determined Palladian Partial Differential Equation (HA-ODETLAP) should be used instead. In the second step concerning river derivation, we find it necessary to favor those given river locations. Otherwise they will be missed out. We set their respective initial water amounts to the critical accumulation level to ensure a river flows across them. In the subsequent branch thinning process, those locations are protected from being trimmed. We foresee applications of our solution framework in a few 2D and 3D network tracing problems with similar observation distribution, like dendrite network reconstruction.
BibTeX
```
@article{lau-cagis-2011,
    author = "Lau, Tsz-Yam and Franklin, W. Randolph",
    title = "Completing fragmentary river networks via induced terrain",
    journal = "Cartography and Geographic Information Science",
    year = "2011",
    month = "April",
    pages = "162-174",
    volume = "38",
    number = "2",
    doi = "https://doi.org/10.1559/15230406382161a",
    url = "https://www.tandfonline.com/doi/abs/10.1559/15230406382161a",
    mykey = "lau hydro",
    href = "\bibhref{147-cagis-hydro-lau}"
}
```

Mehrad Kamalzare, Zhongxian Chen, Christopher Stuetzle, Barbara Cutler, W. Randolph Franklin, and Thomas F. Zimmie. Computer simulation of overtopping of levees. In 2011 Pam-Am CGS Geotechnical Conference: 14th Pan-American Conference on Soil Mechanics and Geotechnical Engineering. Toronto, 2–6 Oct 2011. URL: http://www.panam-cgc2011.ca/.
[details] [full text]

BibTeX

@inproceedings{panam-2011,
    author = "Kamalzare, Mehrad and Chen, Zhongxian and Stuetzle, Christopher and Cutler, Barbara and Franklin, W. Randolph and Zimmie, Thomas F.",
    title = "Computer simulation of overtopping of levees",
    booktitle = "2011 {Pam-Am} {CGS} Geotechnical Conference: 14th Pan-American Conference on Soil Mechanics and Geotechnical Engineering",
    month = "2--6 Oct",
    year = "2011",
    address = "Toronto",
    url = "http://www.panam-cgc2011.ca/",
    mykey = "levee stuetzle",
    href = "\bibhref{146-panam-levees}"
}

W. Randolph Franklin. The RPI GeoStar project. In Anne Ruas, editor, Proceedings of the 25th International Cartographic Conference. Paris, 3–8 July 2011. online, retrieved 26-Oct-13. URL: http://icaci.org/files/documents/ICC_proceedings/ICC2011/.
[details] [full text] [slides]

BibTeX

@inproceedings{icc-2011,
    author = "Franklin, W. Randolph",
    editor = "Ruas, Anne",
    title = "The {RPI} {GeoStar} project",
    booktitle = "Proceedings of the 25th International Cartographic Conference",
    year = "2011",
    address = "Paris",
    isbn = "978-1-907075-05-6",
    month = "3--8 July",
    url = "http://icaci.org/files/documents/ICC\_proceedings/ICC2011/",
    mykey = "geostar",
    note = "online, retrieved 26-Oct-13",
    customlinkslides = "https://wrfranklin.org/p/145-icc2011-geostar-talk.pdf",
    href = "\bibhrefpt{145-icc2011-geostar}{145-icc2011-geostar-talk.pdf}"
}

Zhongxian Chen, Christopher S. Stuetzle, Barbara M. Cutler, Jared A. Gross, W. Randolph Franklin, and Thomas F. Zimmie. Analyses, simulations and physical modeling validation of levee and embankment erosion. In Geo-Frontiers 2011: Advances in geotechnical engineering. Dallas TX, 13–16 Mar 2011. URL: http://www.geofrontiers11.com/.
[details] [full text]

BibTeX

@inproceedings{chen-geofrontiers-2011,
    author = "Chen, Zhongxian and Stuetzle, Christopher S. and Cutler, Barbara M. and Gross, Jared A. and Franklin, W. Randolph and Zimmie, Thomas F.",
    title = "Analyses, Simulations and Physical Modeling Validation of Levee and Embankment Erosion",
    booktitle = "Geo-Frontiers 2011: Advances in geotechnical engineering",
    year = "2011",
    address = "Dallas TX",
    month = "13--16 Mar",
    href = "\bibhref{141-geofrontiers2011-analyses-chen}",
    mykey = "levee stuetzle",
    url = "http://www.geofrontiers11.com/"
}

Salles V. G. de Magalhães, Marcus V. A. Andrade, and W. Randolph Franklin. Multiple observer siting in huge terrains stored in external memory. International Journal of Computer Information Systems and Industrial Management (IJCISIM), 2011.
[details] [full text]
Abstract
This paper presents an heuristic method to give an approximated solution to the observer siting problem on high resolution terrains that are too large to be processed in the internal memory. Informally, the problem is to determine an optimal positioning of as few as possible observers for being able to observe as many target points as possible. Tests have shown that the proposed heuristic can solve this problem using, on average, fifteen percent fewer observers than another heuristic described in the literature. This will permit more efficient positioning of facilities such as mobile phone towers, fire observation towers, and vigilance systems.
BibTeX
```
@article{magalhaes-ijcisim-2011,
    author = "de Magalhães, Salles V. G. and Andrade, Marcus V. A. and Franklin, W. Randolph",
    title = "Multiple Observer Siting in Huge Terrains Stored in External Memory",
    journal = "International Journal of Computer Information Systems and Industrial Management (IJCISIM)",
    year = "2011",
    volume = "3",
    issn = "2150-7988",
    href = "\bibhref{148-ijcisim11-emsite-magalhaes}",
    mykey = "visviewshedsiting marcus salles"
}
```

2010

Tsz-Yam Lau and W. Randolph Franklin. Completing river networks with only partial river observations via hydrology-aware ODETLAP. In 20th Annual Fall Workshop on Computational Geometry (FWCG 2010). Stony Brook University, Stony Brook, NY 11794, USA, 29–30 Oct 2010. (extended abstract and talk).
[details] [full text] [slides]

BibTeX

@inproceedings{lau-fwcg-2010,
    author = "Lau, Tsz-Yam and Franklin, W. Randolph",
    title = "Completing River Networks with Only Partial River Observations via Hydrology-Aware {ODETLAP}",
    booktitle = "20th Annual Fall Workshop on Computational Geometry ({FWCG} 2010)",
    month = "29--30 Oct",
    year = "2010",
    note = "(extended abstract and talk)",
    mykey = "lau hydro odetlap",
    address = "Stony Brook University, Stony Brook, NY 11794, USA",
    customlinkslides = "https://wrfranklin.org/p/138-fwcg2010-lau-talk.pdf",
    href = "\bibhrefat{138-fwcg2010-lau}{138-fwcg2010-lau-talk.pdf}"
}

W. Randolph Franklin. Towards a mathematics of terrain. In 20th Annual Fall Workshop on Computational Geometry (FWCG 2010). Stony Brook University, Stony Brook, NY 11794, USA, 29–30 Oct 2010. (extended abstract and talk).
[details] [full text] [slides]

BibTeX

@inproceedings{terrain-fwcg-2010,
    author = "Franklin, W. Randolph",
    title = "Towards a Mathematics of Terrain",
    booktitle = "20th Annual Fall Workshop on Computational Geometry ({FWCG} 2010)",
    month = "29--30 Oct",
    year = "2010",
    note = "(extended abstract and talk)",
    address = "Stony Brook University, Stony Brook, NY 11794, USA",
    customlinkslides = "https://wrfranklin.org/p/144-fwcg2010-terrain-talk.pdf",
    mykey = "terrain",
    href = "\bibhrefat{144-fwcg2010-terrain}{144-fwcg2010-terrain-talk.pdf}"
}

W. Randolph Franklin and Barb Cutler. KNOWMESH – meshless geometry with knowledge representation. In DARPA GRID2 workshop. 18–19 Aug 2010.
[details] [slides]

BibTeX

@inproceedings{grid-2010,
    author = "Franklin, W. Randolph and Cutler, Barb",
    title = "{KNOWMESH} -- Meshless geometry with knowledge representation",
    booktitle = "{DARPA GRID2} workshop",
    year = "2010",
    customlinkslides = "https://wrfranklin.org/p/142-darpa-knowmesh-talk.pdf",
    href = "\bibhreft{142-darpa-knowmesh-talk.pdf}",
    month = "18--19 Aug"
}

Jared A. Gross, Christopher S. Stuetzle, Zhongxian Chen, Barbara Cutler, W. Randolph Franklin, and Thomas F. Zimmie. Simulating levee erosion with physical modeling validation. In ICSE-5 5th international conference on scour and erosion. San Francisco, 7–10 Nov 2010.
[details] [full text] [slides]

BibTeX

@inproceedings{gross-icse-2010,
    author = "Gross, Jared A. and Stuetzle, Christopher S. and Chen, Zhongxian and Cutler, Barbara and Franklin, W. Randolph and Zimmie, Thomas F.",
    title = "Simulating levee erosion with physical modeling validation",
    booktitle = "{ICSE-5} 5th international conference on scour and erosion",
    year = "2010",
    address = "San Francisco",
    month = "7--10 Nov",
    customlinkslides = "https://wrfranklin.org/p/134-icse2010-gross-talk.ps",
    href = "\bibhrefpt{134-icse2010-gross}{134-icse2010-gross-talk.ps}",
    mykey = "levee stuetzle"
}

W. Randolph Franklin, Zhongyi Xie, Eddie Lau, and You Li. Algorithms for terrain and bathymetric sensor data. In ICA Workshop on Advances in Sensors and Algorithms for Topographic and Thematic Mapping. Orlando, Florida, 19 Nov 2010. The International Cartographic Association (ICA) Commission on Mapping from Satellite Imagery.
[details] [full text] [slides]

BibTeX

@inproceedings{ica-2010,
    author = "Franklin, W. Randolph and Xie, Zhongyi and Lau, Eddie and Li, You",
    title = "Algorithms for terrain and bathymetric sensor data",
    booktitle = "{ICA} Workshop on Advances in Sensors and Algorithms for Topographic and Thematic Mapping",
    year = "2010",
    address = "Orlando, Florida",
    month = "19 Nov",
    organization = "The {International} Cartographic Association {(ICA)} Commission on Mapping from Satellite Imagery",
    customlinkslides = "https://wrfranklin.org/p/143-orlando-ica-sensors-2010-talk.pdf",
    mykey = "xie youli lau bathy",
    href = "\bibhrefpt{143-orlando-ica-sensors-2010}{143-orlando-ica-sensors-2010-talk.pdf}"
}

Tsz-Yam Lau and W. Randolph Franklin. Completing fragmentary river networks via induced terrain. In Geospatial Data and Geovisualization: Environment, Security, and Society, a special joint symposium of ISPRS Technical Commission IV & AutoCarto 2010. Orlando, Florida, 15–18 Nov 2010.
[details] [full text] [slides]

BibTeX

@inproceedings{lau-autocarto-2010,
    author = "Lau, Tsz-Yam and Franklin, W. Randolph",
    title = "Completing fragmentary river networks via induced terrain",
    booktitle = "Geospatial Data and Geovisualization: Environment, Security, and Society, a special joint symposium of {ISPRS} Technical Commission {IV} \\& {AutoCarto} 2010",
    year = "2010",
    address = "Orlando, Florida",
    month = "15--18 Nov",
    mykey = "lau hydro",
    customlinkslides = "https://wrfranklin.org/p/135-autocarto2010-lau-talk.pptx",
    href = "\bibhrefpt{135-autocarto2010-lau}{135-autocarto2010-lau-talk.pptx}"
}

You Li and W. Randolph Franklin. 4D-ODETLAP: a novel high-dimensional compression method on time-varying geospatial data. In Geospatial Data and Geovisualization: Environment, Security, and Society, a special joint symposium of ISPRS Technical Commission IV & AutoCarto 2010. Orlando, Florida, 15–18 Nov 2010.
[details] [full text] [slides]

BibTeX

@inproceedings{li-autocarto-2010,
    author = "Li, You and Franklin, W. Randolph",
    title = "{4D-ODETLAP}: A Novel High-dimensional Compression Method on Time-varying Geospatial Data",
    booktitle = "Geospatial Data and Geovisualization: Environment, Security, and Society, a special joint symposium of {ISPRS} Technical Commission {IV} \\& {AutoCarto} 2010",
    year = "2010",
    address = "Orlando, Florida",
    mykey = "youli odetlap",
    month = "15--18 Nov",
    customlinkslides = "https://wrfranklin.org/p/136-autocarto2010-li-talk.pptx",
    href = "\bibhrefpt{136-autocarto2010-li}{136-autocarto2010-li-talk.pptx}"
}

Zhongxian Chen, Christopher Stuetzle, Barbara Cutler, Jared Gross, W. Randolph Franklin, and Thomas Zimmie. Quantitative analysis of simulated erosion for different soils. In 18th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS 2010). San Jose, CA, USA, 2–5 Nov 2010. (poster).
[details] [full text] [poster]

BibTeX

@inproceedings{chen-acmgis-2010,
    author = "Chen, Zhongxian and Stuetzle, Christopher and Cutler, Barbara and Gross, Jared and Franklin, W. Randolph and Zimmie, Thomas",
    title = "Quantitative analysis of simulated erosion for different soils",
    booktitle = "18th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS 2010)",
    year = "2010",
    month = "2--5 Nov",
    address = "San Jose, CA, USA",
    href = "\bibhrefpp{137-acmgis2010-chen}{137-acmgis2010-chen-poster.pdf}",
    customlinkposter = "https://wrfranklin.org/p/137-acmgis2010-chen-poster.pdf",
    mykey = "levee stuetzle",
    note = "(poster)"
}

You Li, Tsz-Yam Lau, Chris Stuetzle, Peter Fox, and W. Randolph Franklin. 3D oceanographic data compression using 3D-ODETLAP. In 18th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS 2010). San Jose, CA, USA, 2–5 Nov 2010. (PhD Dissertation showcase).
[details] [full text] [slides]

BibTeX

@inproceedings{li-acmgis-2010,
    author = "Li, You and Lau, Tsz-Yam and Stuetzle, Chris and Fox, Peter and Franklin, W. Randolph",
    title = "{3D} oceanographic data compression using {3D-ODETLAP}",
    booktitle = "18th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS 2010)",
    year = "2010",
    month = "2--5 Nov",
    mykey = "youli odetlap lau stuetzle",
    address = "San Jose, CA, USA",
    customlinkslides = "https://wrfranklin.org/p/139-acmgis2010-li-talk.pptx",
    href = "\bibhrefpt{139-acmgis2010-li}{139-acmgis2010-li-talk.pptx}",
    note = "(PhD Dissertation showcase)"
}

Zhongyi Xie, W. Randolph Franklin, and Dan Tracy. Slope preserving lossy terrain compression. In 18th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS 2010). San Jose, CA, USA, 2–5 Nov 2010. (PhD Dissertation Showcase).
[details] [full text] [poster]

BibTeX

@inproceedings{xie-acmgis-2010,
    author = "Xie, Zhongyi and Franklin, W. Randolph and Tracy, Dan",
    title = "Slope Preserving Lossy Terrain Compression",
    booktitle = "18th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS 2010)",
    year = "2010",
    month = "2--5 Nov",
    address = "San Jose, CA, USA",
    href = "\bibhrefpp{140-acmgis2010-xie}{140-acmgis2010-xie-poster.pdf}",
    customlinkposter = "https://wrfranklin.org/p/140-acmgis2010-xie-poster.pdf",
    mykey = "tracy xie terrain",
    note = "(PhD Dissertation Showcase)"
}

Christopher S. Stuetzle, Zhongxian Chen, Barbara Cutler, W. Randolph Franklin, Jared Gross, Katrina Perez, and Thomas Zimmie. Computer simulations and physical modelling of erosion. In 7th International Conference on Physical Modelling in Geotechnics (ICPMG 2010). Zürich, 20–24 Jun 2010.
[details] [full text] [slides]

BibTeX

@inproceedings{stuetzle-icpmg-2010,
    author = "Stuetzle, Christopher S. and Chen, Zhongxian and Cutler, Barbara and Franklin, W. Randolph and Gross, Jared and Perez, Katrina and Zimmie, Thomas",
    title = "Computer simulations and physical modelling of erosion",
    booktitle = "7th International Conference on Physical Modelling in Geotechnics ({ICPMG} 2010)",
    year = "2010",
    address = "Zürich",
    customlinkslides = "https://wrfranklin.org/p/131-zurich2010-stuetzle-talk.pdf",
    href = "\bibhrefpt{131-zurich2010-stuetzle}{131-zurich2010-stuetzle-talk.pdf}",
    mykey = "levee stuetzle",
    month = "20--24 Jun"
}

W. Randolph Franklin. Parallel volume computation of the union of many cubes. (rejected), 2010.
[details]

BibTeX

@unpublished{union-2010,
    author = "Franklin, W. Randolph",
    title = "Parallel Volume Computation of the Union of Many Cubes",
    note = "(rejected)",
    year = "2010"
}

Salles V. G. de Magalhães, Marcus V. A. Andrade, and W. Randolph Franklin. An optimization heuristic for siting observers in huge terrains stored in external memory. In 10th International Conference on Hybrid Intelligent Systems (HIS 2010). Atlanta USA, 23–25 Aug 2010.
[details] [full text]

BibTeX

@inproceedings{magalhaes-his-2010,
    author = "de Magalhães, Salles V. G. and Andrade, Marcus V. A. and Franklin, W. Randolph",
    title = "An optimization heuristic for siting observers in huge terrains stored in external memory",
    booktitle = "10th International Conference on Hybrid Intelligent Systems ({HIS} 2010)",
    address = "Atlanta USA",
    month = "23--25 Aug",
    year = "2010",
    href = "\bibhref{132-atlanta-his10-emsite-magalhaes}",
    mykey = "marcus salles"
}

Marcus V. A. Andrade, Salles V. G. de Magalhães, Mirella A. de Magalhães, W. Randolph Franklin, and Barbara M. Cutler. Efficient viewshed computation on terrain in external memory. Geoinformatica, 2010. (online 26 Nov 2009). URL: http://www.springerlink.com/content/p1783648185g1252/, doi:https://doi.org/10.1007/s10707-009-0100-9.
[details] [full text]
Abstract
The recent availability of detailed geographic data permits terrain applications to process large areas at high resolution. However the required massive data processing presents significant challenges, demanding algorithms optimized for bothdata movement and computation. One such application is viewshed computation,that is, to determine all the points visible from a given point p. In this paper, we present an efficient algorithm to compute viewsheds on terrain stored in external memory. In the usual case where the observer's radius of interest is smaller than the terrain size, the algorithm complexity is θ(scan(n2)) where n2 is the number of points in an n×n DEM and scan(n2)is the minimum number of I/O operations required to read n2 contiguous items from external memory. This is much faster than existing published algorithms.
BibTeX
```
@article{andrade-geoinfo-ext-viewshed-2008,
    author = "Andrade, Marcus V. A. and de Magalhães, Salles V. G. and de Magalhães, Mirella A. and Franklin, W. Randolph and Cutler, Barbara M.",
    title = "Efficient viewshed computation on terrain in external memory",
    journal = "Geoinformatica",
    year = "2010",
    href = "\bibhref{126-andrade-geoinfo-ext-viewshed-2008}",
    URL = "http://www.springerlink.com/content/p1783648185g1252/",
    DOI = "https://doi.org/10.1007/s10707-009-0100-9",
    mykey = "visviewshedsiting marcus salles",
    note = "(online 26 Nov 2009)"
}
```

W. Randolph Franklin. ECSE-4750 Computer graphics. 2010. accessed 15-Dec-2010. URL: https://wrfranklin.org/pmwiki/ComputerGraphicsFall2010/.
[details]

BibTeX

@misc{ecse4750,
    author = "Franklin, W. Randolph",
    title = "{ECSE-4750} {C}omputer Graphics",
    url = "https://wrfranklin.org/pmwiki/ComputerGraphicsFall2010/",
    note = "accessed 15-Dec-2010",
    year = "2010"
}

2009

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. In 19th Fall Workshop on Computational Geometry (FWCG 2009). Tufts University, Medford MA USA, 13–14 Nov 2009. (extended abstract and talk).
[details] [full text] [slides]

BibTeX

@inproceedings{stuetzle-fwcg-2009,
    author = "Stuetzle, Christopher S. and Chen, Zhongxian and Perez, Katrina and Gross, Jared and Cutler, Barbara and Franklin, W. Randolph and Zimmie, Thomas",
    title = "Segmented Height Field and Smoothed Particle Hydrodynamics in Erosion Simulation",
    booktitle = "19th Fall Workshop on Computational Geometry ({FWCG} 2009)",
    month = "13--14 Nov",
    year = "2009",
    note = "(extended abstract and talk)",
    address = "Tufts University, Medford MA USA",
    customlinkslides = "https://wrfranklin.org/p/130-fwcg2009-stuetzle-talk.pdf",
    href = "\bibhrefat{130-fwcg2009-stuetzle}{130-fwcg2009-stuetzle-talk.pdf}",
    mykey = "levee hydro stuetzle"
}

Tsz-Yam Lau, You Li, Zhongyi Xie, and W. Randolph Franklin. Sea floor bathymetry trackline surface fitting without visible artifacts using ODETLAP. In 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS 2009). Seattle WA USA, 4–6 Nov 2009. Winner of the best fast forward presentation award.
[details] [full text] [slides] [poster] [video] [award]

BibTeX

@inproceedings{lau-acmgis-2009,
    author = "Lau, Tsz-Yam and Li, You and Xie, Zhongyi and Franklin, W. Randolph",
    title = "Sea Floor Bathymetry Trackline Surface Fitting Without Visible Artifacts Using {ODETLAP}",
    booktitle = "17th {ACM SIGSPATIAL} International Conference on Advances in Geographic Information Systems ({ACM SIGSPATIAL GIS} 2009)",
    year = "2009",
    address = "Seattle WA USA",
    month = "4--6 Nov",
    note = "Winner of the best fast forward presentation award",
    customlinkslides = "https://wrfranklin.org/p/129-acmgis2009-lau-talk.pdf",
    customlinkposter = "https://wrfranklin.org/p/129-acmgis2009-lau-poster.pdf",
    customlinkvideo = "https://wrfranklin.org/p/129-acmgis2009-lau-video.avi",
    customlinkaward = "https://wrfranklin.org/p/129-acmgis2009-lau-ffaward.jpg",
    href = "\bibhrefpttppv{129-acmgis2009-lau}",
    mykey = "xie youli odetlap bathy lauacmgis2009"
}

Tsz-Yam Lau, You Li, Zhongyi Xie, and W. Randolph Franklin. Sea floor bathymetry trackline surface fitting without visible artifacts using ODETLAP. In 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS 2009). Seattle WA USA, 4–6 Nov 2009.
[details] [full text] [slides] [poster] [video] [award]

BibTeX

@inproceedings{lau-acmgis-2009-nonote,
    author = "Lau, Tsz-Yam and Li, You and Xie, Zhongyi and Franklin, W. Randolph",
    title = "Sea Floor Bathymetry Trackline Surface Fitting Without Visible Artifacts Using {ODETLAP}",
    booktitle = "17th {ACM SIGSPATIAL} International Conference on Advances in Geographic Information Systems ({ACM SIGSPATIAL GIS} 2009)",
    year = "2009",
    address = "Seattle WA USA",
    month = "4--6 Nov",
    customlinkslides = "https://wrfranklin.org/p/129-acmgis2009-lau-talk.pdf",
    customlinkposter = "https://wrfranklin.org/p/129-acmgis2009-lau-poster.pdf",
    customlinkvideo = "https://wrfranklin.org/p/129-acmgis2009-lau-video.avi",
    customlinkaward = "https://wrfranklin.org/p/129-acmgis2009-lau-ffaward.jpg",
    href = "\bibhrefpttppv{129-acmgis2009-lau}",
    mykey = "nonote youli xie lau odetlap bathy"
}

W. Randolph Franklin. Geostar. March 2009. URL: https://wrfranklin.org/pmwiki/Research/GeoStar.
[details]

BibTeX

@misc{geostar-web,
    author = "Franklin, W. Randolph",
    title = "GeoStar",
    month = "March",
    year = "2009",
    url = "https://wrfranklin.org/pmwiki/Research/GeoStar"
}

W. Randolph Franklin. Final report – Geologically correct terrain data structures and radar siting, HM1582-05-2-0002. March 2009.
[details] [full text]

BibTeX

@misc{darpa-geostar-final-2009,
    author = "Franklin, W. Randolph",
    title = "Final report -- {Geologically} Correct Terrain Data Structures and Radar Siting, {HM1582-05-2-0002}",
    month = "March",
    year = "2009",
    mykey = "terrain geostar",
    href = "\bibhref{243-darpa-geostar-final-2009}"
}

W. Randolph Franklin. PNPOLY - point inclusion in polygon test. 2009. accessed 31-Dec-2009. URL: https://wrfranklin.org/Research/Short_Notes/pnpoly.html.
[details]

BibTeX

@misc{pnpoly,
    author = "Franklin, W. Randolph",
    title = "{PNPOLY} - Point Inclusion in Polygon Test",
    url = "https://wrfranklin.org/Research/Short\_Notes/pnpoly.html",
    note = "accessed 31-Dec-2009",
    year = "2009"
}

W. Randolph Franklin. PNPOLY - point inclusion in polygon test. 2009. \url https://wrfranklin.org/Research/Short_Notes/pnpoly.html, accessed 31-Dec-2009.
[details]

BibTeX

@misc{pnpoly-url,
    author = "Franklin, W. Randolph",
    title = "{PNPOLY} - Point Inclusion in Polygon Test",
    note = "\url{https://wrfranklin.org/Research/Short\_Notes/pnpoly.html}, accessed 31-Dec-2009",
    year = "2009"
}

W. Randolph Franklin. ECSE-6800 Advanced computer graphics and visualization. \url https://wrfranklin.org/pmwiki/AdvancedComputerGraphicsSpring2009/ [accessed 31-Dec-2009], 2009.
[details]

BibTeX

@misc{ecse6800,
    author = "Franklin, W. Randolph",
    title = "{ECSE-6800} {A}dvanced Computer Graphics and Visualization",
    howpublished = "\url{https://wrfranklin.org/pmwiki/AdvancedComputerGraphicsSpring2009/} [accessed 31-Dec-2009]",
    year = "2009"
}

2008

Jared Stookey, Zhongyi Xie, Barbara Cutler, W. Randolph Franklin, Daniel M. Tracy, and Marcus V.A. Andrade. Parallel ODETLAP for terrain compression and reconstruction. In Walid G. Aref, editor, 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS 2008). 5–7 Nov 2008. URL: http://acmgis08.cs.umn.edu/.
[details] [full text] [slides] [poster]
Abstract
We introduce a parallel approximation of an Over-determined Laplacian Partial Differential Equation solver (ODETLAP) applied to the compression and restoration of terrain data used for Geographical Information Systems (GIS). ODETLAP can be used to reconstruct a compressed elevation map, or to generate a dense regular grid from airborne Light Detection and Ranging (LIDAR) point cloud data. With previous methods, the time to execute ODETLAP does not scale well with the size of the input elevation map, resulting in running times that are prohibitively long for large data sets. Our algorithm divides the data set into patches, runs ODETLAP on each patch, and then merges the patches together. This method gives two distinct speed improvements. First, we provide scalability by reducing the complexity such that the execution time grows almost linearly with the size of the input, even when run on a single processor. Second, we are able to calculate ODETLAP on the patches concurrently in a parallel or distributed environment. Our new patchbased implementation takes 2 seconds to run ODETLAP on an 800 × 800 elevation map using 128 processors, while the original version of ODETLAP takes nearly 10 minutes on a single processor (271 times longer). We demonstrate the effectiveness of the new algorithm by running it on data sets as large as 16000 × 16000 on a cluster of computers. We also discuss our preliminary results from running on an IBM Blue Gene/L system with 32,768 processors.
BibTeX
```
@inproceedings{stookey-acmgis-2008,
    author = "Stookey, Jared and Xie, Zhongyi and Cutler, Barbara and Franklin, W. Randolph and Tracy, Daniel M. and Andrade, Marcus V.A.",
    editor = "Aref, Walid G.",
    title = "Parallel {ODETLAP} for terrain compression and reconstruction",
    booktitle = "16th {ACM SIGSPATIAL} International Conference on Advances in Geographic Information Systems ({ACM GIS} 2008)",
    year = "2008",
    location = "Irvine CA",
    month = "5--7 Nov",
    href = "\bibhrefptp{123-acmgis2008-stookey}{123-acmgis2008-stookey-talk.ppt}{123-acmgis2008-stookey-poster.ppt}",
    url = "http://acmgis08.cs.umn.edu/",
    customlinkslides = "https://wrfranklin.org/p/123-acmgis2008-stookey-talkb.pdf",
    customlinkposter = "https://wrfranklin.org/p/123-acmgis2008-stookey-poster.ppt",
    mykey = "odetlap tracy marcus xie stuetzle parallel"
}
```

Daniel M. Tracy, W. Randolph Franklin, Barbara Cutler, Franklin T. Luk, Marcus Andrade, and Jared Stookey. Path planning on a compressed terrain. In Walid G. Aref and others, editors, 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS 2008). Irvine CA, 5–7 Nov 2008. (poster and fast forward presentation). URL: http://acmgis08.cs.umn.edu/.
[details] [full text] [slides] [poster]

BibTeX

@inproceedings{tracy-acmgis-2008,
    author = "Tracy, Daniel M. and Franklin, W. Randolph and Cutler, Barbara and Luk, Franklin T. and Andrade, Marcus and Stookey, Jared",
    editor = "Aref, Walid G. and others",
    title = "Path Planning on a Compressed Terrain",
    booktitle = "16th {ACM SIGSPATIAL} International Conference on Advances in Geographic Information Systems ({ACM GIS} 2008)",
    year = "2008",
    address = "Irvine CA",
    month = "5--7 Nov",
    customlinkslides = "https://wrfranklin.org/p/124-acmgis2008-tracy-talk.pdf",
    customlinkposter = "https://wrfranklin.org/p/124-acmgis2008-tracy-poster.pdf",
    mykey = "pathplan marcus tracy",
    href = "\bibhrefpttpp{124-acmgis2008-tracy}",
    note = "(poster and fast forward presentation)",
    url = "http://acmgis08.cs.umn.edu/"
}

Christopher Stuetzle, W. Randolph Franklin, Barbara Cutler, Jonathan Muckell, Marcus Andrade, Jared Stookey, Metin Inanc, and Zhongyi Xie. Evaluating hydrology preservation of simplified terrain representations. In Walid G. Aref and others, editors, 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS 2008). Irvine CA, 5–7 Nov 2008. (PhD student poster and fast forward presentation). URL: http://acmgis08.cs.umn.edu/.
[details] [slides] [poster]

BibTeX

@inproceedings{muckell-acmgis-2008,
    author = "Stuetzle, Christopher and Franklin, W. Randolph and Cutler, Barbara and Muckell, Jonathan and Andrade, Marcus and Stookey, Jared and Inanc, Metin and Xie, Zhongyi",
    editor = "Aref, Walid G. and others",
    title = "Evaluating Hydrology Preservation of Simplified Terrain Representations",
    booktitle = "16th {ACM SIGSPATIAL} International Conference on Advances in Geographic Information Systems ({ACM GIS} 2008)",
    year = "2008",
    address = "Irvine CA",
    month = "5--7 Nov",
    mykey = "inanc muckell marcus xie terrain hydro",
    customlinkslides = "https://wrfranklin.org/p/125-acmgis2008-muckell-talk.ppt",
    customlinkposter = "https://wrfranklin.org/p/125-acmgis2008-muckell-poster.ppt",
    href = "\bibhreftp{125-acmgis2008-muckell-talk.ppt}{125-acmgis2008-muckell-poster.ppt}",
    note = "(PhD student poster and fast forward presentation)",
    url = "http://acmgis08.cs.umn.edu/"
}

Daniel M. Tracy, W Randolph Franklin, Barb Cutler, Franklin Luk, Marcus Andrade, and Jared Stookey. Path planning on complex terrain. In 18th Fall Workshop on Computational Geometry (FWCG 2008). Rensselaer Polytechnic Institute, Troy NY USA, 31 Oct – 1 Nov 2008. (extended abstract, talk and poster).
[details] [full text] [slides] [poster]

BibTeX

@inproceedings{tracy-fwcg-2008,
    author = "Tracy, Daniel M. and Franklin, W Randolph and Cutler, Barb and Luk, Franklin and Andrade, Marcus and Stookey, Jared",
    title = "Path Planning on Complex Terrain",
    booktitle = "18th Fall Workshop on Computational Geometry ({FWCG} 2008)",
    month = "31 Oct -- 1 Nov",
    year = "2008",
    note = "(extended abstract, talk and poster)",
    address = "Rensselaer Polytechnic Institute, Troy NY USA",
    customlinkslides = "https://wrfranklin.org/p/128-fwcg2008-tracy-talk.ppt",
    customlinkposter = "https://wrfranklin.org/p/128-fwcg2008-tracy-poster.ppt",
    mykey = "pathplan marcus tracy",
    href = "\bibhrefatp{128-fwcg2008-tracy}{128-fwcg2008-tracy-talk.ppt}{128-fwcg2008-tracy-poster.ppt}"
}

W. Randolph Franklin. Operating on large geometric datasets. In 18th Fall Workshop on Computational Geometry. Rensselaer Polytechnic Institute, Troy NY, 31 Oct – 1 Nov 2008. (extended abstract and talk).
[details] [full text] [slides]

BibTeX

@inproceedings{wrf-fwcg-2008,
    author = "Franklin, W. Randolph",
    title = "Operating on large geometric datasets",
    booktitle = "18th Fall Workshop on Computational Geometry",
    month = "31 Oct -- 1 Nov",
    year = "2008",
    note = "(extended abstract and talk)",
    address = "Rensselaer Polytechnic Institute, Troy NY",
    customlinkslides = "https://wrfranklin.org/p/122-fwcg2008-big-talk.pdf",
    href = "\bibhrefat{122-fwcg2008-big}{122-fwcg2008-big-talk.pdf}"
}

Zhongyi Xie, Marcus A. Andrade, W Randolph Franklin, Barbara Cutler, Metin Inanc, Jonathan Muckell, and Daniel M. Tracy. Progressive transmission of lossily compressed terrain. In CLEI 2008 Conferencia Latinoamericana de Informática. Santa Fe, Argentina, 8–12 Sep 2008.
[details] [full text]

BibTeX

@inproceedings{andrade-prog-trans-2008,
    author = "Xie, Zhongyi and Andrade, Marcus A. and Franklin, W Randolph and Cutler, Barbara and Inanc, Metin and Muckell, Jonathan and Tracy, Daniel M.",
    title = "Progressive Transmission of Lossily Compressed Terrain",
    booktitle = "{CLEI 2008} Conferencia Latinoamericana de Informática",
    year = "2008",
    address = "Santa Fe, Argentina",
    month = "8--12 Sep",
    href = "\bibhref{127-andrade-prog-trans-2008}",
    mykey = "marcus tracy inanc muckell xie terrain"
}

Jonathan Muckell, Marcus Andrade, W. Randolph Franklin, Barbara Cutler, Metin Inanc, Zhongyi Xie, and Daniel M. Tracy. Hydrology-aware constrained triangulation of terrain data. (unpublished), Apr 2008.
[details] [full text]

BibTeX

@unpublished{muckell-HydroTIN-2008,
    author = "Muckell, Jonathan and Andrade, Marcus and Franklin, W. Randolph and Cutler, Barbara and Inanc, Metin and Xie, Zhongyi and Tracy, Daniel M.",
    title = "Hydrology-Aware Constrained Triangulation of Terrain Data",
    mykey = "inanc marcus muckell xie tracy hydro",
    href = "\bibhref{120-muckell-HydroTIN-2008}",
    note = "(unpublished)",
    month = "Apr",
    year = "2008"
}

Jonathan Muckell, Marcus Andrade, W. Randolph Franklin, Barbara Cutler, Metin Inanc, Zhongyi Xie, and Daniel M. Tracy. Evaluating hydrology preservation of simplified terrain representations. (unpublished), Apr 2008.
[details] [full text]

BibTeX

@unpublished{muckell-HydroMetric-ODETLAP-2008,
    author = "Muckell, Jonathan and Andrade, Marcus and Franklin, W. Randolph and Cutler, Barbara and Inanc, Metin and Xie, Zhongyi and Tracy, Daniel M.",
    title = "Evaluating Hydrology Preservation of Simplified Terrain Representations",
    href = "\bibhref{121-muckell-HydroMetric-ODETLAP-2008}",
    note = "(unpublished)",
    month = "Apr",
    mykey = "odetlap tracy inanc marcus muckell xie hydro",
    year = "2008"
}

W. Randolph Franklin, Daniel M. Tracy, Marcus Andrade, Jonathan Muckell, Metin Inanc, Zhongyi Xie, and Barbara Cutler. Slope accuracy and path planning on compressed terrain. In Symposium on Spatial Data Handling. Montpellier FR, June 2008.
[details] [full text]

BibTeX

@inproceedings{wrf-sdh-2008,
    author = "Franklin, W. Randolph and Tracy, Daniel M. and Andrade, Marcus and Muckell, Jonathan and Inanc, Metin and Xie, Zhongyi and Cutler, Barbara",
    title = "Slope Accuracy and Path Planning on Compressed Terrain",
    booktitle = "Symposium on Spatial Data Handling",
    year = "2008",
    month = "June",
    address = "Montpellier FR",
    mykey = "tracy inanc marcus muckell xie pathplan terrain",
    href = "\bibhref{119-sdh08-slope}"
}

2007

Barbara M. Cutler and W Randolph Franklin. Surface area of the union of many spheres. In (submitted, rejected). 2007.
[details]

BibTeX

@inproceedings{spheresarea-2007,
    author = "Cutler, Barbara M. and Franklin, W Randolph",
    title = "Surface Area of the Union of Many Spheres",
    booktitle = "(submitted, rejected)",
    year = "2007"
}

Zhongyi Xie, Marcus A. Andrade, W. Randolph Franklin, Barbara Cutler, Metin Inanc, Daniel M. Tracy, and Jonathan Muckell. Approximating terrain with over-determined Laplacian PDEs. In 17th Fall Workshop on Computational Geometry. IBM TJ Watson Research Center, Hawthorne NY, 2–3 Nov 2007. (poster session, no formal proceedings).
[details] [full text] [poster]

BibTeX

@inproceedings{xie-fwcg-2007,
    author = "Xie, Zhongyi and Andrade, Marcus A. and Franklin, W. Randolph and Cutler, Barbara and Inanc, Metin and Tracy, Daniel M. and Muckell, Jonathan",
    title = "Approximating terrain with over-determined {Laplacian} {PDEs}",
    booktitle = "17th Fall Workshop on Computational Geometry",
    month = "2--3 Nov",
    mykey = "tracy inanc marcus xie muckell odetlap",
    year = "2007",
    note = "(poster session, no formal proceedings)",
    address = "IBM TJ Watson Research Center, Hawthorne NY",
    customlinkposter = "https://wrfranklin.org/p/117-fwcg07-xie-poster.ppt",
    href = "\bibhrefap{117-fwcg07-xie-abs}{117-fwcg07-xie-poster.ppt}"
}

Jonathan Muckell, Marcus Andrade, W. Randolph Franklin, Barbara Cutler, Metin Inanc, Zhongyi Xie, and Daniel M. Tracy. Drainage network and watershed reconstruction on simplified terrain. In 17th Fall Workshop on Computational Geometry. IBM TJ Watson Research Center, Hawthorne NY, 2–3 Nov 2007. poster session, no formal proceedings.
[details] [full text] [slides]

BibTeX

@inproceedings{muckell-fwcg-2007,
    author = "Muckell, Jonathan and Andrade, Marcus and Franklin, W. Randolph and Cutler, Barbara and Inanc, Metin and Xie, Zhongyi and Tracy, Daniel M.",
    title = "Drainage network and watershed reconstruction on simplified terrain",
    booktitle = "17th Fall Workshop on Computational Geometry",
    month = "2--3 Nov",
    year = "2007",
    note = "poster session, no formal proceedings",
    address = "IBM TJ Watson Research Center, Hawthorne NY",
    customlinkslides = "https://wrfranklin.org/p/116-fwcg07-muckell-poster.ppt",
    mykey = "tracy marcus inanc muckell xie hydro",
    href = "\bibhrefap{116-fwcg07-muckell-abs}{116-fwcg07-muckell-poster.ppt}"
}

W Randolph Franklin, Metin Inanc, Zhongyi Xie, Daniel M. Tracy, Barbara Cutler, Marcus V A Andrade, and Franklin Luk. Smugglers and border guards – the GeoStar project at RPI. In 15th ACM International Symposium on Advances in Geographic Information Systems (ACM GIS 2007). Seattle, WA, USA, Nov 2007.
[details] [full text] [slides]
Abstract
We present the GeoStar project at RPI, which researches various terrain (i.e., elevation) representations and operations thereon. This work is motivated by the large amounts of hi-res data now available. The purpose of each representation is to lossily compress terrain while maintaining important properties. Our ODETLAP representation generalizes a Laplacian partial differential equation by using two inconsistent equations for each known point in the grid, as well as one equation for each unknown point. The surface is reconstructed from a carefully chosen small set of known points. Our second representation segments the terrain intoa set of regions, each of which is simply described. Our third representation has the most long term potential: scooping, which forms the terrain by emulating surface water erosion. Siting hundreds of observers, such as border guards, so that their viewsheds jointly cover the maximum terrain is our first operation. This process allows both observer and target to be above the local terrain, and the observer to have a finite radius of interest. Planning a path so that a smuggler may get from point A to point B while maximally avoiding the border guards is our second operation. The path metric includes path length, distance traveled uphill,and amount of time visible to a guard. The quality of our representations is determined, not only by their RMS elevation error, but by how accurately they support these operations.
BibTeX
```
@inproceedings{acmgis07,
    author = "Franklin, W Randolph and Inanc, Metin and Xie, Zhongyi and Tracy, Daniel M. and Cutler, Barbara and Andrade, Marcus V A and Luk, Franklin",
    title = "Smugglers and border guards -- the {GeoStar} project at {RPI}",
    booktitle = "15th {ACM} International Symposium on Advances in Geographic Information Systems {(ACM GIS 2007)}",
    year = "2007",
    address = "Seattle, WA, USA",
    month = "Nov",
    customlinkslides = "https://wrfranklin.org/p/115-seattle07-acmgis-smugglers-talk.ppt",
    mykey = "pathplan visviewshedsiting marcus tracy inanc xie",
    href = "\bibhrefpt{115-seattle07-acmgis-smugglers}{115-seattle07-acmgis-smugglers-talk.ppt}"
}
```

W. Randolph Franklin. GeoStar April 2007 review. \url https://wrfranklin.org/pmwiki/Research/GeoStarApril2007Review, 2007. [Online; accessed 8-June-2007].
[details]

BibTeX

@misc{darpa-review-apr07,
    author = "Franklin, W. Randolph",
    title = "{GeoStar} {April} 2007 Review",
    howpublished = "\url{https://wrfranklin.org/pmwiki/Research/GeoStarApril2007Review}",
    note = "[Online; accessed 8-June-2007]",
    year = "2007"
}

Daniel M. Tracy, W. Randolph Franklin, Barbara Cutler, Marcus A Andrade, Franklin T Luk, Metin Inanc, and Zhongyi Xie. Multiple observer siting and path planning on lossily compressed terrain. In Proceedings of SPIE Vol. 6697 Advanced Signal Processing Algorithms, Architectures, and Implementations XVII. San Diego CA, 27 August 2007. International Society for Optical Engineering. paper 6697-16.
[details] [full text]
Abstract
We examine a smugglers and border guards scenario. We place observers on a terrain so as to optimize their visible coverage area. Then we compute a path that a smuggler would take so as to avoid detection, while also minimizing the path length. We also examine how our results are affected by using a lossy representation of the terrain instead. We propose three new application-specific error metrics for evaluating terrain compression. Our target terrain applications are the optimal placement of observers on a landscape and the navigation through the terrain by smugglers. Instead of using standard metrics such as average or maximum elevation error, we seek to optimize our compression on the specific real-world application of smugglers and border guards.
BibTeX
```
@inproceedings{dt-wrf-spie-2007,
    author = "Tracy, Daniel M. and Franklin, W. Randolph and Cutler, Barbara and Andrade, Marcus A and Luk, Franklin T and Inanc, Metin and Xie, Zhongyi",
    title = "Multiple observer siting and path planning on lossily compressed terrain",
    booktitle = "Proceedings of {SPIE} Vol. 6697 Advanced Signal Processing Algorithms, Architectures, and Implementations {XVII}",
    year = "2007",
    month = "27 August",
    organization = "International Society for Optical Engineering",
    address = "San Diego CA",
    note = "paper 6697-16",
    mykey = "inanc tracy marcus xie pathplan visviewshedsiting",
    href = "\bibhref{114-spie07-tracy}"
}
```

Zhongyi Xie, W. Randolph Franklin, Barbara Cutler, Marcus A Andrade, Metin Inanc, and Daniel M. Tracy. Surface compression using over-determined Laplacian approximation. In Proceedings of SPIE Vol. 6697 Advanced Signal Processing Algorithms, Architectures, and Implementations XVII. San Diego CA, 27 August 2007. International Society for Optical Engineering. paper 6697-15.
[details] [full text]

Abstract

BibTeX

@inproceedings{zx-wrf-spie-2007,
    author = "Xie, Zhongyi and Franklin, W. Randolph and Cutler, Barbara and Andrade, Marcus A and Inanc, Metin and Tracy, Daniel M.",
    title = "Surface compression using over-determined {Laplacian} approximation",
    booktitle = "Proceedings of {SPIE} Vol. 6697 Advanced Signal Processing Algorithms, Architectures, and Implementations {XVII}",
    year = "2007",
    month = "27 August",
    organization = "International Society for Optical Engineering",
    address = "San Diego CA",
    note = "paper 6697-15",
    href = "\bibhref{113-spie07-xie}",
    mykey = "marcus inanc xie odetlap"
}

2006

W. Randolph Franklin. Smugglers' path planning on compressed terrain. talk at UniGIS conference, May 2006.
[details] [slides]

BibTeX

@misc{unigis-2006,
    author = "Franklin, W. Randolph",
    title = "Smugglers' path planning on compressed terrain",
    howpublished = "talk at {UniGIS} conference",
    organization = "Simon Fraser University",
    address = "Vancouver, Canada",
    month = "May",
    year = "2006",
    mykey = "pathplan",
    customlinkslides = "https://wrfranklin.org/p/158-unigis06-smugglers.ppt",
    href = "\bibhreft{158-unigis06-smugglers.ppt}"
}

Metin Inanc and W Randolph Franklin. Terrain representation using tessellation of irregular planar tiles (extended abstract). In 16th Fall Workshop on Computational Geometry. Smith College, Northampton MA, 10-11 Nov 2006.
[details] [full text] [poster]

BibTeX

@inproceedings{inanc-fwcg-2006,
    author = "Inanc, Metin and Franklin, W Randolph",
    title = "Terrain Representation Using Tessellation of Irregular Planar Tiles (extended abstract)",
    booktitle = "16th Fall Workshop on Computational Geometry",
    year = "2006",
    month = "10-11 Nov",
    address = "Smith College, Northampton MA",
    customlinkposter = "https://wrfranklin.org/p/108-smith-fwcg06-tiles-inanc-poster.jpg",
    href = "\bibhrefap{108-smith-fwcg06-tiles-inanc-abs}{108-smith-fwcg06-tiles-inanc-poster.jpg}",
    mykey = "inanc terrain"
}

Daniel M. Tracy, W Randolph Franklin, and Franklin Luk. Multiple observer siting on a compressed terrain (extended abstract). In 16th Fall Workshop on Computational Geometry. Smith College, Northampton MA, 10-11 Nov 2006.
[details] [full text] [slides]

BibTeX

@inproceedings{tracy-fwcg-2006,
    author = "Tracy, Daniel M. and Franklin, W Randolph and Luk, Franklin",
    title = "Multiple Observer Siting on a Compressed Terrain (extended abstract)",
    booktitle = "16th Fall Workshop on Computational Geometry",
    year = "2006",
    month = "10-11 Nov",
    address = "Smith College, Northampton MA",
    customlinkslides = "https://wrfranklin.org/p/107-smith-fwcg06-multiple-tracy-poster.jpg",
    href = "\bibhrefap{107-smith-fwcg06-multiple-tracy-abs}{107-smith-fwcg06-multiple-tracy-poster.jpg}",
    mykey = "tracy visviewshedsiting"
}

Caroline Westort and W. Randolph Franklin. Alternative sculpting hypotheses for terrain data compression. In Proceedings of SPIE Vol. 6313 Advanced Architectures, and Implementations XVI. San Diego CA, 15-16 August 2006. International Society for Optical Engineering. 6313-16, Session 4.
[details]
Abstract
Digital Terrain Models (DTM~s) are large. Processes and data-structures employed to generate and represent them rarely capture the topographic complexity one finds in nature. The result is bulky, unwieldy data sets which need to be thinned to be useful. Many approaches to compressing terrain data resort to assumptions which compromise the complexity of the existing terrain; discontinuities are ignored, for example, surfaces are assumed to be ~2.5 D~; absent of elements such as overhangs, cliffs, or tunnels. Interpolation techniques over rough terrain, in the case of grids, often ignore topographic roughness where it exists. The tradeoffs between the traditional 3-dimensional terrain data structures - grids, TINs and contour line representations - are well-versed. What is called for are novel ways to describe and represent terrain that are compact but which also retain specific, subjectively selected complexity. This paper discusses five alternative notions of sculpting gleaned from a broad spectrum of domains, including CAD/CAM, computer graphics, and the traditional arts. The goal is to come up with novel computational alternatives for three-dimensional terrain surfaces, that may satisfy both the need for more compactness, and for complexity retention. The five notions are: * Carving (subtractive techniques) * ~Modeling~, in the traditional sculpting sense, where one adds material to form an object. * Assembly of sub-parts, or sub-regions * Bending, smoothing, or deforming * Dynamic sculpture or arrangements.
BibTeX
```
@inproceedings{cw-wrf-spie-2006,
    author = "Westort, Caroline and Franklin, W. Randolph",
    title = "Alternative sculpting hypotheses for terrain data compression",
    booktitle = "Proceedings of {SPIE} Vol. 6313 Advanced Architectures, and Implementations {XVI}",
    year = "2006",
    month = "15-16 August",
    organization = "International Society for Optical Engineering",
    address = "San Diego CA",
    note = "6313-16, Session 4",
    mykey = "terrain"
}
```
W. Randolph Franklin and Metin Inanc. Compressing terrain datasets using segmentation. In Proceedings of SPIE Vol. 6313 Advanced Architectures, and Implementations XVI. San Diego CA, 15-16 August 2006. International Society for Optical Engineering. 6313-17, Session 4.
[details] [full text]
Abstract
We propose a novel compression scheme to achieve lossless compression of elevation datasets. Our scheme does not use predictors in traditional sense. Predictors are based on dataset segments instead of the rows and columns processed so far. We believe that this is a far better way of expressing context in an image or elevation datasets since it can capture continuities in different geometries and is not limited to a subset of a pixel~s neighborhood. We compare the compression results of our scheme with that of JPEG-2000.
BibTeX
```
@inproceedings{wrf-mi-spie-2006,
    author = "Franklin, W. Randolph and Inanc, Metin",
    title = "Compressing terrain datasets using segmentation",
    booktitle = "Proceedings of {SPIE} Vol. 6313 Advanced Architectures, and Implementations {XVI}",
    year = "2006",
    month = "15-16 August",
    organization = "International Society for Optical Engineering",
    address = "San Diego CA",
    note = "6313-17, Session 4",
    mykey = "terrain inanc",
    href = "\bibhref{112b-spie06-inanc}"
}
```

W. Randolph Franklin and Christian Vogt. Tradeoffs when multiple observer siting on large terrain cells. In Andreas Riedl, Wolfgang Kainz, and Gregory Elmes, editors, Progress in Spatial Data Handling: 12th International Symposium on Spatial Data Handling, pages 845–861. Springer, Vienna, 2006.
[details] [full text] [slides]

BibTeX

@incollection{wrf-sdh2006,
    author = "Franklin, W. Randolph and Vogt, Christian",
    editor = "Riedl, Andreas and Kainz, Wolfgang and Elmes, Gregory",
    title = "Tradeoffs when multiple observer siting on large terrain cells",
    booktitle = "Progress in Spatial Data Handling: 12th International Symposium on Spatial Data Handling",
    pages = "845--861",
    publisher = "Springer",
    year = "2006",
    note = "ISBN 978-3-540-35588-5",
    address = "Vienna",
    mykey = "visviewshedsiting",
    customlinkslides = "https://wrfranklin.org/p/112-sdh06-vienna-siting-tradeoffs-talk.ppt",
    href = "\bibhrefpt{112-sdh06-vienna-siting-tradeoffs}{112-sdh06-vienna-siting-tradeoffs-talk.ppt}"
}

W. Randolph Franklin, Metin Inanc, and Zhongyi Xie. Two novel surface representation techniques. In Autocarto 2006. Vancouver Washington, 25-28 June 2006. Cartography and Geographic Information Society, \url https://cartogis.org/autocarto/autocarto-2006/.
[details] [full text]

BibTeX

@inproceedings{wrf-autocarto-2006,
    author = "Franklin, W. Randolph and Inanc, Metin and Xie, Zhongyi",
    title = "Two novel surface representation techniques",
    booktitle = "Autocarto 2006",
    year = "2006",
    address = "Vancouver Washington",
    month = "25-28 June",
    organization = "Cartography and Geographic Information Society, \url{https://cartogis.org/autocarto/autocarto-2006/}",
    mykey = "inanc xie terrain",
    href = "\bibhref{111-vancouverwa-autocarto06-twonovel}"
}

W. Randolph Franklin and Eric Landis. Connected components on 1000x1000x1000 datasets. In 16th Fall Workshop on Computational Geometry. Smith College, Northampton, MA, 10-11 Nov 2006. (extended abstract).
[details] [full text] [slides]

BibTeX

@inproceedings{wrf-connect-fwcg2006,
    author = "Franklin, W. Randolph and Landis, Eric",
    title = "Connected components on 1000x1000x1000 datasets",
    booktitle = "16th Fall Workshop on Computational Geometry",
    address = "Smith College, Northampton, MA",
    month = "10-11 Nov",
    year = "2006",
    mykey = "connect",
    note = "(extended abstract)",
    customlinkslides = "https://wrfranklin.org/p/110-smith-fwcg06-connect-talk.pdf",
    href = "\bibhrefat{110-smith-fwcg06-connect}{110-smith-fwcg06-connect-talk}"
}

Eric N. Landis, Tong Zhang, Edwin N. Nagy, George Nagy, and W. Randolph Franklin. Cracking, damage and fracture in four dimensions. Materials and Structures, online date: 13 July 2006.
[details] [full text]
Abstract
Abstract Concrete and cracking are nearly synonymous despite our best efforts and intentions. Relationships between cracking and the stress states that lead to cracking can be instructive. In an effort to better understand these relationships, X-ray microtomography was used to make high-resolution three-dimensional digital images of small concrete specimens under load. Using 3D image analysis, quantitative measurements of internal crack growth were made that include effects of crack tortuosity, branching and microcracking. Successive images at different levels of cracking and damage provide us with a detailed picture of internal crack progression. When coupled with load-deformation response, bulk material properties such as fracture toughness or damage variables can be quantitatively linked with cracking. Measurements to date have shown distinct fracture regimes linked to crack formation and propagation. In addition, the crack measurements offer a way to provide a physical basis for a scalar damage variable.
BibTeX
```
@article{landis2006,
    author = "Landis, Eric N. and Zhang, Tong and Nagy, Edwin N. and Nagy, George and Franklin, W. Randolph",
    title = "Cracking, damage and fracture in four dimensions",
    journal = "Materials and Structures",
    publisher = "Springer",
    year = "2006",
    mykey = "connect",
    month = "online date: 13 July",
    href = "\bibhref{109-matstruct2006-cracking-landis}",
    Keywords = "Concrete - Fracture - Damage - Tomography",
    publisher-url = "http://www.springerlink.com/content/ftgmk3m461716833/"
}
```

W. Randolph Franklin. CONNECT – find 3D connected components. 2006. URL: https://wrfranklin.org/pmwiki/ConnectedComponents.
[details]

BibTeX

@misc{connect-web,
    author = "Franklin, W. Randolph",
    title = "{CONNECT} -- Find {3D} connected components",
    url = "https://wrfranklin.org/pmwiki/ConnectedComponents",
    mykey = "connect",
    year = "2006"
}

2005

Michael B. Gousie and Wm. Randolph Franklin. Augmenting grid-based contours to improve thin plate dem generation. Photogrammetric Engineering & Remote Sensing, 71(1):69–79, 2005.
[details] [full text]

BibTeX

@article{Gousie05,
    author = "Gousie, Michael B. and Franklin, Wm. Randolph",
    title = "Augmenting Grid-based Contours to Improve Thin Plate DEM Generation",
    journal = "Photogrammetric Engineering \\& Remote Sensing",
    volume = "71",
    number = "1",
    pages = "69-79",
    year = "2005",
    mykey = "terrain",
    href = "\bibhref{106-pers05-thinplate}"
}

W. Randolph Franklin. Nearpt3 — Nearest point query on 184M points in $E^3$ with a uniform grid. In Proceedings of the 17th Canadian Conference on Computational Geometry (CCCG'05), 239–242. Windsor, Ontario, 10-12 August 2005.
[details] [full text] [slides]

BibTeX

@inproceedings{wrf-nearpt3-cccg-2005,
    author = "Franklin, W. Randolph",
    title = "Nearpt3 --- {Nearest} Point Query on {184M} Points in {$E^3$} with a Uniform Grid",
    year = "2005",
    booktitle = "Proceedings of the 17th {Canadian} Conference on Computational Geometry {(CCCG'05)}",
    address = "Windsor, Ontario",
    month = "{10-12 August}",
    pages = "239--242",
    mykey = "nearpt",
    customlinkslides = "https://wrfranklin.org/p/105-nearpt3-talk.pdf",
    href = "\bibhrefnpt{paper (current version)}{105-nearpt3}{105-nearpt3-talk.pdf}"
}

W. Randolph Franklin. Nearpt3 — Nearest point query on 184M points in $E^3$ with a uniform grid. \url https://wrfranklin.org/Research/nearpt3/, 2005.
[details]

BibTeX

@misc{wrf-nearpt3-web,
    author = "Franklin, W. Randolph",
    year = "2005",
    title = "Nearpt3 --- {Nearest} Point Query on {184M} Points in {$E^3$} with a Uniform Grid",
    howpublished = "\url{https://wrfranklin.org/Research/nearpt3/}",
    mykey = "nearpt"
}

Wm. Randolph Franklin. Mass properties of the union of millions of identical cubes. In Ravi Janardan, Debashish Dutta, and Michiel Smid, editors, Geometric and Algorithmic Aspects of Computer Aided Design and Manufacturing, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, volume 67, pages 329–345. American Mathematical Society, 2005.
[details] [full text] [slides]

BibTeX

@incollection{wrf-dimacs2005,
    author = "Franklin, Wm. Randolph",
    editor = "Janardan, Ravi and Dutta, Debashish and Smid, Michiel",
    title = "Mass Properties of the Union of Millions of Identical Cubes",
    booktitle = "Geometric and Algorithmic Aspects of Computer Aided Design and Manufacturing, {DIMACS} Series in Discrete Mathematics and Theoretical Computer Science",
    publisher = "American Mathematical Society",
    volume = "67",
    year = "2005",
    pages = "329--345",
    mykey = "union3 topology",
    succeeds = "wrf-dimacs2003",
    customlinkslides = "https://wrfranklin.org/p/104-dimacs03-union-talk.pdf",
    href = "\bibhrefpt{104-dimacs03-union}{104-dimacs03-union-talk.pdf}"
}

2004

W. Randolph Franklin. Nearpt3 — Nearest point query in $E^3$ with a uniform grid (extended abstract). In 14th Annual Fall Workshop on Computational Geometry. MIT, 20 Nov 2004.
[details] [full text] [slides]

BibTeX

@inproceedings{wrf-nearpt3-mit-2004,
    author = "Franklin, W. Randolph",
    title = "Nearpt3 --- {Nearest} Point Query in {$E^3$} with a Uniform Grid (extended abstract)",
    booktitle = "14th Annual Fall Workshop on Computational Geometry",
    address = "{MIT}",
    month = "20 Nov",
    year = "2004",
    mykey = "nearpt",
    customlinkslides = "https://wrfranklin.org/p/102-fwcg2004-nearpt3-talk.pdf",
    href = "\bibhrefpt{102-fwcg2004-nearpt3}{102-fwcg2004-nearpt3-talk.pdf}"
}

W. Randolph Franklin. Analysis of mass properties of the union of millions of polyhedra. In M. L. Lucian and M. Neamtu, editors, Geometric Modeling and Computing: Seattle 2003, pages 189–202. Nashboro Press, Brentwood TN, 2004.
[details] [full text]

BibTeX

@incollection{wrf-union-analysis-2004,
    author = "Franklin, W. Randolph",
    editor = "Lucian, M. L. and Neamtu, M.",
    title = "Analysis of Mass Properties of the Union of Millions of Polyhedra",
    year = "2004",
    booktitle = "Geometric Modeling and Computing: Seattle 2003",
    publisher = "Nashboro Press, Brentwood TN",
    pages = "189--202",
    isbn = "0-0-9728482-3-1",
    mykey = "union3 topology parallel",
    href = "\bibhref{101-siam04-union}"
}

Wm. Randolph Franklin. Automated observer siting on terrain, showing intervisibility. \url https://wrfranklin.org/Research/siting/, 2004.
[details]

BibTeX

@misc{wrf-siting-jan2004,
    author = "Franklin, Wm. Randolph",
    precedes = "wrf-siting-web",
    title = "Automated Observer Siting on Terrain, Showing Intervisibility",
    howpublished = "\url{https://wrfranklin.org/Research/siting/}",
    mykey = "xxxvisviewshedsiting",
    year = "2004"
}

W. Randolph Franklin and Christian Vogt. Efficient observer siting on large terrain cells (extended abstract). In GIScience 2004: Third International Conference on Geographic Information Science. U Maryland College Park, 20–23 Oct 2004.
[details] [full text] [slides]
Abstract
This paper refines our testbed implementation of a suite of programs, for fast viewshed, and for fast approximate visibility index determination, and for siting multiple observers jointly to cover terrain. We process DEMs up to 2402 × 2402, while executing so quickly that multiple experiments are easily possible. Both the observer and target may be at a given fixed height above the terrain. We conclude that estimating visibility index using 20-30 random targets per observer is a good compromise between speed and quality. When forcing the selection of top observers to be well spaced out, subdividing the cell into such small blocks that only 2-5 observers are selected per block is best. Applications of multiple observer siting include radio towers, terrain observation, and mitigation of environmental visual nuisances.
BibTeX
```
@inproceedings{wrf-siting-apr2004,
    author = "Franklin, W. Randolph and Vogt, Christian",
    title = "Efficient observer siting on large terrain cells (extended abstract)",
    booktitle = "{GIScience} 2004: Third International Conference on Geographic Information Science",
    year = "2004",
    address = "U Maryland College Park",
    month = "20--23 Oct",
    mykey = "visviewshedsiting",
    customlinkslides = "https://wrfranklin.org/p/103-collegepark-giscience2004-siting-talk.pdf",
    href = "\bibhrefpt{103-collegepark-giscience2004-siting}{103-collegepark-giscience2004-siting-talk.pdf}"
}
```

W. Randolph Franklin. Terrain observer siting research web site. \url https://wrfranklin.org/Research/siting/, 2004.
[details]

BibTeX

@misc{wrf-siting-web,
    author = "Franklin, W. Randolph",
    title = "Terrain observer siting research web site",
    howpublished = "\url{https://wrfranklin.org/Research/siting/}",
    mykey = "visviewshedsiting",
    year = "2004"
}

W. Randolph Franklin and Christian Vogt. Multiple observer siting on terrain with intervisibility or lo-res data. In XXth Congress, International Society for Photogrammetry and Remote Sensing. Istanbul, 12-23 July 2004.
[details] [full text] [poster]
Abstract
We describe two current projects with our toolkit for siting multiple observers on terrain. (Both observers and targets are at some specified height above ground level. Observers can see targets, when not hidden by the terrain, out to a specified radius of interest.) Siting the observers so that they are intervisible, i.e., so that the visibility graph is a connected set, is the first project. The second project tests the effect, on the optimality of the multiple observer siting (w/o intervisiblity), of reducing the map cell's horizontal or vertical resolution. We lowered the resolution, sited observers optimally, then computed those observers' joint visibility index on the hi-res data. We observed that much less precise vertical resolution is ok, but that reducing the horizontal resolution by even a factor of two leads to an observer siting with significantly reduced joint visibility index, when evaluated on the hi-res data. Applications of multiple observer siting include siting radio towers and mitigating visual nuisances.
BibTeX
```
@inproceedings{wrf-cv-siting-isprs,
    author = "Franklin, W. Randolph and Vogt, Christian",
    title = "Multiple observer siting on terrain with intervisibility or lo-res data",
    booktitle = "{XX}th Congress, International Society for Photogrammetry and Remote Sensing",
    year = "2004",
    address = "Istanbul",
    month = "12-23 July",
    customlinkposter = "https://wrfranklin.org/p/100-istanbul-isprs04-siting-poster.pdf",
    mykey = "visviewshedsiting",
    href = "\bibhrefpp{100-istanbul-isprs04-siting}{100-istanbul-isprs04-siting-poster.jpg}"
}
```

2003

Michael Gousie and W. Randolph Franklin. Constructing a DEM from grid-based data by computing intermediate contours. In Erik Hoel and Phillippe Rigaux, editors, GIS 2003: Proceedings of the Eleventh ACM International Symposium on Advances in Geographic Information Systems, 71–77. New Orleans, 2003.
[details] [full text]

BibTeX

@inproceedings{acmgis2003,
    author = "Gousie, Michael and Franklin, W. Randolph",
    editor = "Hoel, Erik and Rigaux, Phillippe",
    title = "Constructing a {DEM} from Grid-based Data by Computing Intermediate Contours",
    booktitle = "GIS 2003: Proceedings of the Eleventh ACM International Symposium on Advances in Geographic Information Systems",
    date = "November 7--8",
    address = "New Orleans",
    pages = "71-77",
    year = "2003",
    mykey = "terrain",
    href = "\bibhref{99-acmgis03-intermed-contour}"
}

Edwin Nagy, Tong Zhang, Wm Randolph Franklin, George Nagy, and E Landis. 3D analysis of tomographic images. In 16th ASCE Engineering Mechanics Conference. U Washington, Seattle, 16-18 July 2003. electronic proceedings.
[details] [full text]

BibTeX

@inproceedings{acse2003,
    author = "Nagy, Edwin and Zhang, Tong and Franklin, Wm Randolph and Nagy, George and Landis, E",
    title = "{3D} Analysis of Tomographic Images",
    booktitle = "16th {ASCE} Engineering Mechanics Conference",
    year = "2003",
    address = "U Washington, Seattle",
    month = "16-18 July",
    mykey = "connect",
    note = "electronic proceedings",
    href = "\bibhref{98-acse03-3danalysis-nagy}"
}

2002

DARPA/DSO. Geostar. \url http://www.darpa.mil/dso/future/geo/index.htm, 2002.
[details]

BibTeX

@misc{geostar,
    author = "DARPA/DSO",
    title = "Geostar",
    howpublished = "\url{http://www.darpa.mil/dso/future/geo/index.htm}",
    year = "2002"
}

W. Randolph Franklin. Siting observers on terrain. In Dianne Richardson and Peter van Oosterom, editors, Advances in Spatial Data Handling: 10th International Symposium on Spatial Data Handling, 109–120. Springer-Verlag, 2002.
[details] [full text]
Abstract
This paper presents an experimental study of a new algorithm that synthesizes separate programs, for fast viewshed, and for fast approximate visibility index determination, into a working testbed for siting multiple observers jointly to cover terrain from a full level-1 DEM, and to do it so quickly that multiple experiments are easily possible. Both the observer and target may be at a given fixed distance above the terrain. The process operates as follows. (1) An approximate visibility index is calculated for each point in the cell under consideration. (2) A set of tentative observers is selected from the highly visible points. (3) The actual observers are selected from them, so as to cover as much of the cell of possibe, using a greedy algorithm. Various experiments with varying parameters were performed on the Lake Champlain West cell, with observations such as the following. (1) Forcing tentative observers to be well spaced was more important than using the most visible tentative observers. (2) Most of the new observers added (because they covered the most unseen points) were already visible to an existing observer. (3) Randomly deleting many tentative observers before final selection didn't reduce the final area covered.
BibTeX
```
@inproceedings{wrf-site,
    author = "Franklin, W. Randolph",
    editor = "Richardson, Dianne and van Oosterom, Peter",
    title = "Siting observers on terrain",
    booktitle = "Advances in Spatial Data Handling: 10th International Symposium on Spatial Data Handling",
    publisher = "Springer-Verlag",
    pages = "109--120",
    year = "2002",
    href = "\bibhref{97-ottawa-sdh02-siting}",
    isbn = "2-540-43802-5",
    mykey = "visviewshedsiting"
}
```

2001

DARPA/DSO, W. Randolph Franklin, and Yehuda Avniel. Geospatial terrain analysis and representations (geo*). \url http://www.darpa.mil/dso/future/geo/index.htm, 2001. [Online; accessed 27-Dec–2001].
[details]

BibTeX

@misc{darpa-geospatial01,
    author = "DARPA/DSO and Franklin, W. Randolph and Avniel, Yehuda",
    title = "Geospatial terrain analysis and representations (geo*)",
    howpublished = "\url{http://www.darpa.mil/dso/future/geo/index.htm}",
    year = "2001",
    note = "[Online; accessed 27-Dec--2001]"
}

G Nagy, T Zhang, WR Franklin, E Landis, E Nagy, and D Keane. Volume and surface area distributions of cracks in concrete. In C. Arcelli, L.P. Cordella, and G. Sanniti di Baja, editors, Visual Form 2001: 4th International Workshop on Visual Form IWVF4, volume 2051/2001 of Lecture Notes in Computer Science. Springer-Verlag Heidelberg, Capri, Italy, 28-30 May 2001.
[details] [full text] [poster]

BibTeX

@incollection{capri01,
    author = "Nagy, G and Zhang, T and Franklin, WR and Landis, E and Nagy, E and Keane, D",
    editor = "Arcelli, C. and Cordella, L.P. and di Baja, G. Sanniti",
    title = "Volume and Surface Area Distributions of Cracks in Concrete",
    booktitle = "Visual Form 2001: 4th International Workshop on Visual Form {IWVF4}",
    publisher = "Springer-Verlag Heidelberg",
    year = "2001",
    mykey = "connect",
    volume = "2051/2001",
    series = "Lecture Notes in Computer Science",
    address = "Capri, Italy",
    month = "28-30 May",
    href = "\bibhrefpp{95-capri01-paper}{95-capri01-poster.gif}",
    customlinkposter = "https://wrfranklin.org/p/95-capri01-poster.gif"
}

W. Randolph Franklin, Benjamin Mann, and Douglas Cochran. NSF 01-111 computational algorithms and representations for geometric objects (cargo). \url http://www.nsf.gov/cgi-bin/getpub?nsf01111, May 2001.
[details]

BibTeX

@misc{cargo,
    author = "Franklin, W. Randolph and Mann, Benjamin and Cochran, Douglas",
    title = "{NSF} 01-111 Computational Algorithms and Representations for Geometric Objects (CARGO)",
    howpublished = "\url{http://www.nsf.gov/cgi-bin/getpub?nsf01111}",
    month = "May",
    year = "2001"
}

Hélio Pedrini, William Robson Schwartz, and W. R. Franklin. Automatic extraction of topographic features using adaptive triangular meshes. In 2001 International Conference on Image Processing (ICIP-2001), volume 3, 732–735. Thessaloniki, Greece, 7-10 October 2001. IEEE. doi:https://doi.org/10.1109/ICIP.2001.958223.
[details]

BibTeX

@inproceedings{pedrini-icip-2001,
    author = "Pedrini, Hélio and Schwartz, William Robson and Franklin, W. R.",
    title = "Automatic Extraction of Topographic Features Using Adaptive Triangular Meshes",
    booktitle = "2001 International Conference on Image Processing (ICIP-2001)",
    year = "2001",
    address = "Thessaloniki, Greece",
    month = "7-10 October",
    publisher = "IEEE",
    pages = "732-735",
    volume = "3",
    doi = "https://doi.org/10.1109/ICIP.2001.958223",
    href = "\bibhref{96-pedrini-icip-2001}",
    bibsource = "DBLP, http://dblp.uni-trier.de"
}

Wm. Randolph Franklin. Triangulated irregular network computation. 2001. accessed 8-June–2007. URL: https://wrfranklin.org/pmwiki/Research/TriangulatedIrregularNetwork.
[details]

BibTeX

@misc{tin-code,
    author = "Franklin, Wm. Randolph",
    title = "Triangulated Irregular Network computation",
    url = "https://wrfranklin.org/pmwiki/Research/TriangulatedIrregularNetwork",
    note = "accessed 8-June--2007",
    year = "2001"
}

2000

Harold Moellering, Keith Clarke, Robert Cromley, Wm Randolph Franklin, Alan Saalfeld, Jon Kimerling, and Marc Armstrong. Analytical cartography. UCGIS Emerging Research Themes in GIScience (white paper), Dec 2000. (UCGIS = University Consortium for Geographic Information Science).
[details]

BibTeX

@article{ucgis-ancart,
    author = "Moellering, Harold and Clarke, Keith and Cromley, Robert and Franklin, Wm Randolph and Saalfeld, Alan and Kimerling, Jon and Armstrong, Marc",
    title = "Analytical Cartography",
    journal = "UCGIS Emerging Research Themes in GIScience (white paper)",
    year = "2000",
    month = "Dec",
    note = "(UCGIS = University Consortium for Geographic Information Science)"
}

W. Randolph Franklin. Approximating visibility. In GIScience 2000. Savannah, Georgia, USA, 30 Oct 2000.
[details] [full text]

BibTeX

@inproceedings{wrf-savannah,
    author = "Franklin, W. Randolph",
    title = "Approximating visibility",
    booktitle = "{GIScience} 2000",
    month = "30 Oct",
    address = "Savannah, Georgia, USA",
    year = "2000",
    mykey = "visviewshedsiting",
    href = "\bibhref{91-savannah-giscience00-appvis}"
}

W. Randolph Franklin. Applications of analytical cartography. Cartography and Geographic Information Systems, 27(3):225–237, 2000.
[details] [full text]

BibTeX

@article{wrf-cagis-00,
    author = "Franklin, W. Randolph",
    title = "Applications of Analytical Cartography",
    journal = "Cartography and Geographic Information Systems",
    year = "2000",
    volume = "27",
    number = "3",
    pages = "225-237",
    href = "\bibhref{94-cagis00-gisapps}"
}

W. Randolph Franklin. Applications of geometry. In Kenneth H Rosen, editor, Handbook of Discrete and Combinatorial Mathematics, chapter 13.8, pages 867–888. CRC Press, 2000.
[details]

BibTeX

@incollection{wrf-crc00,
    author = "Franklin, W. Randolph",
    editor = "Rosen, Kenneth H",
    title = "Applications of Geometry",
    booktitle = "Handbook of Discrete and Combinatorial Mathematics",
    pages = "867-888",
    publisher = "{CRC} Press",
    year = "2000",
    chapter = "13.8"
}

1999

W. Randolph Franklin and Michael Gousie. Terrain elevation data structure operations. In C. Peter Keller, editor, Proceedings of the 19th International Cartographic Association Conference, 1011–1020. Ottawa, August 1999. URL: https://wrfranklin.org/wiki/Research/ica99/.
[details] [full text]

BibTeX

@inproceedings{wrf-ica99-web,
    author = "Franklin, W. Randolph and Gousie, Michael",
    editor = "Keller, C. Peter",
    title = "Terrain Elevation Data Structure Operations",
    booktitle = "Proceedings of the 19th {International Cartographic Association} Conference",
    month = "August",
    pages = "1011--1020",
    isbn = "0-919088-54-6",
    address = "Ottawa",
    url = "https://wrfranklin.org/wiki/Research/ica99/",
    href = "\bibhref{90-ottawa-ica99-terrain}",
    mykey = "terrain",
    year = "1999"
}

1998

Michael Gousie and W. Randolph Franklin. Converting elevation contours to a grid. In Eighth International Symposium on Spatial Data Handling, 647–656. Vancouver BC Canada, July 1998. Dept of Geography, Simon Fraser University, Burnaby, BC, Canada.
[details] [full text] [slides]

BibTeX

@inproceedings{gousie98,
    author = "Gousie, Michael and Franklin, W. Randolph",
    title = "Converting Elevation Contours to a Grid",
    booktitle = "Eighth International Symposium on Spatial Data Handling",
    address = "Vancouver BC Canada",
    year = "1998",
    month = "July",
    pages = "647-656",
    publisher = "Dept of Geography, Simon Fraser University, Burnaby, BC, Canada",
    customlinkslides = "https://wrfranklin.org/p/89-vancouver-sdh98-contour-gousie-talk.pdf",
    mykey = "terrain odetlap",
    href = "\bibhrefpt{89-vancouver-sdh98-contour-gousie}{89-vancouver-sdh98-contour-gousie-talk.pdf}"
}

1996

W. Randolph Franklin and Amir Said. Lossy compression of elevation data. In Seventh International Symposium on Spatial Data Handling, 8B29ff. Delft, August 1996.
[details] [full text]

BibTeX

@inproceedings{wrflossy,
    author = "Franklin, W. Randolph and Said, Amir",
    title = "Lossy Compression of Elevation Data",
    booktitle = "Seventh International Symposium on Spatial Data Handling",
    address = "Delft",
    year = "1996",
    month = "August",
    pages = "8B29ff",
    href = "\bibhref{87-delft96-lossy}"
}

1995

W. Randolph Franklin. Compressing elevation data. In Fourth International Symposium on Large Spatial Databases — SSD '95. Portland, Maine, USA, 6–9 Aug 1995.
[details] [full text]

BibTeX

@inproceedings{wrfelev95,
    author = "Franklin, W. Randolph",
    title = "Compressing Elevation Data",
    booktitle = "Fourth International Symposium on Large Spatial Databases --- {SSD} '95",
    year = "1995",
    publisher = "Portland, Maine, USA",
    month = "6--9 Aug",
    href = "\bibhref{86-ssd95-compress}"
}

Mohan Kankanhalli and Wm Randolph Franklin. Area and perimeter computation of the union of a set of iso-rectangles in parallel. J. Parallel Distrib. Comput., 27(2):107–117, June 1995. doi:https://doi.org/10.1006/jpdc.1995.1076.
[details] [full text]
Abstract
Finding the area and perimeter of the union/intersection of a set of iso-rectangles is a very important part of circuit extraction in VLSI design. We combine two techniques, the uniform grid and the vertex neighborhoods, to develop a new parallel algorithm for the area and perimeter problems which has an average linear time performance but is not worst-case optimal. The uniform grid technique has been used to generate the candidate vertices of the union or intersection of the rectangles. An efficient point-in-rectangles inclusion test filters the candidate set to obtain the relevant vertices of the union or intersection. Finally, the vertex neighborhood technique is used to compute the mass properties from these vertices. This algorithm has an average time complexity of O(((n + k)/p) + log p) where n is the number of input rectangle edges with k intersections on p processors assuming a PRAM model of computation. The analysis of the algorithm on a SIMD architecture is also presented. This algorithm requires very simple data structures which makes the implementation easy. We have implemented the algorithm on a Sun 4/280 workstation and a Connection Machine. The sequential implementation performs better than the optimal algorithm for large datasets. The parallel implementation on a Connection Machine CM-2 with 32K processors also shows good results.
BibTeX
```
@article{kf-apcus-92,
    author = "Kankanhalli, Mohan and Franklin, Wm Randolph",
    title = "Area and Perimeter Computation of the Union of a Set of Iso-Rectangles in Parallel",
    year = "1995",
    pages = "107--117",
    volume = "27",
    number = "2",
    doi = "https://doi.org/10.1006/jpdc.1995.1076",
    month = "June",
    journal = "J. Parallel Distrib. Comput.",
    keywords = "intersection, parallel computation, grids, area",
    href = "\bibhref{85-jpdc95-parallel-union-area}",
    mykey = "topology kankanhalli parallel"
}
```

1994

W. Randolph Franklin. 17) how do I find if a point lies within a polygon? In J O'Rourke, editor, comp.graphics.algorithms Frequently Asked Questions (FAQ). 1994.
[details]

BibTeX

@incollection{wrfgraphicsfaq,
    author = "Franklin, W. Randolph",
    editor = "O'Rourke, J",
    booktitle = "comp.graphics.algorithms Frequently Asked Questions ({FAQ})",
    title = "17) How do {I} find if a point lies within a polygon?",
    year = "1994",
    paperlist = "83"
}

W. Randolph Franklin, Jr Clark K Ray, and Shashank Mehta. Geometric algorithms for siting of air defense missile batteries. Technical Report, US Army Topographic Engineering Center, March 1994. Battelle, Columbus Division Contract Number DAAL03-86-D-0001, Delivery Order Number 2756, Scientific Services Program.
[details]

BibTeX

@techreport{wrf-tec-94,
    author = "Franklin, W. Randolph and Clark K Ray, Jr and Mehta, Shashank",
    title = "Geometric Algorithms for Siting of Air Defense Missile Batteries",
    institution = "US Army Topographic Engineering Center",
    year = "1994",
    month = "March",
    note = "Battelle, Columbus Division Contract Number DAAL03-86-D-0001, Delivery Order Number 2756, Scientific Services Program"
}

Wm. Randolph Franklin. Overlay area calculation program. 1994. URL: https://wrfranklin.org/wiki/Research/overlay.tgz.
[details]

BibTeX

@misc{overlay-code-94,
    author = "Franklin, Wm. Randolph",
    title = "Overlay Area Calculation Program",
    url = "https://wrfranklin.org/wiki/Research/overlay.tgz",
    mykey = "overlay",
    year = "1994"
}

Wm Randolph Franklin and Clark Ray. Higher isn't necessarily better: visibility algorithms and experiments. In Thomas C. Waugh and Richard G. Healey, editors, Advances in GIS Research: Sixth International Symposium on Spatial Data Handling, 751–770. Edinburgh, 5–9 Sept 1994. The International Geographical Union's Commission on Geographical Information Systems and The Association for Geographic Information, Taylor & Francis.
[details] [full text]
Abstract
We describe several fast programs to compute viewsheds and weighted visibility indices for observation points in a raster terrain. These pro grams explore various tradeoffs between speed and accuracy. We have analyzed many cells of data; there is no strong correlation between a point's elevation and its weighted visibility index. However, the, very few, high visibility points tend to characterize features of the terrain. This work can form a basis for automatically locating observers jointly to cover a terrain region of interest.
BibTeX
```
@inproceedings{fr-hinbv-94,
    author = "Franklin, Wm Randolph and Ray, Clark",
    editor = "Waugh, Thomas C. and Healey, Richard G.",
    title = "Higher isn't Necessarily Better: Visibility Algorithms and Experiments",
    booktitle = "Advances in {GIS} Research: Sixth International Symposium on Spatial Data Handling",
    organization = "The International Geographical Union's Commission on Geographical Information Systems and The Association for Geographic Information",
    year = "1994",
    month = "5--9 Sept",
    address = "Edinburgh",
    publisher = "Taylor \\& Francis",
    pages = "751--770",
    mykey = "visviewshedsiting",
    href = "\bibhref{84-edinburgh-sdh94-higher-not-better}"
}
```

Wm Randolph Franklin, Venkateshkumar Sivaswami, David Sun, Mohan Kankanhalli, and Chandrasekhar Narayanaswami. Calculating the area of overlaid polygons without constructing the overlay. Cartography and Geographic Information Systems, pages 81–89, April 1994.
[details] [full text]

BibTeX

@article{fsskn-ofmop-93,
    author = "Franklin, Wm Randolph and Sivaswami, Venkateshkumar and Sun, David and Kankanhalli, Mohan and Narayanaswami, Chandrasekhar",
    title = "Calculating the Area of Overlaid Polygons Without Constructing the Overlay",
    year = "1994",
    month = "April",
    pages = "81--89",
    journal = "Cartography and Geographic Information Systems",
    succeeds = "f-cmopa-90",
    mykey = "overlay kankanhalli chandra",
    keywords = "intersection, grids, area",
    href = "\bibhref{81-cagis94-overlay}"
}

1993

Wm Randolph Franklin and Mohan S. Kankanhalli. Volumes from overlaying 3-D triangulations in parallel. In D. Abel and B.C. Ooi, editors, Advances in Spatial Databases: Third Intl. Symp., SSD'93, volume 692 of Lecture Notes in Computer Science, pages 477–489. Springer-Verlag, June 1993.
[details] [full text]

BibTeX

@incollection{fk-vo3tp-93,
    author = "Franklin, Wm Randolph and Kankanhalli, Mohan S.",
    editor = "Abel, D. and Ooi, B.C.",
    title = "Volumes From Overlaying 3-{D} Triangulations in Parallel",
    booktitle = "Advances in Spatial Databases: Third Intl. Symp., SSD'93",
    publisher = "Springer-Verlag",
    month = "June",
    year = "1993",
    series = "Lecture Notes in Computer Science",
    volume = "692",
    pages = "477--489",
    comment = "SSD = Symp on Large Spatial DBs, Singapore",
    href = "\bibhref{78-ssd93-tet}",
    keywords = "parallel computation, intersection, volume, CAD",
    mykey = "kankanhalli overlay parallel"
}

UCGIA Steering Committee. On the possible role(s) of a “university consortium for geographic information and analysis” (UCGIA). In Proceedings, American Congress on Surveying and Mapping / American Society for Photogrammetry and Remote Sensing '93. New Orleans, 1993.
[details]

BibTeX

@inproceedings{wrf-ucgia,
    author = "Committee, UCGIA Steering",
    title = "On the Possible Role(s) of a ``University Consortium for Geographic Information and Analysis'' ({UCGIA})",
    booktitle = "Proceedings, American Congress on Surveying and Mapping / American Society for Photogrammetry and Remote Sensing '93",
    year = "1993",
    address = "New Orleans"
}

1992

Renamed local topo report. 1992.
[details]

BibTeX

@misc{wrf-localtopo-92x,
    title = "Renamed local topo report",
    year = "1992"
}

Chandrasekhar Narayanaswami and Wm Randolph Franklin. Boolean combinations of polygons in parallel. In Proceedings of the 1992 International Conference on Parallel Processing, volume. 17–21 Aug 1992.
[details] [full text]

BibTeX

@inproceedings{nf-bcpp-92,
    author = "Narayanaswami, Chandrasekhar and Franklin, Wm Randolph",
    title = "Boolean Combinations of Polygons in Parallel",
    booktitle = "Proceedings of the 1992 International Conference on Parallel Processing",
    month = "17--21 Aug",
    year = "1992",
    volume = "",
    pages = "",
    href = "\bibhref{76-icpp92-boolean}",
    mykey = "chandra",
    keywords = "parallel computation, grids, intersection, CAD"
}

Wm Randolph Franklin. Map overlay area animation and parallel simulation. In David H. Douglas, editor, Proceedings, SORSA'92 Symposium and Workshop, 200–203. July 28–August 2 1992.
[details] [full text]

BibTeX

@inproceedings{f-moaap-92,
    author = "Franklin, Wm Randolph",
    editor = "Douglas, David H.",
    title = "Map Overlay Area Animation and Parallel Simulation",
    booktitle = "Proceedings, SORSA'92 Symposium and Workshop",
    year = "1992",
    month = "July 28--August 2",
    pages = "200--203",
    href = "\bibhref{79-sorsa92-overlay}",
    mykey = "overlay",
    keywords = "parallel computation, intersection, area"
}

Wm Randolph Franklin. Tutorial on curve fitting for GIS. In David H. Douglas, editor, Proceedings, SORSA'92 Symposium and Workshop. July 28–August 2 1992.
[details] [full text]

BibTeX

@inproceedings{f-tcfg-92,
    author = "Franklin, Wm Randolph",
    editor = "Douglas, David H.",
    title = "Tutorial on Curve Fitting for {GIS}",
    booktitle = "Proceedings, SORSA'92 Symposium and Workshop",
    year = "1992",
    optpages = "235--250",
    month = "July 28--August 2",
    href = "\bibhref{77-sorsa92-bezier}",
    keywords = "splines, tutorial"
}

Chandrasekhar Narayanaswami and Wm Randolph Franklin. Edge intersection on the Hypercube computer. Information Processing Letters, 41(5):257–262, 3 April 1992.
[details] [full text]

BibTeX

@article{nf-eihc-92,
    author = "Narayanaswami, Chandrasekhar and Franklin, Wm Randolph",
    title = "Edge Intersection on the {H}ypercube Computer",
    journal = "Information Processing Letters",
    year = "1992",
    volume = "41",
    number = "5",
    month = "3 April",
    pages = "257--262",
    keywords = "parallel algorithms, performance evaluation, intersection, grids",
    mykey = "chandra",
    href = "\bibhref{68-ipl92-hypercube}"
}

WR Franklin. Local topological properties of polyhedra. (unpublished talk), Sept 1992. URL: https://wrfranklin.org/wiki/Research/unpub/localtopo.pdf.
[details]
Abstract
What various data structures are possible to represent polygons and polyhedra? Having only local information about the location and neighborhood of each vertex is sufficient, and surprisingly useful.
BibTeX
```
@unpublished{wrf-localtopo-92,
    author = "Franklin, WR",
    title = "Local topological properties of polyhedra",
    month = "Sept",
    year = "1992",
    note = "(unpublished talk)",
    mykey = "topology",
    url = "https://wrfranklin.org/wiki/Research/unpub/localtopo.pdf"
}
```

1991

Chandrasekhar Narayanaswami and Wm Randolph Franklin. Determination of mass properties of polygonal CSG objects in parallel. In Joshua Turner, editor, Proc. Symposium on Solid Modeling Foundations and CAD/CAM Applications, pages 279–288. ACM/SIGGRAPH, 5–7 June 1991.
[details] [full text]

BibTeX

@incollection{nf-dmppci-91,
    author = "Narayanaswami, Chandrasekhar and Franklin, Wm Randolph",
    editor = "Turner, Joshua",
    title = "Determination of Mass Properties of Polygonal {CSG} Objects in Parallel",
    year = "1991",
    month = "5--7 June",
    pages = "279--288",
    booktitle = "Proc. Symposium on Solid Modeling Foundations and CAD/CAM Applications",
    publisher = "ACM/SIGGRAPH",
    href = "\bibhref{69a-turner91-determination}",
    mykey = "chandra",
    precedes = "nf-dmppcj-91",
    keywords = "parallel computation, intersection, grids, constructive solid geometry, area"
}

Wm Randolph Franklin. Computer systems and low level data structures for GIS. In David Maguire, Mike Goodchild, and David Rhind, editors, Geographical Information Systems, Principles and Applications, volume 1, pages 215–225. Longman Scientific and Technical, London UK, 1991.
[details] [full text]

BibTeX

@incollection{f-cslld-91,
    author = "Franklin, Wm Randolph",
    editor = "Maguire, David and Goodchild, Mike and Rhind, David",
    title = "Computer Systems and Low Level Data Structures for {GIS}",
    booktitle = "Geographical Information Systems, Principles and Applications",
    publisher = "Longman Scientific and Technical",
    address = "London UK",
    year = "1991",
    pages = "215--225",
    volume = "1",
    href = "\bibhref{73-maguire91-gis}",
    keywords = "tutorial"
}

C. Narayanaswami and Wm Randolph Franklin. Determination of mass properties of polygonal CSG objects in parallel. Internat. J. Comput. Geom. Appl., 1(4):381–403, 1991.
[details] [full text]

BibTeX

@article{nf-dmppcj-91,
    author = "Narayanaswami, C. and Franklin, Wm Randolph",
    title = "Determination of mass properties of polygonal {CSG} objects in parallel",
    journal = "Internat. J. Comput. Geom. Appl.",
    volume = "1",
    number = "4",
    year = "1991",
    pages = "381--403",
    href = "\bibhref{69-ijcga91-determination}",
    mykey = "chandra",
    succeeds = "nf-dmppci-91",
    keywords = "parallel computation, intersection, constructive solid geometry, area, grids"
}

Varol Akman, A. Arslan, W. Randolph Franklin, and P. J. W. ten Hagen. Implementing a topological picturebook. In Proc. 13th IMACS World Congress on Computation and Applied Maths. Dublin, 1991.
[details]

BibTeX

@inproceedings{akman-dublin,
    author = "Akman, Varol and Arslan, A. and Franklin, W. Randolph and ten {H}agen, P. J. W.",
    title = "Implementing a Topological Picturebook",
    booktitle = "Proc. 13th IMACS World Congress on Computation and Applied Maths",
    year = "1991",
    address = "Dublin",
    mykey = "akman"
}

W. Randolph Franklin, Rahul Bansal, and Elissa Gilbert. Sensitivity analysis of expert systems. In Uma G. Gupta, editor, Validating and Verifying Knowledge-Based Systems, pages 347–355. IEEE Computer Society Press, 1991.
[details] [full text]

BibTeX

@incollection{wrf-gupta,
    author = "Franklin, W. Randolph and Bansal, Rahul and Gilbert, Elissa",
    editor = "Gupta, Uma G.",
    title = "Sensitivity Analysis of Expert Systems",
    booktitle = "Validating and Verifying Knowledge-Based Systems",
    publisher = "IEEE Computer Society Press",
    year = "1991",
    pages = "347--355",
    href = "\bibhref{51-vv91-sensitivity-es}"
}

1990

Varol Akman, D. Ede, W. Randolph Franklin, and P. J. W. ten Hagen. Mental models of force and motion. In Okyay Kaynak, editor, Proc. IEEE International Workshop on Intelligent Motion Control, volume 1, 153–158. Bogazici University, Istanbul, 20-22 August 1990. IEEE Press. Catalog No. 90TH0272-5.
[details]

BibTeX

@inproceedings{akman-mental,
    author = "Akman, Varol and Ede, D. and Franklin, W. Randolph and ten {H}agen, P. J. W.",
    Editor = "Kaynak, Okyay",
    title = "Mental Models of Force and Motion",
    booktitle = "Proc. {IEEE} International Workshop on Intelligent Motion Control",
    Address = "Bogazici University, Istanbul",
    volume = "1",
    year = "1990",
    Month = "20-22 August",
    pages = "153--158",
    Publisher = "IEEE Press. Catalog No. 90TH0272-5",
    mykey = "akman"
}

Wm Randolph Franklin. Calculating map overlay polygon' areas without explicitly calculating the polygons — implementation. In 4th International Symposium on Spatial Data Handling, 151–160. Zürich, 23-27 July 1990.
[details] [full text]

BibTeX

@inproceedings{f-cmopa-90,
    author = "Franklin, Wm Randolph",
    title = "Calculating Map Overlay Polygon' Areas Without Explicitly Calculating the Polygons --- Implementation",
    booktitle = "4th International Symposium on Spatial Data Handling",
    month = "23-27 July",
    year = "1990",
    pages = "151--160",
    address = "Zürich",
    href = "\bibhref{67-sdh90-overlay}",
    precedes = "fsskn-ofmop-93",
    mykey = "overlay",
    keywords = "intersection, area, grids, measure, polygons"
}

Wm Randolph Franklin, Narayanaswami Chandrasekhar, Mohan Kankanhalli, Varol Akman, and Peter YF Wu. Efficient geometric operations for CAD. In Michael J. Wozny, Joshua U. Turner, and K. Preiss, editors, Geometric Modeling for Product Engineering, pages 485–498. Elsevier Science Publishers B.V. (North-Holland), 1990.
[details] [full text]

BibTeX

@incollection{fckaw-egoc-90,
    author = "Franklin, Wm Randolph and Chandrasekhar, Narayanaswami and Kankanhalli, Mohan and Akman, Varol and Wu, Peter YF",
    editor = "Wozny, Michael J. and Turner, Joshua U. and Preiss, K.",
    title = "Efficient Geometric Operations for {CAD}",
    booktitle = "Geometric Modeling for Product Engineering",
    publisher = "Elsevier Science Publishers B.V. (North-Holland)",
    year = "1990",
    note = "Selected and expanded papers from the IFIP WG 5.2/NSF Working Conference on Geometric Modeling, Rensselaerville, USA, 18-22 September 1988",
    pages = "485--498",
    href = "\bibhref{58-wozny90-efficient}",
    mykey = "topology chandra akman kankanhalli",
    keywords = "intersection, CAD, grids"
}

Wm Randolph Franklin and Mohan Kankanhalli. Parallel object-space hidden surface removal. In Proceedings of SIGGRAPH'90, volume 24, 87–94. August 1990.
[details] [full text]

BibTeX

@inproceedings{fk-poshs-90-in-geom,
    author = "Franklin, Wm Randolph and Kankanhalli, Mohan",
    title = "Parallel Object-Space Hidden Surface Removal",
    booktitle = "Proceedings of SIGGRAPH'90",
    journal = "Comput. Graph.",
    comments = "Dallas, Texas",
    volume = "24",
    month = "August",
    year = "1990",
    pages = "87--94",
    href = "\bibhref{62-siggraph90-parallel}",
    mykey = "vis3dobj kankanhalli",
    keywords = "computer graphics, parallel computation, hidden line/surface elimination, grids"
}

Wm Randolph Franklin and Venkatesh Sivaswami. OVERPROP — calculating areas of map overlay polygons without calculating the overlay. In Canadian National Conference on Geographic Information Systems: Challenge for the 1990's, 1646–1654. Ottawa, 5-8 Mar 1990. Canadian Institute of Surveying and Mapping.
[details] [full text]

BibTeX

@inproceedings{fs-ocamo-90-in-geom,
    author = "Franklin, Wm Randolph and Sivaswami, Venkatesh",
    title = "{OVERPROP} --- Calculating Areas of Map Overlay Polygons without Calculating the Overlay",
    booktitle = "Canadian National Conference on Geographic Information Systems: Challenge for the 1990's",
    publisher = "Canadian Institute of Surveying and Mapping",
    address = "Ottawa",
    pages = "1646--1654",
    month = "5-8 Mar",
    year = "1990",
    href = "\bibhref{61-ottawa90-overlay}",
    mykey = "overlay",
    keywords = "intersection, area, grids"
}

Peter Y.F. Wu and W. Randolph Franklin. A logic programming approach to cartographic map overlay. Journal of Computational Intelligence, 6(2):61–70, May 1990. doi:https://doi.org/10.1111/j.1467-8640.1990.tb00290.x.
[details] [full text]

BibTeX

@article{wu-jci,
    author = "Wu, Peter Y.F. and Franklin, W. Randolph",
    title = "A Logic Programming Approach to Cartographic Map Overlay",
    journal = "Journal of Computational Intelligence",
    volume = "6",
    number = "2",
    month = "May",
    year = "1990",
    pages = "61--70",
    doi = "https://doi.org/10.1111/j.1467-8640.1990.tb00290.x",
    href = "\bibhref{52-ccij90-lp-overlay}",
    mykey = "overlay"
}

1989

Wm. Randolph Franklin. Review of Art Gallery Theorems and Algorithms by Joseph O'Rourke. SIAM Review, 31(2):342–343, June 1989.
[details] [full text]

BibTeX

@article{review-orourke-1989,
    author = "Franklin, Wm. Randolph",
    title = "Review of {Art Gallery Theorems and Algorithms by Joseph O'Rourke}",
    journal = "{SIAM} Review",
    volume = "31",
    number = "2",
    year = "1989",
    pages = "342--343",
    month = "June",
    href = "\bibhref{245-review-orourke-1989}",
    mykey = "review"
}

Varol Akman and Wm Randolph Franklin. Representing objects as rays, or how to pile up an octree? Computers and Graphics, 13(3):373–379, 1989.
[details] [full text]

BibTeX

@article{af-rorhp-89,
    author = "Akman, Varol and Franklin, Wm Randolph",
    title = "Representing Objects as Rays, or How to Pile up an Octree?",
    journal = "Computers and Graphics",
    volume = "13",
    number = "3",
    year = "1989",
    pages = "373--379",
    href = "\bibhref{64-cg89-rays}",
    mykey = "akman",
    keywords = "oct trees, measure, polyhedra, rays"
}

W. Randolph Franklin, Narayanaswami Chandrasekhar, and Mohan Kankanhalli. Parallel algorithms for geometric computing. In Final Program, SIAM Conference on Geometric Design, A17. 6–10 Nov 1989. (abstract only).
[details]

BibTeX

@inproceedings{fck-pagc-siam-89,
    author = "Franklin, W. Randolph and Chandrasekhar, Narayanaswami and Kankanhalli, Mohan",
    title = "Parallel Algorithms for Geometric Computing",
    pages = "A17",
    booktitle = "Final Program, {SIAM} Conference on Geometric Design",
    year = "1989",
    month = "6--10 Nov",
    mykey = "chandra kankanhalli",
    note = "(abstract only)"
}

Varol Akman and Wm Randolph Franklin. Ray representation for k-d trees. Pattern Recognition Letters, pages 315–320, November 1989.
[details] [full text]

BibTeX

@article{af-rrkt-89,
    author = "Akman, Varol and Franklin, Wm Randolph",
    title = "Ray Representation for K-d Trees",
    journal = "Pattern Recognition Letters",
    month = "November",
    year = "1989",
    pages = "315--320",
    href = "\bibhref{66-prl89-ray}",
    mykey = "akman",
    keywords = "oct trees, measure, rays"
}

Wm Randolph Franklin, Mohan Kankanhalli, Chandrasekhar Narayanaswami, and Varol Akman. Efficient intersection calculations in large databases. In International Cartographic Association 14th World Conference, A–62 – A–63. Budapest, August 1989.
[details] [full text]

BibTeX

@inproceedings{f-eiclb-89,
    author = "Franklin, Wm Randolph and Kankanhalli, Mohan and Narayanaswami, Chandrasekhar and Akman, Varol",
    title = "Efficient Intersection Calculations in Large Databases",
    booktitle = "International Cartographic Association 14th World Conference",
    address = "Budapest",
    month = "August",
    year = "1989",
    pages = "A-62 -- A-63",
    href = "\bibhref{60-budapest89-efficient}",
    mykey = "akman chandra kankanhalli",
    keywords = "intersection, grids"
}

Wm Randolph Franklin, Mohan Kankanhalli, and Chandrasekhar Narayanaswami. Efficient primitive geometric operations on large databases. In Proceedings National Conference Challenge for the 1990s GIS Geographic Information Systems, 1247–1256. Ottawa, 27 February - 3 Mar 1989. Canadian Institute of Surveying and Mapping.
[details] [full text]

BibTeX

@inproceedings{fkn-epgol-89,
    author = "Franklin, Wm Randolph and Kankanhalli, Mohan and Narayanaswami, Chandrasekhar",
    title = "Efficient Primitive Geometric Operations on Large Databases",
    booktitle = "Proceedings National Conference Challenge for the 1990s {GIS} Geographic Information Systems",
    address = "Ottawa",
    organization = "Canadian Institute of Surveying and Mapping",
    month = "27 February - 3 Mar",
    year = "1989",
    pages = "1247--1256",
    mykey = "geometry kankanhalli chandra",
    href = "\bibhref{59-ottawa89-efficient}",
    keywords = "intersection, CAD, grids"
}

Varol Akman, Wm Randolph Franklin, Mohan Kankanhalli, and Chandrasekhar Narayanaswami. Geometric computing and the uniform grid data technique. Computer Aided Design, 21(7):410–420, 1989.
[details] [full text]

BibTeX

@article{afkn-gcugd-89,
    author = "Akman, Varol and Franklin, Wm Randolph and Kankanhalli, Mohan and Narayanaswami, Chandrasekhar",
    title = "Geometric Computing and the Uniform Grid Data Technique",
    journal = "Computer Aided Design",
    year = "1989",
    volume = "21",
    number = "7",
    pages = "410--420",
    href = "\bibhref{54-cad89-ug}",
    mykey = "akman chandra kankanhalli",
    keywords = "intersection, CAD, grids"
}

Wm Randolph Franklin, Chandrasekhar Narayanaswami, Mohan Kankanhalli, David Sun, Meng-Chu Zhou, and Peter YF Wu. Uniform grids: a technique for intersection detection on serial and parallel machines. In Proceedings of Auto Carto 9: Ninth International Symposium on Computer-Assisted Cartography, 100–109. Baltimore, Maryland, 2-7 April 1989.
[details] [full text]

BibTeX

@inproceedings{fnkszw-ugtid-89,
    author = "Franklin, Wm Randolph and Narayanaswami, Chandrasekhar and Kankanhalli, Mohan and Sun, David and Zhou, Meng-Chu and Wu, Peter YF",
    title = "Uniform Grids: A Technique for Intersection Detection on Serial and Parallel Machines",
    booktitle = "Proceedings of Auto Carto 9: Ninth International Symposium on Computer-Assisted Cartography",
    year = "1989",
    month = "2-7 April",
    address = "Baltimore, Maryland",
    pages = "100--109",
    href = "\bibhref{57-autocarto89-ug}",
    mykey = "chandra kankanhalli",
    keywords = "parallel computation, intersection, CAD, grids"
}

Varol Akman, W. Randolph Franklin, and B. Veth. Design systems with common sense. In PJW ten Hagen and P. Veerkamp, editors, Proceedings of the Third Eurographics Workshop on Intelligent CAD Systems: Practical Experience and Evaluation, 317–322. Texel, the Netherlands, 3-7 Apr 1989. Springer–Verlag.
[details]

BibTeX

@inproceedings{akman-design-89,
    author = "Akman, Varol and Franklin, W. Randolph and Veth, B.",
    editor = "ten Hagen, PJW and Veerkamp, P.",
    title = "Design Systems with Common Sense",
    booktitle = "Proceedings of the Third Eurographics Workshop on Intelligent CAD Systems: Practical Experience and Evaluation",
    month = "3-7 Apr",
    year = "1989",
    pages = "317--322",
    address = "Texel, the Netherlands",
    publisher = "Springer--Verlag",
    mykey = "akman"
}

1988

Wm. Randolph Franklin. Review of Computational Geometry: An Introduction by Franco P. Preparata and Michael Ian Shamos. SIAM Review, 30(4):669–670, December 1988.
[details] [full text]

BibTeX

@article{review-preparata-shamos-1988,
    author = "Franklin, Wm. Randolph",
    title = "Review of {Computational Geometry: An Introduction by Franco P. Preparata and Michael Ian Shamos}",
    journal = "{SIAM} Review",
    volume = "30",
    number = "4",
    year = "1988",
    pages = "669--670",
    month = "December",
    href = "\bibhref{244-review-preparata-shamos-1988}",
    mykey = "review"
}

W. Randolph Franklin, Rahul Bansal, Elissa Gilbert, and Gautam Shroff. Debugging and tracing expert systems. In Benn R. Konsynski, editor, Proceeding of the 21st International Hawaii International Conference on System Sciences, volume III, 159–167. Kona, Hawaii, January 1988.
[details] [full text]

BibTeX

@inproceedings{wrf-hawaii-88,
    author = "Franklin, W. Randolph and Bansal, Rahul and Gilbert, Elissa and Shroff, Gautam",
    editor = "Konsynski, Benn R.",
    title = "Debugging and Tracing Expert Systems",
    booktitle = "Proceeding of the 21st International Hawaii International Conference on System Sciences",
    volume = "III",
    address = "Kona, Hawaii",
    month = "January",
    year = "1988",
    pages = "159--167",
    href = "\bibhref{48-hawaii88-debuges}"
}

Wm Randolph Franklin. A linear time exact hidden surface algorithm. In Kenneth I. Joy and others, editors, Tutorial: Computer Graphics: Image Synthesis, pages 218–224. 1988.
[details]

BibTeX

@incollection{f-ltehs-88,
    author = "Franklin, Wm Randolph",
    editor = "Joy, Kenneth I. and others",
    title = "A linear time exact hidden surface algorithm",
    booktitle = "Tutorial: Computer Graphics: Image Synthesis",
    year = "1988",
    pages = "218--224",
    succeeds = "f-ltehs-80",
    precedes = "f-ehsao-81",
    mykey = "vis3dobj",
    keywords = "computer graphics, hidden line/surface elimination"
}

Wm Randolph Franklin and Varol Akman. Adaptive grid for polyhedral visibility in object space, an implementation. Computer Journal, 31(1):56–60, February 1988.
[details] [full text]

BibTeX

@article{fa-agpvo-88-in-geom,
    author = "Franklin, Wm Randolph and Akman, Varol",
    title = "Adaptive Grid for polyhedral visibility in object space, an implementation",
    journal = "Computer Journal",
    volume = "31",
    number = "1",
    pages = "56-60",
    month = "February",
    year = "1988",
    href = "\bibhref{43-cj88-polyvis}",
    mykey = "akman vis3dobj",
    keywords = "computer graphics, hidden line/surface elimination"
}

Wm Randolph Franklin, Narayanaswami Chandrasekhar., Mohan Kankanhalli, Manoj Seshan, and Varol Akman. Efficiency of uniform grids for intersection detection on serial and parallel machines. In Nadia Magnenat-Thalmann and D. Thalmann, editors, New Trends in Computer Graphics (Proc. Computer Graphics International'88), pages 288–297. Springer-Verlag, 1988.
[details] [full text]

BibTeX

@incollection{fcksa-eugid-88,
    author = "Franklin, Wm Randolph and Chandrasekhar., Narayanaswami and Kankanhalli, Mohan and Seshan, Manoj and Akman, Varol",
    editor = "Magnenat-Thalmann, Nadia and Thalmann, D.",
    title = "Efficiency of uniform grids for intersection detection on serial and parallel machines",
    booktitle = "New Trends in Computer Graphics (Proc. Computer Graphics International'88)",
    publisher = "Springer-Verlag",
    year = "1988",
    pages = "288--297",
    href = "\bibhref{50-gi88-ug}",
    mykey = "akman chandra kankanhalli",
    keywords = "parallel computation, intersection, grids"
}

WR Franklin, N. Chandrasekhar, M. Kankanhalli, and V. Akman. Fast intersection detection on serial and parallel machines using the uniform grid technique. 1988.
[details] [full text]

BibTeX

@unpublished{fcka-fidspm-88,
    author = "Franklin, WR and Chandrasekhar, N. and Kankanhalli, M. and Akman, V.",
    title = "Fast intersection detection on serial and parallel machines using the uniform grid technique",
    year = "1988",
    note = "",
    href = "\bibhref{53-unpub88-fast}",
    mykey = "akman kankanhalli chandra"
}

1987

Wm Randolph Franklin. Polygon properties calculated from the vertex neighborhoods. In Proc. 3rd Annu. ACM Sympos. Comput. Geom., 110–118. 1987.
[details] [full text]

BibTeX

@inproceedings{f-ppcvn-87,
    author = "Franklin, Wm Randolph",
    title = "Polygon properties calculated from the vertex neighborhoods",
    booktitle = "Proc. 3rd Annu. ACM Sympos. Comput. Geom.",
    year = "1987",
    pages = "110--118",
    oldlabel = "geom-1214",
    href = "\bibhref{46-scg87-vertex}",
    mykey = "topology",
    keywords = "rays, measure, polygons"
}

Wm Randolph Franklin and V. Akman. A workbench to compute unobstructed shortest paths in three-space. In Proc. 1st Internat. Conf. Indust. Applied Math., 1–38. Paris, France, 1987.
[details] [full text]

BibTeX

@inproceedings{fa-wcusp-87,
    author = "Franklin, Wm Randolph and Akman, V.",
    title = "A workbench to compute unobstructed shortest paths in three-space",
    booktitle = "Proc. 1st Internat. Conf. Indust. Applied Math.",
    address = "Paris, France",
    year = "1987",
    pages = "1--38",
    oldlabel = "geom-1319",
    href = "\bibhref{36-siam87-shortest}",
    mykey = "akman pathplan",
    keywords = "motion planning"
}

Wm Randolph Franklin and Varol Akman. A simple and efficient haloed line algorithm for hidden line elimination. Computer Graphics Forum, 6(2):103–109, May 1987.
[details] [full text]

BibTeX

@article{fa-sehla-87,
    author = "Franklin, Wm Randolph and Akman, Varol",
    title = "A simple and efficient haloed line algorithm for hidden line elimination",
    journal = "Computer Graphics Forum",
    volume = "6",
    number = "2",
    pages = "103-109",
    month = "May",
    year = "1987",
    href = "\bibhref{42-cgf87-haloed}",
    mykey = "akman vis3dobj",
    keywords = "computer graphics, hidden line/surface elimination"
}

Wm Randolph Franklin and Peter YF Wu. A polygon overlay system in prolog. In Autocarto 8: Proceedings of the Eighth International Symposium on Computer-Assisted Cartography, 97–106. Baltimore, Maryland, 29 Mar – 3 April 1987.
[details] [full text]

BibTeX

@inproceedings{fw-posp-87,
    author = "Franklin, Wm Randolph and Wu, Peter YF",
    title = "A Polygon Overlay System in Prolog",
    booktitle = "Autocarto 8: Proceedings of the Eighth International Symposium on Computer-Assisted Cartography",
    address = "Baltimore, Maryland",
    month = "29 Mar -- 3 April",
    year = "1987",
    pages = "97--106",
    href = "\bibhref{45-autocarto87-overlay-prolog}",
    mykey = "overlay",
    keywords = "intersection, artificial intelligence"
}

1986

Varol Akman and W. Randolph Franklin. Locus techniques for shortest path problems in robotics. In IFAC Symposium on Robot Control (SYSROCO'85). Barcelona, 1986.
[details] [full text]

BibTeX

@incollection{akman-barcelona-86,
    author = "Akman, Varol and Franklin, W. Randolph",
    title = "Locus Techniques for Shortest Path Problems in Robotics",
    booktitle = "IFAC Symposium on Robot Control (SYSROCO'85)",
    address = "Barcelona",
    year = "1986",
    href = "\bibhref{35-sysroco85-locus}",
    mykey = "akman pathplan"
}

Varol Akman and Wm Randolph Franklin. On the question `is $\sum _1^n \sqrt a_i\le L ?$'. EATCS Bulletin, pages 16–20, February 1986.
[details] [full text]

BibTeX

@article{af-oqiss-86,
    author = "Akman, Varol and Franklin, Wm Randolph",
    title = "On the Question `Is {$\sum\_1^n \sqrt{a\_i}\le L ?$}'",
    journal = "EATCS Bulletin",
    number = "28",
    month = "February",
    year = "1986",
    pages = "16--20",
    href = "\bibhref{38-eatcs86-question}",
    mykey = "akman",
    keywords = "motion planning"
}

Wm Randolph Franklin, Margaret Nichols, Sumitro Samaddar, and Peter YF Wu. Experiences with using prolog for geometry. In Proceedings of Graphics Interface'86, Vision Interface'86, 26–31. Vancouver, BC, 26–30 May 1986.
[details]

BibTeX

@inproceedings{fnsw-eupg-86,
    author = "Franklin, Wm Randolph and Nichols, Margaret and Samaddar, Sumitro and Wu, Peter YF",
    title = "Experiences with Using Prolog for Geometry",
    booktitle = "Proceedings of Graphics Interface'86, Vision Interface'86",
    address = "Vancouver, BC",
    month = "26--30 May",
    year = "1986",
    pages = "26--31",
    keywords = "computer graphics, artificial intelligence"
}

Wm Randolph Franklin, Peter Y.F. Wu, Sumitro Samaddar, and Margaret Nichols. Geometry in prolog. In Tosiyasu Kunii, editor, Advanced Computer Graphics, Proceedings of Computer Graphics Tokyo 86, 71–78. April 1986.
[details] [full text]

BibTeX

@inproceedings{fwsn-gp-86,
    author = "Franklin, Wm Randolph and Wu, Peter Y.F. and Samaddar, Sumitro and Nichols, Margaret",
    editor = "Kunii, Tosiyasu",
    title = "Geometry in Prolog",
    booktitle = "Advanced Computer Graphics, Proceedings of Computer Graphics Tokyo 86",
    month = "April",
    year = "1986",
    pages = "71-78",
    href = "\bibhref{41-tokyo86-geom-prolog}",
    keywords = "computer graphics, artificial intelligence"
}

Wm Randolph Franklin and Varol Akman. Reconstructing visible regions from visible segments. BIT, 26:430–441, 1986.
[details] [full text]

BibTeX

@article{fa-rvrvs-86,
    author = "Franklin, Wm Randolph and Akman, Varol",
    title = "Reconstructing Visible Regions From Visible Segments",
    journal = "BIT",
    volume = "26",
    pages = "430--441",
    year = "1986",
    href = "\bibhref{30-bit86-reconstruct}",
    mykey = "akman",
    keywords = "computer graphics, hidden line/surface elimination"
}

Wm Randolph Franklin, Peter Y.F. Wu, Sumitro Samaddar, and Margaret Nichols. Prolog and geometry projects. IEEE Computer Graphics and Applications, pages 46–55, November 1986.
[details] [full text]

BibTeX

@article{fwsn-pgp-86,
    author = "Franklin, Wm Randolph and Wu, Peter Y.F. and Samaddar, Sumitro and Nichols, Margaret",
    title = "Prolog and Geometry Projects",
    journal = "IEEE Computer Graphics and Applications",
    month = "November",
    year = "1986",
    pages = "46--55",
    href = "\bibhref{44-cga86-prolog}",
    keywords = "computer graphics, artificial intelligence"
}

Wm Randolph Franklin. Problems with raster graphics algorithms. In L.R.A. Kessener, F.J. Peters, and M.L.P. van Lierop, editors, Data Structures for Raster Graphics, proceedings of a Workshop held at Steensel, The Netherlands, June 24–28, 1985, pages 1–8. Springer-Verlag EurographicSeminars, 1986.
[details] [full text]

BibTeX

@incollection{f-prga-85,
    author = "Franklin, Wm Randolph",
    editor = "Kessener, L.R.A. and Peters, F.J. and van Lierop, M.L.P.",
    title = "Problems with Raster Graphics Algorithms",
    booktitle = "Data Structures for Raster Graphics, proceedings of a Workshop held at Steensel, The Netherlands, June 24--28, 1985",
    publisher = "Springer-Verlag EurographicSeminars",
    year = "1986",
    pages = "1--8",
    comments = "(invited presentation)",
    href = "\bibhref{34-eindhoven85-raster}",
    keywords = "computer graphics, discrete geometry"
}

1985

Wm. Randolph Franklin and Peter Y. F. Wu. Convex hull and polygon intersection in Prolog. (presented at SIAM GM&R), 18 Jul 1985.
[details] [full text]

BibTeX

@unpublished{fw-siam85,
    author = "Franklin, Wm. Randolph and Wu, Peter Y. F.",
    title = "Convex hull and polygon intersection in {Prolog}",
    month = "18 Jul",
    year = "1985",
    note = "(presented at SIAM GM\\&R)",
    href = "\bibhref{37-siam85-prolog-hull}"
}

Wm Randolph Franklin. Computational geometry in prolog. In Proceedings of the NATO Advanced Study Institute on Fundamental Algorithms for Computer Graphics, volume 17 of NATO ASI Series F, pages 737–749. Springer-Verlag, Ilkley, Yorkshire, England, 30 March – 12 April 1985.
[details] [full text]

BibTeX

@incollection{f-cgp-85,
    author = "Franklin, Wm Randolph",
    title = "Computational Geometry in Prolog",
    booktitle = "Proceedings of the {NATO} Advanced Study Institute on Fundamental Algorithms for Computer Graphics",
    address = "Ilkley, Yorkshire, England",
    month = "30 March -- 12 April",
    year = "1985",
    publisher = "Springer-Verlag",
    series = "{NATO} {ASI} Series F",
    volume = "17",
    pages = "737--749",
    href = "\bibhref{33-nato85-prolog}",
    keywords = "artificial intelligence"
}

Wm Randolph Franklin and Varol Akman. Shortest paths in 3-space, Voronoi diagrams with barriers, and related complexity and algebraic issues. In Proceedings of the NATO Advanced Study Institute on Fundamental Algorithms for Computer Graphics, volume 17 of NATO ASI Series F, pages 895–917. Springer-Verlag, Ilkley, Yorkshire, England, 30 March – 12 April 1985.
[details] [full text]

BibTeX

@incollection{fa-sp3sv-85,
    author = "Franklin, Wm Randolph and Akman, Varol",
    title = "Shortest Paths in 3-Space, {V}oronoi Diagrams with Barriers, and Related Complexity and Algebraic Issues",
    booktitle = "Proceedings of the {NATO} Advanced Study Institute on Fundamental Algorithms for Computer Graphics",
    address = "Ilkley, Yorkshire, England",
    month = "30 March -- 12 April",
    year = "1985",
    publisher = "Springer-Verlag",
    series = "{NATO} {ASI} Series F",
    volume = "17",
    pages = "895--917",
    href = "\bibhref{31-nato85-shortest}",
    mykey = "akman pathplan",
    keywords = "motion planning"
}

Wm Randolph Franklin and Varol Akman. Shortest paths in 3-space, Voronoi diagrams with barriers, and related complexity and algebraic issues. In L. Basañez, Gabriel A. Ferraté, and George N. Saridis, editors, Robot Control (SYROCO '85): Proceedings of the 1st IFAC Symposium, volume 1, pages 271–275. International Federation of Automatic Control, Barcelona, Spain, 6–8 November 1985.
[details]

BibTeX

@incollection{fa-sp3sv-85a,
    author = "Franklin, Wm Randolph and Akman, Varol",
    editor = "Basañez, L. and Ferraté, Gabriel A. and Saridis, George N.",
    title = "Shortest Paths in 3-Space, {V}oronoi Diagrams with Barriers, and Related Complexity and Algebraic Issues",
    booktitle = "Robot Control ({SYROCO} '85): Proceedings of the 1st {IFAC} Symposium",
    address = "Barcelona, Spain",
    month = "6--8 November",
    year = "1985",
    volume = "1",
    publisher = "International Federation of Automatic Control",
    isbn = "0080334466, 9780080334462",
    pages = "271--275",
    xfulltext = "https://wrfranklin.org/p/31-nato85-shortest.pdf",
    xhref = "\bibhref{31-nato85-shortest}",
    mykey = "akman pathplan",
    keywords = "motion planning"
}

Wm Randolph Franklin and Varol Akman. Building an octree from a set of parallelepipeds. IEEE Computer Graphics and Applications, 5(10):58–64, October 1985.
[details] [full text]

BibTeX

@article{fa-bospj-85,
    author = "Franklin, Wm Randolph and Akman, Varol",
    title = "Building an Octree from a Set of Parallelepipeds",
    journal = "IEEE Computer Graphics and Applications",
    month = "October",
    year = "1985",
    volume = "5",
    number = "10",
    pages = "58-64",
    href = "\bibhref{40-cga85-octree}",
    mykey = "akman",
    succeeds = "fa-bospi-85",
    keywords = "computer graphics, oct trees"
}

Wm Randolph Franklin and Varol Akman. Octree data structures and creation by stacking. In Nadia Magenat-Thalmann, editor, Computer Generated Images, State of the Art. Springer-Verlag, 1985.
[details] [full text]

BibTeX

@incollection{fa-odscs-85,
    author = "Franklin, Wm Randolph and Akman, Varol",
    editor = "Magenat-Thalmann, Nadia",
    title = "Octree Data Structures and Creation by Stacking",
    booktitle = "Computer Generated Images, State of the Art",
    publisher = "Springer-Verlag",
    year = "1985",
    href = "\bibhref{39-cgi85-octree-stack}",
    mykey = "akman",
    keywords = "computer graphics, oct trees"
}

Wm Randolph Franklin, Varol Akman, and Colin Verrilli. Voronoi diagrams with barriers and on polyhedra for minimal path planning. Visual Comput., 1(2):133–150, October 1985.
[details] [full text]

BibTeX

@article{fav-vdbpm-85,
    author = "Franklin, Wm Randolph and Akman, Varol and Verrilli, Colin",
    title = "Voronoi diagrams with barriers and on polyhedra for minimal path planning",
    journal = "Visual Comput.",
    volume = "1",
    number = "2",
    month = "October",
    year = "1985",
    pages = "133--150",
    oldlabel = "geom-1246",
    href = "\bibhref{18-vc85-voronoi}",
    mykey = "akman pathplan",
    keywords = "robotics, planar partitions, motion planning, Voronoi diagrams"
}

Wm Randolph Franklin and Varol Akman. Building an octree from a set of parallelepipeds. In Graphics Interface. 1985.
[details] [full text]

BibTeX

@inproceedings{fa-bospi-85,
    author = "Franklin, Wm Randolph and Akman, Varol",
    title = "Building an Octree from a Set of Parallelepipeds",
    booktitle = "Graphics Interface",
    year = "1985",
    precedes = "fa-bospj-85",
    keywords = "computer graphics, oct trees, CAD",
    mykey = "akman",
    href = "\bibhref{29-gi85-building}"
}

Varol Akman and W. Randolph Franklin. Partitioning the space to calculate shortest paths to any goal around polyhedral obstacles. In Proceedings of ROBEXS'85, the First Annual Workshop on Robotics and Expert Systems. NASA/Johnson Space Center, 27–28 June 1985.
[details] [full text]

BibTeX

@inproceedings{akman-robexs-85,
    author = "Akman, Varol and Franklin, W. Randolph",
    title = "Partitioning the Space to Calculate Shortest Paths to any Goal Around Polyhedral Obstacles",
    booktitle = "Proceedings of ROBEXS'85, the First Annual Workshop on Robotics and Expert Systems",
    address = "NASA/Johnson Space Center",
    month = "27--28 June",
    year = "1985",
    href = "\bibhref{32-robexs85-shortest}",
    mykey = "pathplan akman"
}

1984

Wm Randolph Franklin. Cartographic errors symptomatic of underlying algebra problems. In Proc. International Symposium on Spatial Data Handling, volume 1, 190–208. Zürich, 20–24 August 1984.
[details] [full text]

BibTeX

@inproceedings{f-cesua-84,
    author = "Franklin, Wm Randolph",
    title = "Cartographic Errors Symptomatic of Underlying Algebra Problems",
    booktitle = "Proc. International Symposium on Spatial Data Handling",
    volume = "1",
    month = "20--24 August",
    year = "1984",
    address = "Zürich",
    pages = "190--208",
    href = "\bibhref{27-sdh84-cartoerrs}"
}

Wm Randolph Franklin. Adaptive grids for geometric operations. Cartographica, 21(2–3):161–167, Summer – Autumn 1984. monograph 32–33.
[details] [full text]

BibTeX

@article{f-aggo-84,
    author = "Franklin, Wm Randolph",
    title = "Adaptive Grids for geometric operations",
    journal = "Cartographica",
    volume = "21",
    number = "2--3",
    pages = "161--167",
    month = "Summer -- Autumn",
    year = "1984",
    note = "monograph 32--33",
    succeeds = "f-aggo-83",
    href = "\bibhref{23-cartographica86-grid}",
    keywords = "intersection, grids"
}

Wm Randolph Franklin and Varol Akman. Shortest paths between source and goal points located on/around a convex polyhedron. In 22nd Annual Allerton Conference on Communication, Control, and Computing. Urbana, Illinois, USA, 3–5 October 1984.
[details] [full text]

BibTeX

@inproceedings{fa-spsgo-84,
    author = "Franklin, Wm Randolph and Akman, Varol",
    title = "Shortest Paths Between Source and Goal Points Located On/Around a Convex Polyhedron",
    booktitle = "22nd Annual Allerton Conference on Communication, Control, and Computing",
    month = "3--5 October",
    year = "1984",
    address = "Urbana, Illinois, USA",
    href = "\bibhref{26-allerton84-shortest}",
    mykey = "akman pathplan",
    keywords = "motion planning"
}

W. Randolph Franklin. A simpler iterative solution to the Towers of Hanoi problem. SIGPLAN Notices, 19(8):87–88, August 1984.
[details] [full text]

BibTeX

@article{wrf-sigplan-84,
    author = "Franklin, W. Randolph",
    title = "A Simpler Iterative Solution to the {T}owers of {H}anoi Problem",
    journal = "SIGPLAN Notices",
    volume = "19",
    number = "8",
    month = "August",
    year = "1984",
    pages = "87--88",
    href = "\bibhref{28-sigplan84-hanoi}"
}

1983

Wm Randolph Franklin. Rays — new representation for polygons and polyhedra. Computer Graphics and Image Processing, 22:327–338, 1983.
[details] [full text]

BibTeX

@article{f-rnrpp-83,
    author = "Franklin, Wm Randolph",
    title = "RAYS --- New Representation for Polygons and Polyhedra",
    journal = "Computer Graphics and Image Processing",
    volume = "22",
    year = "1983",
    pages = "327--338",
    href = "\bibhref{13-cvgip83-rays}",
    keywords = "measure, polygons, rays"
}

Wm Randolph Franklin. Efficient rotation of an object. IEEE Trans. Comput., C-32(11):1064–1067, November 1983.
[details] [full text]

BibTeX

@article{f-ero-83,
    author = "Franklin, Wm Randolph",
    title = "Efficient Rotation of an Object",
    journal = "IEEE Trans. Comput.",
    volume = "C-32",
    number = "11",
    month = "November",
    year = "1983",
    pages = "1064--1067",
    href = "\bibhref{16-ieeetc83-rotation}",
    keywords = "computer graphics, CAD"
}

Wm Randolph Franklin. A simplified map overlay algorithm. In Harvard Computer Graphics Conference. Cambridge, Mass, USA, 31 July – 4 August 1983.
[details] [full text]

BibTeX

@inproceedings{fsmoa-83,
    author = "Franklin, Wm Randolph",
    title = "A Simplified Map Overlay Algorithm",
    booktitle = "Harvard Computer Graphics Conference",
    address = "Cambridge, Mass, USA",
    month = "31 July -- 4 August",
    year = "1983",
    mykey = "overlay",
    href = "\bibhref{22-harvard83-overlay}",
    keywords = "intersection"
}

Wm Randolph Franklin. Adaptive grids for geometric operations. In Barry S Wellar, editor, Proc. Sixth International Symposium on Automated Cartography (Auto-Carto Six), Volume II: Automated Cartography: international perspectives on achievements and challenges, 230–239. Ottawa, 1983.
[details]

BibTeX

@inproceedings{f-aggo-83,
    author = "Franklin, Wm Randolph",
    editor = "Wellar, Barry S",
    title = "Adaptive Grids for geometric operations",
    booktitle = "Proc. Sixth International Symposium on Automated Cartography (Auto-Carto Six), Volume II: Automated Cartography: international perspectives on achievements and challenges",
    pages = "230--239",
    address = "Ottawa",
    year = "1983",
    precedes = "wrf-aggo-84",
    keywords = "intersection, grids"
}

W. Randolph Franklin. Software aspects of business graphics. Computers and Graphics, 1983. (invited paper).
[details] [full text]

BibTeX

@article{wrf-business-83,
    author = "Franklin, W. Randolph",
    title = "Software Aspects of Business Graphics",
    journal = "Computers and Graphics",
    volume = "7",
    number = "1",
    year = "1983",
    href = "\bibhref{20-cag83-swaspects}",
    note = "(invited paper)"
}

1982

W. Randolph Franklin. Software engineering reasons for vlsi design methodology. In IEEE Computer Society Workshop Report: VLSI and Software Engineering Workshop, pages 86–89. Port Chester, NY, USA, 4–6 October 1982.
[details] [full text]

BibTeX

@incollection{wrf-vlsi-82,
    author = "Franklin, W. Randolph",
    title = "Software Engineering Reasons for VLSI Design Methodology",
    booktitle = "IEEE Computer Society Workshop Report: VLSI and Software Engineering Workshop",
    month = "4--6 October",
    year = "1982",
    address = "Port Chester, NY, USA",
    pages = "86--89",
    href = "\bibhref{21-portchester82-vlsi}"
}

W. Randolph Franklin. Program translates statistics into 3-D color map of europe. IEEE Computer and Applications, 2(5):front cover and p. 4, July 1982. (invited).
[details]

BibTeX

@article{wrf-cga-82,
    author = "Franklin, W. Randolph",
    title = "Program Translates Statistics into 3-{D} Color Map of Europe",
    journal = "IEEE Computer and Applications",
    volume = "2",
    number = "5",
    month = "July",
    year = "1982",
    pages = "front cover and p. 4",
    note = "(invited)"
}

W. Randolph Franklin. On an improved algorithm for decentralized extrema finding. Comm. ACM, 25(5):336–337, May 1982.
[details] [full text]

BibTeX

@article{wrf-cacm-82,
    author = "Franklin, W. Randolph",
    title = "On an Improved Algorithm for Decentralized Extrema Finding",
    journal = "Comm. ACM",
    volume = "25",
    number = "5",
    month = "May",
    year = "1982",
    pages = "336--337",
    href = "\bibhref{14-cacm82-ring}"
}

G. Wazzan, W. Randolph Franklin, W. R. Spillers, A. Greenwood, T. F. Gantry, and H. Chu. Simulation of buried power transmission systems: some computer graphics options. Computers and Graphics, 6(1):7–14, 1982.
[details] [full text]

BibTeX

@article{wrf-cg-82,
    author = "Wazzan, G. and Franklin, W. Randolph and Spillers, W. R. and Greenwood, A. and Gantry, T. F. and Chu, H.",
    title = "Simulation of Buried Power Transmission Systems: Some Computer Graphics Options",
    journal = "Computers and Graphics",
    volume = "6",
    number = "1",
    year = "1982",
    pages = "7--14",
    href = "\bibhref{12-cg82-buried-power}"
}

Wm Randolph Franklin. Efficient polyhedron intersection and union. In Proc. Graphics Interface, 73–80. Toronto, 1982.
[details] [full text]

BibTeX

@inproceedings{f-epiu-82,
    author = "Franklin, Wm Randolph",
    title = "Efficient polyhedron intersection and union",
    booktitle = "Proc. Graphics Interface",
    pages = "73-80",
    address = "Toronto",
    year = "1982",
    href = "\bibhref{15-gi82-xsect}",
    mykey = "topology",
    keywords = "intersection, CAD"
}

1981

Wm Randolph Franklin. An exact hidden sphere algorithm that operates in linear time. Comput. Graph. Image Process., 15:364–379, 1981.
[details] [full text]

BibTeX

@article{f-ehsao-81,
    author = "Franklin, Wm Randolph",
    title = "An exact hidden sphere algorithm that operates in linear time",
    journal = "Comput. Graph. Image Process.",
    volume = "15",
    year = "1981",
    pages = "364--379",
    oldlabel = "geom-224",
    href = "\bibhref{8-cgip81-hsa}",
    succeeds = "f-ltehs-80",
    mykey = "vis3dobj",
    keywords = "computer graphics, hidden line/surface elimination"
}

Wm Randolph Franklin. 3-D geometric databases using hierarchies of inscribing boxes. In Proceedings of the 7th Canadian Man-Computer Conference, 173–180. Waterloo, Ontario, Canada, 10–12 June 1981.
[details] [full text]

BibTeX

@inproceedings{f-3gduh-81,
    author = "Franklin, Wm Randolph",
    title = "3-{D} Geometric Databases Using Hierarchies of Inscribing Boxes",
    booktitle = "Proceedings of the 7th Canadian Man-Computer Conference",
    month = "10--12 June",
    year = "1981",
    address = "Waterloo, Ontario, Canada",
    pages = "173--180",
    href = "\bibhref{10-waterloo81-inscribing}",
    keywords = "computer graphics, CAD"
}

W. Randolph Franklin and Alan H. Barr. Faster calculation of superquadric shapes. IEEE Computer Graphics and Applications, 1(3):41–47, July 1981.
[details] [full text]

BibTeX

@article{wrf-cga-81,
    author = "Franklin, W. Randolph and Barr, Alan H.",
    title = "Faster Calculation of Superquadric Shapes",
    journal = "IEEE Computer Graphics and Applications",
    volume = "1",
    number = "3",
    month = "July",
    year = "1981",
    pages = "41--47",
    href = "\bibhref{11-cga81-superquadrics}"
}

1980

Wm Randolph Franklin. A linear time exact hidden surface algorithm. Comput. Graph., 14(3):117–123, 1980.
[details] [full text]

BibTeX

@article{f-ltehs-80-in-geom,
    author = "Franklin, Wm Randolph",
    title = "A linear time exact hidden surface algorithm",
    booktitle = "Proc. SIGGRAPH '80",
    journal = "Comput. Graph.",
    volume = "14",
    number = "3",
    year = "1980",
    pages = "117--123",
    oldlabel = "geom-223",
    precedes = "f-ltehs-88",
    href = "\bibhref{7-siggraph80-linear-hsa}",
    keywords = "computer graphics, hidden line/surface elimination",
    mykey = "vis3dobj",
    portal = "\url{http://portal.acm.org/citation.cfm?id= 807480\&dl= GUIDE\&coll= GUIDE\&CFID= 52002891\&CFTOKEN= 56467748}"
}

1979

Wm Randolph Franklin. Evaluation of algorithms to display vector plots on raster devices. Computer Graphics and Image Processing, 11(4):377–397, December 1979.
[details]

BibTeX

@article{f-eadvp-79,
    author = "Franklin, Wm Randolph",
    title = "Evaluation of Algorithms to Display Vector Plots on Raster Devices",
    journal = "Computer Graphics and Image Processing",
    volume = "11",
    number = "4",
    month = "December",
    year = "1979",
    pages = "377--397",
    keywords = "computer graphics, CAD, discrete geometry"
}

W. Randolph Franklin. Padded lists—set operations in $O(log log N)$ time. Information Processing Letters, 9(4):161–166, November 1979.
[details] [full text]

BibTeX

@article{wrf-ipl-79,
    author = "Franklin, W. Randolph",
    title = "Padded Lists---Set Operations in {$O(log log N)$} Time",
    journal = "Information Processing Letters",
    volume = "9",
    number = "4",
    month = "November",
    year = "1979",
    pages = "161--166",
    href = "\bibhref{3-ipl79-padded}"
}

W. Randolph Franklin. Prism — a prism plotting program. In Allan H. Schmidt, editor, Mapping Software and Cartographic Data Bases, Harvard Library of Computer Mapping, 1979 collection, pages 75–79. 1979.
[details]

BibTeX

@incollection{wrf-prism-hu,
    author = "Franklin, W. Randolph",
    editor = "Schmidt, Allan H.",
    title = "Prism --- A Prism Plotting Program",
    booktitle = "Mapping Software and Cartographic Data Bases",
    year = "1979",
    pages = "75--79",
    mykey = "vis3dobj",
    series = "Harvard Library of Computer Mapping, 1979 collection"
}

1978

Wm Randolph Franklin and Harry R. Lewis. 3-D graphic display of discrete spatial data by prism maps. In Proc. SIGGRAPH'78, volume 12(3), 70–75. August 1978.
[details] [full text]

BibTeX

@inproceedings{fl-3gdds-78,
    author = "Franklin, Wm Randolph and Lewis, Harry R.",
    title = "3-{D} Graphic Display of Discrete Spatial Data By Prism Maps",
    booktitle = "Proc. {SIGGRAPH}'78",
    journal = "Computer Graphics",
    volume = "12(3)",
    month = "August",
    year = "1978",
    pages = "70--75",
    keywords = "computer graphics, hidden line/surface elimination",
    mykey = "vis3dobj",
    href = "\bibhref{5b-sig78-prism}"
}

Wm Randolph Franklin. Combinatorics of hidden surface algorithms. Technical Report, Center for Research in Computing Technology, Harvard Univ., Cambridge, MA, June 1978.
[details] [full text]

BibTeX

@phdthesis{f-chsa-78,
    author = "Franklin, Wm Randolph",
    title = "Combinatorics of hidden surface algorithms",
    type = "Technical {Report}",
    number = "TR-12-78",
    school = "Center for Research in Computing Technology, Harvard Univ.",
    address = "Cambridge, MA",
    year = "1978",
    month = "June",
    oldlabel = "geom-221",
    href = "\bibhrefthesis{0-harvard78-thesis}",
    comments = "Thesis w/o appendices available as a TR from CRCT. Complete thesis available only on microfilm from Harvard, since Harvard did not then subscribe to UMI.",
    mykey = "vis3dobj",
    keywords = "computer graphics, hidden line/surface elimination"
}

William G. Nisen and W. Randolph Franklin. The maturation of computer graphics. ICP Interface Manufacturing and Engineering, 3(4):5–11, 1978.
[details] [full text]

BibTeX

@article{nisen-maturation-78,
    author = "Nisen, William G. and Franklin, W. Randolph",
    title = "The Maturation of Computer Graphics",
    journal = "ICP Interface Manufacturing and Engineering",
    volume = "3",
    number = "4",
    year = "1978",
    pages = "5--11",
    href = "\bibhref{2-nisen78-maturation}"
}

1973

Wm. Randolph Franklin. Triangulated irregular network program. 1973. accessed 30 Oct 2008. URL: http://wrfranklin.org/wiki/Research/tin73.tgz.
[details]

BibTeX

@misc{tin-code-73,
    author = "Franklin, Wm. Randolph",
    title = "Triangulated Irregular Network Program",
    url = "http://wrfranklin.org/wiki/Research/tin73.tgz",
    note = "accessed 30 Oct 2008",
    year = "1973"
}