W. Randolph
Franklin.

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.

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

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

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",
    href = "\bibhref{234-implementing-sos-2022}",
    mykey = "recent salles parallel overlay homepage-selected"
}

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

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",
    note = "arXiv 2006.16783",
    href = "\bibhref{237-siting-thousands-2020}",
    mykey = "recent salles parallel visibility visviewshedsiting wenlili homepage-selected"
}