{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,13]],"date-time":"2026-05-13T03:03:03Z","timestamp":1778641383281,"version":"3.51.4"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Computer Science Research Institute"},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-1017399"],"award-info":[{"award-number":["CCF-1017399"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100005595","name":"University of California","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100005595","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100007065","name":"Nvidia","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100007065","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006168","name":"National Nuclear Security Administration","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006168","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100007000","name":"Laboratory Directed Research and Development","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100007000","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100002418","name":"Intel Corporation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100002418","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2014,1]]},"abstract":"<jats:p>\n            We formalize sampling a function using\n            <jats:italic>k<\/jats:italic>\n            -d darts. A\n            <jats:italic>k<\/jats:italic>\n            -d Dart is a set of independent, mutually orthogonal,\n            <jats:italic>k<\/jats:italic>\n            -dimensional hyperplanes called\n            <jats:italic>k<\/jats:italic>\n            -d flats. A dart has\n            <jats:italic>d<\/jats:italic>\n            choose\n            <jats:italic>k<\/jats:italic>\n            flats, aligned with the coordinate axes for efficiency. We show\n            <jats:italic>k<\/jats:italic>\n            -d darts are useful for exploring a function's properties, such as estimating its integral, or finding an exemplar above a threshold. We describe a recipe for converting some algorithms from point sampling to\n            <jats:italic>k<\/jats:italic>\n            -d dart sampling, if the function can be evaluated along a\n            <jats:italic>k<\/jats:italic>\n            -d flat.\n          <\/jats:p>\n          <jats:p>\n            We demonstrate that\n            <jats:italic>k<\/jats:italic>\n            -d darts are more efficient than point-wise samples in high dimensions, depending on the characteristics of the domain: for example, the subregion of interest has small volume and evaluating the function along a flat is not too expensive. We present three concrete applications using line darts (1-d darts): relaxed maximal Poisson-disk sampling, high-quality rasterization of depth-of-field blur, and estimation of the probability of failure from a response surface for uncertainty quantification. Line darts achieve the same output fidelity as point sampling in less time. For Poisson-disk sampling, we use less memory, enabling the generation of larger point distributions in higher dimensions. Higher-dimensional darts provide greater accuracy for a particular volume estimation problem.\n          <\/jats:p>","DOI":"10.1145\/2522528","type":"journal-article","created":{"date-parts":[[2014,2,4]],"date-time":"2014-02-04T14:16:21Z","timestamp":1391523381000},"page":"1-16","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["<i>k<\/i>\n            -d Darts"],"prefix":"10.1145","volume":"33","author":[{"given":"Mohamed S.","family":"Ebeida","sequence":"first","affiliation":[{"name":"Sandia National Laboratories, Albuquerque, NM"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anjul","family":"Patney","sequence":"additional","affiliation":[{"name":"University of California, Davis, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Scott A.","family":"Mitchell","sequence":"additional","affiliation":[{"name":"Sandia National Laboratories, Albuquerque, NM"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Keith R.","family":"Dalbey","sequence":"additional","affiliation":[{"name":"Sandia National Laboratories, Albuquerque, NM"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrew A.","family":"Davidson","sequence":"additional","affiliation":[{"name":"University of California, Davis, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"John D.","family":"Owens","sequence":"additional","affiliation":[{"name":"University of California, Davis, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,2,7]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/235815.235821"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/7529.8927"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/325334.325182"},{"key":"e_1_2_2_4_1","volume-title":"Proceedings of the 20th International Meshing Roundtable. 258--275","author":"Ebeida M. S.","unstructured":"M. S. Ebeida and S. A. Mitchell . 2011. Uniform random voronoi meshes . In Proceedings of the 20th International Meshing Roundtable. 258--275 . M. S. Ebeida and S. A. Mitchell. 2011. Uniform random voronoi meshes. In Proceedings of the 20th International Meshing Roundtable. 258--275."},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2012.03059.x"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2010324.1964944"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1640443.1640451"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.35.11.1367"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2010324.1964949"},{"key":"e_1_2_2_10_1","volume-title":"Proceedings of Conference on High Performance Graphics (HPG'10)","author":"Gribel C. J.","unstructured":"C. J. Gribel , M. Doggett , and T. Akenine-M\u00f6ller . 2010. Analytical motion blur rasterization with compression . In Proceedings of Conference on High Performance Graphics (HPG'10) . 163--172. C. J. Gribel, M. Doggett, and T. Akenine-M\u00f6ller. 2010. Analytical motion blur rasterization with compression. In Proceedings of Conference on High Performance Graphics (HPG'10). 163--172."},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/97879.97913"},{"key":"e_1_2_2_12_1","first-page":"113","article-title":"On an experimental determination of &pi;","volume":"2","author":"Hall A.","year":"1873","unstructured":"A. Hall . 1873 . On an experimental determination of &pi; . Messenger Math. 2 , 113 -- 114 . A. Hall. 1873. On an experimental determination of &pi;. Messenger Math. 2, 113--114.","journal-title":"Messenger Math."},{"key":"e_1_2_2_13_1","volume-title":"GPU Gems 3","author":"Hammon E.","unstructured":"E. Hammon Jr . 2008. Practical post-process depth of field . In GPU Gems 3 , H. Nguyen, Ed., Addison-Wesley , 583--605. E. Hammon Jr. 2008. Practical post-process depth of field. In GPU Gems 3, H. Nguyen, Ed., Addison-Wesley, 583--605."},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1899404.1899409"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/280814.280925"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1080\/2151237X.2011.617173"},{"key":"e_1_2_2_17_1","volume-title":"Proceedings of the Eurographics Workshop on Rendering Techniques. Springer, 197--206","author":"Jones T. R.","unstructured":"T. R. Jones and R. N. Perry . 2000. Antialiasing with line samples . In Proceedings of the Eurographics Workshop on Rendering Techniques. Springer, 197--206 . T. R. Jones and R. N. Perry. 2000. Antialiasing with line samples. In Proceedings of the Eurographics Workshop on Rendering Techniques. Springer, 197--206."},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2007.01100.x"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2010324.1964950"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2005.07.002"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/38.45807"},{"key":"e_1_2_2_22_1","first-page":"239","article-title":"A comparison of three methods for selecting values of input variables in the analysis of output from a computer code","volume":"21","author":"McKay M. D.","year":"1979","unstructured":"M. D. McKay , R. J. Beckman , and W. J. Conover . 1979 . A comparison of three methods for selecting values of input variables in the analysis of output from a computer code . Technometrics 21 , 2, 239 -- 245 . M. D. McKay, R. J. Beckman, and W. J. Conover. 1979. A comparison of three methods for selecting values of input variables in the analysis of output from a computer code. Technometrics 21, 2, 239--245.","journal-title":"Technometrics"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/37401.37410"},{"key":"e_1_2_2_24_1","doi-asserted-by":"crossref","unstructured":"G. Nebe and N. Sloane. 2012. A catalogue of lattices. http:\/\/www.math.rwth-achen.de\/&sim;Gabriele.Nebe\/LATTICES\/index.html.  G. Nebe and N. Sloane. 2012. A catalogue of lattices. http:\/\/www.math.rwth-achen.de\/&sim;Gabriele.Nebe\/LATTICES\/index.html.","DOI":"10.1090\/conm\/587\/11676"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.2517-6161.1992.tb01895.x"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1969.12000364"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/2386366.2386385"},{"key":"e_1_2_2_28_1","unstructured":"T. Schl\u00f6mer. 2011. PSA point set analysis. http:\/\/code.google.com\/p\/psa\/.  T. Schl\u00f6mer. 2011. PSA point set analysis. http:\/\/code.google.com\/p\/psa\/."},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/0114059"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1778765.1778791"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/2383795.2383799"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/258734.258775"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1360612.1360619"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/RT.2007.4342600"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2522528","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2522528","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:10:00Z","timestamp":1750234200000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2522528"}},"subtitle":["Sampling by\n            <i>k<\/i>\n            -dimensional flat searches"],"short-title":[],"issued":{"date-parts":[[2014,1]]},"references-count":34,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,1]]}},"alternative-id":["10.1145\/2522528"],"URL":"https:\/\/doi.org\/10.1145\/2522528","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,1]]},"assertion":[{"value":"2013-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-02-07","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}