{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,20]],"date-time":"2026-01-20T03:43:00Z","timestamp":1768880580088,"version":"3.49.0"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2020,11,7]],"date-time":"2020-11-07T00:00:00Z","timestamp":1604707200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["DGE-154362, CNS-1565314, and CNS-1838271"],"award-info":[{"award-number":["DGE-154362, CNS-1565314, and CNS-1838271"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Math. Softw."],"published-print":{"date-parts":[[2020,12,31]]},"abstract":"<jats:p>DELAUNAYSPARSE contains both serial and parallel codes written in Fortran 2003 (with OpenMP) for performing medium- to high-dimensional interpolation via the Delaunay triangulation. To accommodate the exponential growth in the size of the Delaunay triangulation in high dimensions, DELAUNAYSPARSE computes only a sparse subset of the complete Delaunay triangulation, as necessary for performing interpolation at the user specified points. This article includes algorithm and implementation details, complexity and sensitivity analyses, usage information, and a brief performance study.<\/jats:p>","DOI":"10.1145\/3422818","type":"journal-article","created":{"date-parts":[[2020,11,7]],"date-time":"2020-11-07T17:07:56Z","timestamp":1604768876000},"page":"1-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["Algorithm 1012"],"prefix":"10.1145","volume":"46","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9541-7041","authenticated-orcid":false,"given":"Tyler H.","family":"Chang","sequence":"first","affiliation":[{"name":"Virginia Polytechnic Institute and State University, Blacksburg, VA"}]},{"given":"Layne T.","family":"Watson","sequence":"additional","affiliation":[{"name":"Virginia Polytechnic Institute and State University, Blacksburg, VA"}]},{"given":"Thomas C. H.","family":"Lux","sequence":"additional","affiliation":[{"name":"Virginia Polytechnic Institute and State University, Blacksburg, VA"}]},{"given":"Ali R.","family":"Butt","sequence":"additional","affiliation":[{"name":"Virginia Polytechnic Institute and State University, Blacksburg, VA"}]},{"given":"Kirk W.","family":"Cameron","sequence":"additional","affiliation":[{"name":"Virginia Polytechnic Institute and State University, Blacksburg, VA"}]},{"given":"Yili","family":"Hong","sequence":"additional","affiliation":[{"name":"Virginia Polytechnic Institute and State University, Blacksburg, VA"}]}],"member":"320","published-online":{"date-parts":[[2020,11,7]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3374219"},{"key":"e_1_2_2_2_1","doi-asserted-by":"crossref","unstructured":"E. Anderson Z. Bai C. Bischof S. Blackford J. Demmel J. Dongarra J. Du Croz A. Greenbaum S. Hammarling A. McKenney and D. Sorensen. 1999. LAPACK Users\u2019 Guide 3rd ed. SIAM Philidelphia PA.  E. Anderson Z. Bai C. Bischof S. Blackford J. Demmel J. Dongarra J. Du Croz A. Greenbaum S. Hammarling A. McKenney and D. Sorensen. 1999. LAPACK Users\u2019 Guide 3rd ed. SIAM Philidelphia PA.","DOI":"10.1137\/1.9780898719604"},{"key":"e_1_2_2_3_1","doi-asserted-by":"crossref","unstructured":"F. Aurenhammer R. Klein and D. T. Lee. 2013. Voronoi Diagrams and Delaunay Triangulations. World Scientific Hackensack NJ.  F. Aurenhammer R. Klein and D. T. Lee. 2013. Voronoi Diagrams and Delaunay Triangulations. World Scientific Hackensack NJ.","DOI":"10.1142\/8685"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/235815.235821"},{"key":"e_1_2_2_5_1","volume-title":"Proceedings of the 32nd International Conference on Neural Information Processing Systems (NIPS\u201918)","author":"Belkin M.","unstructured":"M. Belkin , D. Hsu , and P. P. Mitra . 2018. Overfitting or perfect fitting? Risk bounds for classification and regression rules that interpolate . In Proceedings of the 32nd International Conference on Neural Information Processing Systems (NIPS\u201918) . Curran Associates, Montr\u00e9al, Canada, 2306--2317. M. Belkin, D. Hsu, and P. P. Mitra. 2018. Overfitting or perfect fitting? Risk bounds for classification and regression rules that interpolate. In Proceedings of the 32nd International Conference on Neural Information Processing Systems (NIPS\u201918). Curran Associates, Montr\u00e9al, Canada, 2306--2317."},{"key":"e_1_2_2_6_1","volume-title":"Proceedings of the 25th Annual Symposium on Computational Geometry. ACM","author":"Boissonnat J.-D.","unstructured":"J.-D. Boissonnat , O. Devillers , and S. Hornus . 2009. Incremental construction of the Delaunay triangulation and the Delaunay graph in medium dimension . In Proceedings of the 25th Annual Symposium on Computational Geometry. ACM , Aarhus, Denmark, 208--216. J.-D. Boissonnat, O. Devillers, and S. Hornus. 2009. Incremental construction of the Delaunay triangulation and the Delaunay graph in medium dimension. In Proceedings of the 25th Annual Symposium on Computational Geometry. ACM, Aarhus, Denmark, 208--216."},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/24.2.162"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2019.2892129"},{"key":"e_1_2_2_9_1","volume-title":"Proceedings of the Spring Simulation Conference and the 26th High Performance Computing Symp.osium. Society for Modeling and Simulation","author":"Chang T. H.","unstructured":"T. H. Chang , L. T. Watson , T. C. H. Lux , J. Bernard , B. Li , L. Xu , G. Back , A. R. Butt , K. W. Cameron , and Y. Hong . 2018a. Predicting system performance by interpolation using a high-dimensional Delaunay triangulation . In Proceedings of the Spring Simulation Conference and the 26th High Performance Computing Symp.osium. Society for Modeling and Simulation , Baltimore, MD, Article No. 2. T. H. Chang, L. T. Watson, T. C. H. Lux, J. Bernard, B. Li, L. Xu, G. Back, A. R. Butt, K. W. Cameron, and Y. Hong. 2018a. Predicting system performance by interpolation using a high-dimensional Delaunay triangulation. In Proceedings of the Spring Simulation Conference and the 26th High Performance Computing Symp.osium. Society for Modeling and Simulation, Baltimore, MD, Article No. 2."},{"key":"e_1_2_2_10_1","volume-title":"Proceedings of the ACM Southeast Conference (ACMSE\u201918)","author":"Chang T. H.","unstructured":"T. H. Chang , L. T. Watson , T. C. H. Lux , B. Li , L. Xu , A. R. Butt , K. W. Cameron , and Y. Hong . 2018b. A polynomial time algorithm for multivariate interpolation in arbitrary dimension via the Delaunay triangulation . In Proceedings of the ACM Southeast Conference (ACMSE\u201918) . ACM, Richmond, KY, Article No. 12. T. H. Chang, L. T. Watson, T. C. H. Lux, B. Li, L. Xu, A. R. Butt, K. W. Cameron, and Y. Hong. 2018b. A polynomial time algorithm for multivariate interpolation in arbitrary dimension via the Delaunay triangulation. In Proceedings of the ACM Southeast Conference (ACMSE\u201918). ACM, Richmond, KY, Article No. 12."},{"key":"e_1_2_2_11_1","doi-asserted-by":"crossref","unstructured":"E. W. Cheney and W. A. Light. 2009. A Course in Approximation Theory. American Mathematical Society Providence RI.  E. W. Cheney and W. A. Light. 2009. A Course in Approximation Theory. American Mathematical Society Providence RI.","DOI":"10.1090\/gsm\/101"},{"key":"e_1_2_2_12_1","unstructured":"S. W. Cheng T. K. Dey and J. Shewchuk. 2012. Delaunay Mesh Generation. Computer and Information Science Series CRC Press Boca Raton FL.  S. W. Cheng T. K. Dey and J. Shewchuk. 2012. Delaunay Mesh Generation. Computer and Information Science Series CRC Press Boca Raton FL."},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0010-4485(97)00082-1"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/1370949"},{"key":"e_1_2_2_15_1","volume-title":"Proceedings of the 17th Annual Symposium on Computational Geometry. ACM","author":"Devillers O.","unstructured":"O. Devillers , S. Pion , and M. Teillaud . 2001. Walking in a triangulation . In Proceedings of the 17th Annual Symposium on Computational Geometry. ACM , Medford, MA, 106--114. O. Devillers, S. Pion, and M. Teillaud. 2001. Walking in a triangulation. In Proceedings of the 17th Annual Symposium on Computational Geometry. ACM, Medford, MA, 106--114."},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/73833.73850"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/356004.356010"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01224932"},{"key":"e_1_2_2_19_1","volume-title":"Proceedings of the IEEE International Conference on Big Knowledge. IEEE","author":"Liu Y.","unstructured":"Y. Liu and G. Yin . 2019. Nonparametric functional approximation with Delaunay triangulation learner . In Proceedings of the IEEE International Conference on Big Knowledge. IEEE , Beijing, China, 167--174. Y. Liu and G. Yin. 2019. Nonparametric functional approximation with Delaunay triangulation learner. In Proceedings of the IEEE International Conference on Big Knowledge. IEEE, Beijing, China, 167--174."},{"key":"e_1_2_2_20_1","volume-title":"Proceedings of the Spring Simulation Conference and the 26th High Performance Computing Symposium, Society for Modeling and Simulation","author":"Lux T. C. H.","unstructured":"T. C. H. Lux , L. T. Watson , T. H. Chang , J. Bernard , B. Li , L. Xu , G. Back , A. R. Butt , K. W. Cameron , and Y. Hong . 2018. Predictive modeling of I\/O characteristics in high performance computing systems . In Proceedings of the Spring Simulation Conference and the 26th High Performance Computing Symposium, Society for Modeling and Simulation , Baltimore, MD, Article No. 8. T. C. H. Lux, L. T. Watson, T. H. Chang, J. Bernard, B. Li, L. Xu, G. Back, A. R. Butt, K. W. Cameron, and Y. Hong. 2018. Predictive modeling of I\/O characteristics in high performance computing systems. In Proceedings of the Spring Simulation Conference and the 26th High Performance Computing Symposium, Society for Modeling and Simulation, Baltimore, MD, Article No. 8."},{"key":"e_1_2_2_21_1","volume-title":"Virginia Polytechnic Institute and State University","author":"Lux T. C. H.","unstructured":"T. C. H. Lux . 2020. Interpolants, Error Bounds , and Mathematical Software for Modeling and Predicting Variability in Computer Systems . Ph.D. Dissertation . Virginia Polytechnic Institute and State University , Blacksburg, VA . T. C. H. Lux. 2020. Interpolants, Error Bounds, and Mathematical Software for Modeling and Predicting Variability in Computer Systems. Ph.D. Dissertation. Virginia Polytechnic Institute and State University, Blacksburg, VA."},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(98)00035-2"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.3.1.63"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-2789(90)90085-4"},{"key":"e_1_2_2_25_1","volume-title":"Accessed in March","author":"Architecture Review MP","year":"2015","unstructured":"Open MP Architecture Review Board (ARB). 2015 . OpenMP Application Programming Interface, version 4.5 . Accessed in March , 2019. OpenMP Architecture Review Board (ARB). 2015. OpenMP Application Programming Interface, version 4.5. Accessed in March, 2019."},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574375"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11590-014-0815-x"},{"key":"e_1_2_2_28_1","volume-title":"Proceedings of the 20th Canadian Conference on Computational Geometry. Montr\u00e9al, Qu\u00e9bec, 175--178","author":"Miller G.","unstructured":"G. Miller , T. Phillips , and D. Sheehy . 2008. Linear-size meshes . In Proceedings of the 20th Canadian Conference on Computational Geometry. Montr\u00e9al, Qu\u00e9bec, 175--178 . G. Miller, T. Phillips, and D. Sheehy. 2008. Linear-size meshes. In Proceedings of the 20th Canadian Conference on Computational Geometry. Montr\u00e9al, Qu\u00e9bec, 175--178."},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/0613077"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(96)00025-9"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/24.2.167"}],"container-title":["ACM Transactions on Mathematical Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3422818","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3422818","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3422818","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:24:56Z","timestamp":1750195496000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3422818"}},"subtitle":["DELAUNAYSPARSE: Interpolation via a Sparse Subset of the Delaunay Triangulation in Medium to High Dimensions"],"short-title":[],"issued":{"date-parts":[[2020,11,7]]},"references-count":31,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,12,31]]}},"alternative-id":["10.1145\/3422818"],"URL":"https:\/\/doi.org\/10.1145\/3422818","relation":{},"ISSN":["0098-3500","1557-7295"],"issn-type":[{"value":"0098-3500","type":"print"},{"value":"1557-7295","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,11,7]]},"assertion":[{"value":"2019-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-11-07","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}