{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:04:01Z","timestamp":1750309441631,"version":"3.41.0"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2024,12,12]],"date-time":"2024-12-12T00:00:00Z","timestamp":1733961600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100006227","name":"Lawrence Livermore National Laboratory","doi-asserted-by":"crossref","award":["LDRD 21\u2013ERD\u2013028"],"award-info":[{"award-number":["LDRD 21\u2013ERD\u2013028"]}],"id":[{"id":"10.13039\/100006227","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Math. Softw."],"published-print":{"date-parts":[[2024,12,31]]},"abstract":"<jats:p>\n            Accurate approximation of a real-valued function depends on two aspects of the available data: the density of inputs within the domain of interest and the variation of the outputs over that domain. There are few methods for assessing whether the density of inputs is\n            <jats:italic>sufficient<\/jats:italic>\n            to identify the relevant variations in outputs\u2014i.e., the \u201cgeometric scale\u201d of the function\u2014despite the fact that sampling density is closely tied to the success or failure of an approximation method. In this article, we introduce a general purpose, computational approach to detecting the geometric scale of real-valued functions over a fixed domain using a deterministic interpolation technique from computational geometry. The algorithm is intended to work on scalar data in moderate dimensions (2\u201310). Our algorithm is based on the observation that a sequence of piecewise linear interpolants will converge to a continuous function at a quadratic rate (in\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(L^{2}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            norm) if and only if the data are sampled densely enough to distinguish the feature from noise (assuming sufficiently regular sampling). We present numerical experiments demonstrating how our method can identify feature scale, estimate uncertainty in feature scale, and assess the sampling density for fixed (i.e., static) datasets of input\u2013output pairs. We include analytical results in support of our numerical findings and have released lightweight code that can be adapted for use in a variety of data science settings.\n          <\/jats:p>","DOI":"10.1145\/3700134","type":"journal-article","created":{"date-parts":[[2024,10,14]],"date-time":"2024-10-14T14:46:52Z","timestamp":1728917212000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Algorithm 1049: The Delaunay Density Diagnostic"],"prefix":"10.1145","volume":"50","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1195-5924","authenticated-orcid":false,"given":"Andrew","family":"Gillette","sequence":"first","affiliation":[{"name":"Center for Applied Scientific Computing, Lawrence Livermore National Laboratory, Livermore, CA, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1831-3887","authenticated-orcid":false,"given":"Eugene","family":"Kur","sequence":"additional","affiliation":[{"name":"Strategic Deterrence, Lawrence Livermore National Laboratory, Livermore, CA, USA"}]}],"member":"320","published-online":{"date-parts":[[2024,12,12]]},"reference":[{"key":"e_1_3_1_2_2","doi-asserted-by":"publisher","DOI":"10.5555\/40713"},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/336154.336207"},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.2023.2197686"},{"key":"e_1_3_1_5_2","first-page":"2300","volume-title":"Proceedings of the Advances in Neural Information Processing Systems","author":"Belkin Mikhail","year":"2018","unstructured":"Mikhail Belkin, Daniel J. Hsu, and Partha Mitra. 2018. Overfitting or perfect fitting? Risk bounds for classification and regression rules that interpolate. In Proceedings of the Advances in Neural Information Processing Systems, Vol. 31. Curran Associates, Inc., 2300\u20132311."},{"key":"e_1_3_1_6_2","volume-title":"Proceedings of the Advances in Neural Information Processing Systems","volume":"16","author":"Bengio Yoshua","year":"2003","unstructured":"Yoshua Bengio and Yves Grandvalet. 2003. No unbiased estimator of the variance of k-fold cross-validation. In Proceedings of the Advances in Neural Information Processing Systems, Vol. 16."},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/307400.307439"},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-4338-8_5"},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0962492900000015"},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511543241"},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.1115\/1.2819284"},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1115\/1.1990201"},{"key":"e_1_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/3422818"},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/3190645.3190680"},{"issue":"2","key":"e_1_3_1_15_2","first-page":"299","article-title":"Optimal Delaunay triangulations","volume":"18","author":"Chen Long","year":"2004","unstructured":"Long Chen and Jinchao Xu. 2004. Optimal Delaunay triangulations. Journal of Computational Mathematics 18, 2 (2004), 299\u2013308.","journal-title":"Journal of Computational Mathematics"},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.99.021201"},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","unstructured":"W. Cochran. 2023. San Bernardino Mountains CA 2016 airborne lidar survey. National Center for Airborne Laser Mapping (NCALM). Distributed by OpenTopography. DOI: 10.5069\/G9SX6B51","DOI":"10.5069\/G9SX6B51"},{"key":"e_1_3_1_18_2","unstructured":"Andrew Gillette and Eugene Kur. 2022. Delaunay Density Diagnostic [Github repository]. Retrieved from https:\/\/github.com\/LLNL\/ddd"},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00933356"},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.14358\/PERS.76.6.701"},{"key":"e_1_3_1_21_2","unstructured":"Markelle Kelly Rachel Longjohn and Kolby Nottingham. 2023. The UCI Machine Learning Repository. Retrieved from https:\/\/archive.ics.uci.edu\/"},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1002\/wics.73"},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.1063\/1.5049595"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICBK.2019.00030"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11075-020-01040-2"},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.1063\/1.1356740"},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.1201\/9780203753736"},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0036142999360044"},{"key":"e_1_3_1_29_2","doi-asserted-by":"publisher","DOI":"10.2307\/2344614"},{"key":"e_1_3_1_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574375"},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.1098\/rsta.1911.0009"},{"issue":"636","key":"e_1_3_1_32_2","first-page":"299","article-title":"The deferred approach to the limit","volume":"226","author":"Richardson Lewis Fry","year":"1927","unstructured":"Lewis Fry Richardson and J. Arthur Gaunt. 1927. The deferred approach to the limit. Philosophical Transactions of the Royal Society of London. Series A, Containing Papers of a Mathematical or Physical Character 226, 636\u2013646 (1927), 299\u2013361.","journal-title":"Philosophical Transactions of the Royal Society of London. Series A, Containing Papers of a Mathematical or Physical Character"},{"key":"e_1_3_1_33_2","doi-asserted-by":"publisher","DOI":"10.1214\/ss\/1177012413"},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.2514\/2.1234"},{"key":"e_1_3_1_35_2","volume-title":"Proceedings of the 2004 Winter Simulation Conference","volume":"1","author":"Beers Wim C. M. Van","year":"2004","unstructured":"Wim C. M. Van Beers and Jack P. C. Kleijnen. 2004. Kriging interpolation in simulation: A survey. In Proceedings of the 2004 Winter Simulation Conference, Vol. 1. IEEE."}],"container-title":["ACM Transactions on Mathematical Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3700134","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3700134","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3700134","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:09:49Z","timestamp":1750295389000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3700134"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,12]]},"references-count":34,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,12,31]]}},"alternative-id":["10.1145\/3700134"],"URL":"https:\/\/doi.org\/10.1145\/3700134","relation":{},"ISSN":["0098-3500","1557-7295"],"issn-type":[{"type":"print","value":"0098-3500"},{"type":"electronic","value":"1557-7295"}],"subject":[],"published":{"date-parts":[[2024,12,12]]},"assertion":[{"value":"2023-04-17","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-10-03","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-12-12","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}