{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T18:55:32Z","timestamp":1774637732964,"version":"3.50.1"},"reference-count":58,"publisher":"Association for Computing Machinery (ACM)","issue":"4","funder":[{"name":"National Research Agency under the Investments for the future program","award":["ANR-18-EURE-0017"],"award-info":[{"award-number":["ANR-18-EURE-0017"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2025,8,1]]},"abstract":"<jats:p>We present a novel comprehensive construction algorithm of Apollonius diagrams designed for GPUs. Efficient and robust algorithms have been proposed for the computation of Voronoi diagrams or Power diagrams. In contrast, Apollonius cells are neither convex nor bounded by straight boundaries, making their computation complex, especially in more than two dimensions. Their parallel computation also represents a challenge because of the sequential nature of state-of-the-art algorithms. In this article, we tackle the computation of these diagrams from the geometry of their cells. Our strategy is based on a core cell topology update allowing the iterative insertion of new sites found through nearest neighbor queries. To benefit from the highly parallel environment of modern GPUs and fit their memory restriction, we define a lightweight data structure allowing the representation of the complex topology of Apollonius cells. Additionally, we provide several space exploration procedures for their efficient construction under both homogeneous and heterogeneous spatial distributions. Our method outperforms the fastest state-of-the-art CPU implementation while computing the complete geometry. As a possible use case, we show an application for molecular illustration.<\/jats:p>","DOI":"10.1145\/3730868","type":"journal-article","created":{"date-parts":[[2025,7,27]],"date-time":"2025-07-27T04:02:22Z","timestamp":1753588942000},"page":"1-15","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["In Search of Empty Spheres: 3D Apollonius Diagrams on GPU"],"prefix":"10.1145","volume":"44","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1510-557X","authenticated-orcid":false,"given":"Cyprien","family":"Plateau-Holleville","sequence":"first","affiliation":[{"name":"Universit\u00e9 de Limoges, Limoges, France"},{"name":"XLIM, Limoges, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3375-483X","authenticated-orcid":false,"given":"Benjamin","family":"Stamm","sequence":"additional","affiliation":[{"name":"Universit\u00e4t Stuttgart, Stuttgart, Germany"},{"name":"Institute of Applied Analysis and Numerical Simulation, Stuttgart, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5242-1585","authenticated-orcid":false,"given":"Vincent","family":"Nivoliers","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Claude Bernard Lyon 1, Lyon, France"},{"name":"LIRIS, Lyon, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-5723-1827","authenticated-orcid":false,"given":"Maxime","family":"Maria","sequence":"additional","affiliation":[{"name":"Universit\u00e9 de Limoges, Limoges, France"},{"name":"XLIM, Limoges, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2820-8076","authenticated-orcid":false,"given":"St\u00e9phane","family":"M\u00e9rillou","sequence":"additional","affiliation":[{"name":"Universit\u00e9 de Limoges, Limoges, France"},{"name":"XLIM, Limoges, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,7,27]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/0216006"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/116873.116880"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/235815.235821"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.142610"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/28.1.235"},{"key":"e_1_2_2_6_1","volume-title":"Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Boissonnat J-D.","year":"2084","unstructured":"J-D. Boissonnat and M. I. Karavelas. 2003. On the Combinatorial Complexity of Euclidean Voronoi Cells and Convex Hulls of D-Dimensional Spheres. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (Baltimore, Maryland) (SODA '03). Society for Industrial and Applied Mathematics, USA, 305\u2013312. https:\/\/hal.inria.fr\/inria-00072084\/document"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-33259-6_2"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.14778"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/24.2.162"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1778765.1778784"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.14609"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.20382\/JOCG.V8I1A11"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3528223.3530176"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2004.02.006"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/s0167-8396(03)00027-x"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32241-9_23"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1002\/(sici)1096-987x(19970715)18:9"},{"key":"e_1_2_2_18_1","volume-title":"Fast Fixed-Radius Nearest Neighbors: Interactive Million-Particle Fluids. In GPU Technology Conference (GTC).","author":"Hoetzlein R.","year":"2014","unstructured":"R. Hoetzlein. 2014. Fast Fixed-Radius Nearest Neighbors: Interactive Million-Particle Fluids. In GPU Technology Conference (GTC)."},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1080\/16864360.2016.1273576"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","unstructured":"B. Johnston. 2023. Brady A Johnston\/Molecular Nodes: Molecular Nodes v2.2.0 for Blender 3.4.X. 10.5281\/ZENODO.7498428","DOI":"10.5281\/ZENODO.7498428"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","unstructured":"M. Kamarianakis. 2020. Predicates of the 3D Apollonius Diagram. 10.48550\/ARXIV.2007.06658","DOI":"10.48550\/ARXIV.2007.06658"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45749-6_52"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/2383795.2383801"},{"key":"e_1_2_2_24_1","volume-title":"Proceedings of the 16th Canadian Conference on Computational Geometry, CCCG'04","author":"Kim D-S.","year":"2004","unstructured":"D-S. Kim, Y. Cho, and D. Kim. 2004. Edge-tracing algorithm for euclidean voronoi diagram of 3d spheres. In Proceedings of the 16th Canadian Conference on Computational Geometry, CCCG'04, Concordia University, Montr\u00e9al, Qu\u00e9bec, Canada, August 9\u201311, 2004. 176\u2013179."},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2005.11.007"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.12928"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jet.2023.105675"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2022.103374"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33573-0_21"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-14-s19-s5"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/tvcg.2011.259"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1002\/jcc.25828"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.12870"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2015.09.017"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISVD.2007.7"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1002\/jcc.20484"},{"key":"e_1_2_2_37_1","first-page":"1","article-title":"Performance Comparison of Bounding Volume Hierarchies for GPU Ray Tracing","volume":"11","author":"Meister D.","year":"2022","unstructured":"D. Meister and J. Bittner. 2022. Performance Comparison of Bounding Volume Hierarchies for GPU Ray Tracing. Journal of Computer Graphics Techniques 11, 4 (2022), 1\u201319.","journal-title":"Journal of Computer Graphics Techniques"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1080\/13658816.2012.655742"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","unstructured":"M. K. Mukundan S. B. Thayyil and R. Muthuganapathy. 2022. A parallel algorithm for computing Voronoi diagram of a set of spheres using restricted lower envelope approach and topology matching. Computers & Graphics 106 (Aug. 2022) 210\u2013221. 10.1016\/j.cag.2022.05.017","DOI":"10.1016\/j.cag.2022.05.017"},{"key":"e_1_2_2_40_1","unstructured":"NVIDIA. 2023. NVIDIA ADA LOVELACE PROFESSIONAL GPU ARCHITECTURE. https:\/\/images.nvidia.com\/aem-dam\/en-zz\/Solutions\/technologies\/NVIDIA-ADA-GPU-PROVIZ-Architecture-Whitepaper_1.1.pdf"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btq720"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1002\/jcc.23538"},{"key":"e_1_2_2_43_1","volume-title":"PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation. Technical Report HMC-CS-2014-0905.","author":"O'Neill M. E.","year":"2014","unstructured":"M. E. O'Neill. 2014. PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation. Technical Report HMC-CS-2014-0905. Claremont, CA."},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1002\/nme.5947"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3272127.3275092"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1111411.1111431"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1063\/1.3215722"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.13247"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10707-007-0034-z"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1099\/jgv.0.001730"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dib.2022.108605"},{"key":"e_1_2_2_52_1","unstructured":"The CGAL Project. 2023. CGAL User and Reference Manual (5.6 ed.). CGAL Editorial Board. https:\/\/doc.cgal.org\/5.6\/Manual\/packages.html"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.14125"},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/24.2.167"},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/1899950.1899958"},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","unstructured":"Will H.-M. 1999. Computation of additively weighted Voronoi cells for applications in molecular biology. Ph. D. Dissertation. 10.3929\/ETHZ-A-00384556210.3929\/ethz-a-006652878","DOI":"10.3929\/ETHZ-A-00384556210.3929\/ethz-a-006652878"},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1002\/prot.22052"},{"key":"e_1_2_2_58_1","doi-asserted-by":"publisher","unstructured":"S. Zhukov A. Iones and G. Kronin. 1998. An ambient light illumination model. (1998) 45\u201355. 10.1007\/978-3-7091-6453-2_5","DOI":"10.1007\/978-3-7091-6453-2_5"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3730868","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T17:56:21Z","timestamp":1774634181000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3730868"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,27]]},"references-count":58,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,8,1]]}},"alternative-id":["10.1145\/3730868"],"URL":"https:\/\/doi.org\/10.1145\/3730868","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,7,27]]},"assertion":[{"value":"2025-01-23","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-03-29","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-07-27","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}