Parallel papers · W. Randolph Franklin

Our publications in parallel geometry

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}"
}
```

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."
}
```
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

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"
}
```

2017

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"
}
```
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"
}
```
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"
}
```
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"
}
```

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"
}

Wenli Li. GPU-accelerated terrain processing. PhD thesis, Rensselaer Polytechnic Institute, 2016.
[details] [full text]
Abstract
This thesis extends Overdetermined Laplacian Partial Differential Equations (ODETLAP) for spatial data approximation and compression and parallelizes multiple observer siting on terrain, using General-Purpose Computing on Graphics Processing Units (GPGPU). Both ODETLAP compression and multiple observer siting use greedy algorithms that are parallelizable within iterations but sequential between iterations. They also demonstrate terrain-related research and applications that benefit from GPU acceleration and showcase the achievable speedups. ODETLAP approximation approximates a spatial dataset from scattered data points on a regular grid by solving an overdetermined system of linear equations that minimizes the absolute Laplacian of the approximation and the value errors of the data points. We show that ODETLAP approximation is a linear operator and is comparable in accuracy with natural neighbor interpolation and the multiquadric-biharmonic method. Using ODETLAP approximation to approximate spatial datasets, ODETLAP compression compresses a dataset as a set of known points and their values and decompresses it as an approximation from the known points. We implement ODETLAP approximation and compression using the CUSP library and the speedup is 8 times on a GPU. We design multiple algorithms to improve the accuracy of ODETLAP compression using a limited number of known points and use them to compress 2D terrain datasets and 3D MRI datasets. The results show that ODETLAP compression is 30% to 50% better in minimizing the maximum absolute error than JPEG 2000 for the terrain datasets and 40% to 60% better than JP3D for the MRI datasets. To further increase speed, we design a segmented ODETLAP compression algorithm and use it to compress larger 3D atmospheric and MRI datasets. The results show that the compressed size of the dataset is 60% that of JP3D for the same maximum absolute error. Multiple observer siting places multiple observer points above a terrain to maximize the total area visible from at least one observer. The algorithm first selects a set of highly visible points as tentative observers, and then iteratively selects observers to maximize the cumulative viewshed. We improve the time and space complexities of the algorithm and parallelize it using CUDA on a GPU and using OpenMP on multi-core CPUs. The speedup is up to 60 times on the GPU and 16 times on two CPUs with 16 cores.
BibTeX
```
@phdthesis{wenli-phd,
    author = "Li, Wenli",
    title = "{GPU}-accelerated terrain processing",
    school = "Rensselaer Polytechnic Institute",
    mykey = "wenlili visviewshedsiting gpusiting parallel theses",
    year = "2016"
}
```

2015

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"
}
```

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"
}

2014

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"
}
```
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"
}
```
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

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"
}
```

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, 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"
}
```

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"
}
```

2004

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}"
}

1995

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"
}
```

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"
}