W. Randolph
Franklin.

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.

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

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.

@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",
      journal = "J. Computer Aided Design",
      doi = "https://doi.org/10.1016/j.cad.2022.103285"
  }

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.

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