{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,21]],"date-time":"2026-02-21T05:35:26Z","timestamp":1771652126601,"version":"3.50.1"},"reference-count":74,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2018,4,30]],"date-time":"2018-04-30T00:00:00Z","timestamp":1525046400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"LLC., a wholly owned subsidiary of Honeywell International, Inc., for the U.S. Department of Energy\u2019s National Nuclear Security Administration","award":["DE-NA0003525"],"award-info":[{"award-number":["DE-NA0003525"]}]},{"DOI":"10.13039\/100000015","name":"U.S. Department of Energy","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Applied Mathematics Program. Sandia National Laboratories is a multi-mission laboratory managed and operated by National Technology and Engineering Solutions of Sandia"},{"DOI":"10.13039\/100006132","name":"Office of Science","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100006132","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Office of Advanced Scientific Computing Research"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2018,4,30]]},"abstract":"<jats:p>Blue noise sampling has proved useful for many graphics applications, but remains underexplored in high-dimensional spaces due to the difficulty of generating distributions and proving properties about them. We present a blue noise sampling method with good quality and performance across different dimensions. The method, spoke-dart sampling, shoots rays from prior samples and selects samples from these rays. It combines the advantages of two major high-dimensional sampling methods: the locality of advancing front with the dimensionality-reduction of hyperplanes, specifically line sampling. We prove that the output sampling is saturated with high probability, with bounds on distances between pairs of samples and between any domain point and its nearest sample. We demonstrate spoke-dart applications for approximate Delaunay graph construction, global optimization, and robotic motion planning. Both the blue-noise quality of the output distribution and the adaptability of the intermediate processes of our method are useful in these applications.<\/jats:p>","DOI":"10.1145\/3194657","type":"journal-article","created":{"date-parts":[[2018,5,14]],"date-time":"2018-05-14T12:29:08Z","timestamp":1526300948000},"page":"1-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":20,"title":["Spoke-Darts for High-Dimensional Blue-Noise Sampling"],"prefix":"10.1145","volume":"37","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3710-4500","authenticated-orcid":false,"given":"Scott A.","family":"Mitchell","sequence":"first","affiliation":[{"name":"Sandia National Laboratories, Albuquerque, NM"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mohamed S.","family":"Ebeida","sequence":"additional","affiliation":[{"name":"Sandia National Laboratories, Albuquerque, NM"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Muhammad A.","family":"Awad","sequence":"additional","affiliation":[{"name":"University of California at Davis"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chonhyon","family":"Park","sequence":"additional","affiliation":[{"name":"UNC Chapel Hill"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anjul","family":"Patney","sequence":"additional","affiliation":[{"name":"NVIDIA Research"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ahmad A.","family":"Rushdi","sequence":"additional","affiliation":[{"name":"University of California at Davis and Sandia National Laboratories"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Laura P.","family":"Swiler","sequence":"additional","affiliation":[{"name":"Sandia National Laboratories, Albuquerque, NM"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dinesh","family":"Manocha","sequence":"additional","affiliation":[{"name":"UNC Chapel Hill"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1076-6339","authenticated-orcid":false,"given":"Li-Yi","family":"Wei","sequence":"additional","affiliation":[{"name":"University of Hong Kong and Adobe Research"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,5,12]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3072959.3073588"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2980179.2980218"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/882262.882296"},{"key":"e_1_2_2_4_1","volume-title":"Swiler","author":"Awad Muhammad A.","year":"2016","unstructured":"Muhammad A. Awad , Mohamed S. Ebeida , Scott A. Mitchell , Anjul Patney , Ahmad A. Rushdi , and Laura P . Swiler . 2016 . SpokeDartsPublic Open-source Software . v. 1.0, https:\/\/github.com\/samitch\/SpokeDartsPublic. (2016). Muhammad A. Awad, Mohamed S. Ebeida, Scott A. Mitchell, Anjul Patney, Ahmad A. Rushdi, and Laura P. Swiler. 2016. SpokeDartsPublic Open-source Software. v. 1.0, https:\/\/github.com\/samitch\/SpokeDartsPublic. (2016)."},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1531326.1531392"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/235815.235821"},{"key":"e_1_2_2_7_1","volume-title":"smoof: Single- and multi-objective optimization test functions. The R Journal","author":"Bossek Jakob","year":"2017","unstructured":"Jakob Bossek . 2017. smoof: Single- and multi-objective optimization test functions. The R Journal ( 2017 ). https:\/\/journal.r-project.org\/archive\/2017\/RJ-2017-004\/index.html. Jakob Bossek. 2017. smoof: Single- and multi-objective optimization test functions. The R Journal (2017). https:\/\/journal.r-project.org\/archive\/2017\/RJ-2017-004\/index.html."},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1278780.1278807"},{"key":"e_1_2_2_9_1","volume-title":"TEST OPT: Optimization of a scalar function test problems.","author":"Burkardt John","year":"2011","unstructured":"John Burkardt . 2011 . TEST OPT: Optimization of a scalar function test problems. (2011). http:\/\/people.sc.fsu.edu\/ jburkardt\/m_src\/test_opt\/test_opt.html. John Burkardt. 2011. TEST OPT: Optimization of a scalar function test problems. (2011). http:\/\/people.sc.fsu.edu\/ jburkardt\/m_src\/test_opt\/test_opt.html."},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2508363.2508375"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2009.01499.x"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/7529.8927"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/MRA.2012.2205651"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2366145.2366190"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/325165.325182"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1141911.1141915"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/73833.73869"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2013.08.015"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2010324.1964944"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2012.03059.x"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2522528"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2010324.1964943"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1640443.1640451"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2010.213"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487228.2487233"},{"key":"e_1_2_2_26_1","volume-title":"Handbook of Global Optimization","author":"Horst Reiner","unstructured":"Reiner Horst , Panos M. Pardalos , and H. Edwin Romeijn . 2002. Handbook of Global Optimization . Vol. 2 . Springer . Reiner Horst, Panos M. Pardalos, and H. Edwin Romeijn. 2002. Handbook of Global Optimization. Vol. 2. Springer."},{"key":"e_1_2_2_27_1","unstructured":"Wenzel Jakob. 2010. Mitsuba Renderer. Retrieved from http:\/\/www.mitsuba-renderer.org.  Wenzel Jakob. 2010. Mitsuba Renderer. Retrieved from http:\/\/www.mitsuba-renderer.org."},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1504\/IJMMNO.2013.055204"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2816795.2818102"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/3182688.3183134"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1080\/2151237X.2006.10129217"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2980179.2982435"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2343483.2343502"},{"key":"e_1_2_2_34_1","unstructured":"Thomas Kollig and Alexander Keller. 2003. Efficient illumination by high dynamic range images. In EGRW\u201903. 45--50. http:\/\/dl.acm.org\/citation.cfm?id&equals;882404.882411   Thomas Kollig and Alexander Keller. 2003. Efficient illumination by high dynamic range images. In EGRW\u201903. 45--50. http:\/\/dl.acm.org\/citation.cfm?id&equals;882404.882411"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1141911.1141916"},{"key":"e_1_2_2_36_1","volume-title":"Proceedings of the IEEE Conference on Robotics and Automation. 995--1001","author":"James","unstructured":"James J. Kuffner and Steven M. Lavalle. 2000. RRT-connect: An efficient approach to single-query path planning . In Proceedings of the IEEE Conference on Robotics and Automation. 995--1001 . James J. Kuffner and Steven M. Lavalle. 2000. RRT-connect: An efficient approach to single-query path planning. In Proceedings of the IEEE Conference on Robotics and Automation. 995--1001."},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1095878.1095888"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2007.01100.x"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1177\/02783640122067453"},{"key":"e_1_2_2_40_1","unstructured":"Kuan Yew Leong. 2016. Test functions for optimization. Retrieved from http:\/\/mathworks.com\/matlabcentral\/fileexchange\/59737-test-functions.  Kuan Yew Leong. 2016. Test functions for optimization. Retrieved from http:\/\/mathworks.com\/matlabcentral\/fileexchange\/59737-test-functions."},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1882261.1866189"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1002\/1097-0207(20000910\/20)49:1\/2<61::AID-NME923>3.0.CO;2-Y"},{"key":"e_1_2_2_43_1","volume-title":"Proceedings of CAD\/Graphics\u201991","author":"Liu Jianfei","year":"1991","unstructured":"Jianfei Liu . 1991 . Automatic triangulation of N-dimensional euclidean domains . In Proceedings of CAD\/Graphics\u201991 . 238--241. Jianfei Liu. 1991. Automatic triangulation of N-dimensional euclidean domains. In Proceedings of CAD\/Graphics\u201991. 238--241."},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10409-008-0165-y"},{"key":"e_1_2_2_45_1","volume-title":"An optimization approach to relaxation labeling algorithms. Image and Vision Computing 1, 2","author":"Lloyd S.","year":"1983","unstructured":"S. Lloyd . 1983. An optimization approach to relaxation labeling algorithms. Image and Vision Computing 1, 2 ( 1983 ). S. Lloyd. 1983. An optimization approach to relaxation labeling algorithms. Image and Vision Computing 1, 2 (1983)."},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/PROC.1974.9625"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2462356.2462372"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2462356.2462404"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/37402.37410"},{"key":"e_1_2_2_50_1","volume-title":"Proceedings of the 24th Canadian Conference on Computational Geometry. 1--9. http:\/\/2012","author":"Mitchell Scott A.","year":"2012","unstructured":"Scott A. Mitchell , Alexander Rand , Mohamed S. Ebeida , and Chadrajit Bajaj . 2012 . Variable radii poisson-disk sampling, extended version . In Proceedings of the 24th Canadian Conference on Computational Geometry. 1--9. http:\/\/2012 .cccg.ca\/papers\/paper15-extended.pdf. Scott A. Mitchell, Alexander Rand, Mohamed S. Ebeida, and Chadrajit Bajaj. 2012. Variable radii poisson-disk sampling, extended version. In Proceedings of the 24th Canadian Conference on Computational Geometry. 1--9. http:\/\/2012.cccg.ca\/papers\/paper15-extended.pdf."},{"key":"e_1_2_2_51_1","volume-title":"Lowe","author":"Muja Marius","year":"2009","unstructured":"Marius Muja and David G . Lowe . 2009 . Fast approximate nearest neighbors with automatic algorithm configuration. In VISAPP ( 1). 331--340. Marius Muja and David G. Lowe. 2009. Fast approximate nearest neighbors with automatic algorithm configuration. In VISAPP (1). 331--340."},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/377939.377946"},{"key":"e_1_2_2_53_1","doi-asserted-by":"crossref","unstructured":"Harald Niederreiter. 1992. Random Number Generation and Quasi-Monte Carlo Methods. SIAM.   Harald Niederreiter. 1992. Random Number Generation and Quasi-Monte Carlo Methods. SIAM.","DOI":"10.1137\/1.9781611970081"},{"key":"e_1_2_2_54_1","volume-title":"Proceedings of the 3rd International Game Design and Technology Workshop. 29--33","author":"Overmars Mark H.","year":"2005","unstructured":"Mark H. Overmars . 2005 . Path planning for games . In Proceedings of the 3rd International Game Design and Technology Workshop. 29--33 . Mark H. Overmars. 2005. Path planning for games. In Proceedings of the 3rd International Game Design and Technology Workshop. 29--33."},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/1882261.1866190"},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/2366145.2366189"},{"key":"e_1_2_2_57_1","first-page":"3","article-title":"A hybrid approach for simulating human motion in constrained environments","volume":"21","author":"Pan Jia","year":"2010","unstructured":"Jia Pan , Liangjun Zhang , Ming C. Lin , and Dinesh Manocha . 2010 . A hybrid approach for simulating human motion in constrained environments . Computer Animation and Virtual Worlds 21 , 3 -- 4 (2010), 137--149. Jia Pan, Liangjun Zhang, Ming C. Lin, and Dinesh Manocha. 2010. A hybrid approach for simulating human motion in constrained environments. Computer Animation and Virtual Worlds 21, 3--4 (2010), 137--149.","journal-title":"Computer Animation and Virtual Worlds"},{"key":"e_1_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2016.2632160"},{"key":"e_1_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/2766930"},{"key":"e_1_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.12725"},{"key":"e_1_2_2_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/2185520.2185557"},{"key":"e_1_2_2_62_1","doi-asserted-by":"publisher","DOI":"10.1080\/2151237X.2011.609773"},{"key":"e_1_2_2_63_1","unstructured":"Peter Shirley. 1991. Discrepancy as a quality measure for sample distributions. In Eurographics\u201991. 183--194.  Peter Shirley. 1991. Discrepancy as a quality measure for sample distributions. In Eurographics\u201991. 183--194."},{"key":"e_1_2_2_64_1","doi-asserted-by":"publisher","DOI":"10.1137\/0709036"},{"key":"e_1_2_2_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/2461912.2462013"},{"key":"e_1_2_2_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/2461912.2462023"},{"key":"e_1_2_2_67_1","doi-asserted-by":"publisher","DOI":"10.1109\/5.3288"},{"key":"e_1_2_2_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/3105762.3105778"},{"key":"e_1_2_2_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/2010324.1964945"},{"key":"e_1_2_2_70_1","unstructured":"Eric W. Weisstein. 1999. Hypersphere Packing. Retrieved from http:\/\/mathworld.wolfram.com\/HyperspherePacking.html.  Eric W. Weisstein. 1999. Hypersphere Packing. Retrieved from http:\/\/mathworld.wolfram.com\/HyperspherePacking.html."},{"key":"e_1_2_2_71_1","doi-asserted-by":"publisher","DOI":"10.1137\/100817504"},{"key":"e_1_2_2_72_1","doi-asserted-by":"publisher","DOI":"10.1145\/1015706.1015756"},{"key":"e_1_2_2_73_1","doi-asserted-by":"publisher","DOI":"10.1145\/2516971.2516973"},{"key":"e_1_2_2_74_1","volume-title":"Appendix A: Test Problems in Optimization","author":"Yang Xin-She","unstructured":"Xin-She Yang . 2010. Appendix A: Test Problems in Optimization . John Wiley and Sons, Inc. , 261--266. Xin-She Yang. 2010. Appendix A: Test Problems in Optimization. John Wiley and Sons, Inc., 261--266."}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3194657","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3194657","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3194657","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:08:27Z","timestamp":1750208907000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3194657"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,4,30]]},"references-count":74,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,4,30]]}},"alternative-id":["10.1145\/3194657"],"URL":"https:\/\/doi.org\/10.1145\/3194657","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,4,30]]},"assertion":[{"value":"2016-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-05-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}