{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,3]],"date-time":"2026-07-03T19:01:03Z","timestamp":1783105263987,"version":"3.54.6"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2009,7,27]],"date-time":"2009-07-27T00:00:00Z","timestamp":1248652800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2009,7,27]]},"abstract":"<jats:p>We present a new general-purpose method for optimizing existing point sets. The resulting distributions possess high-quality blue noise characteristics and adapt precisely to given density functions. Our method is similar to the commonly used Lloyd's method while avoiding its drawbacks. We achieve our results by utilizing the concept of capacity, which for each point is determined by the area of its Voronoi region weighted with an underlying density function. We demand that each point has the same capacity. In combination with a dedicated optimization algorithm, this capacity constraint enforces that each point obtains equal importance in the distribution. Our method can be used as a drop-in replacement for Lloyd's method, and combines enhancement of blue noise characteristics and density function adaptation in one operation.<\/jats:p>","DOI":"10.1145\/1531326.1531392","type":"journal-article","created":{"date-parts":[[2009,7,28]],"date-time":"2009-07-28T12:43:55Z","timestamp":1248785035000},"page":"1-8","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":136,"title":["Capacity-constrained point distributions"],"prefix":"10.1145","volume":"28","author":[{"given":"Michael","family":"Balzer","sequence":"first","affiliation":[{"name":"University of Konstanz, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Thomas","family":"Schl\u00f6mer","sequence":"additional","affiliation":[{"name":"University of Konstanz, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Oliver","family":"Deussen","sequence":"additional","affiliation":[{"name":"University of Konstanz, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2009,7,27]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009187"},{"key":"e_1_2_2_2_1","volume-title":"Proceedings of the 5th Annual International Symposium on Voronoi Diagrams in Science and Engineering","volume":"2","author":"Balzer M.","unstructured":"Balzer , M. , and Heck , D . 2008. Capacity-constrained Voronoi diagrams in finite spaces . In Proceedings of the 5th Annual International Symposium on Voronoi Diagrams in Science and Engineering , vol. 2 , 44--56. Balzer, M., and Heck, D. 2008. Capacity-constrained Voronoi diagrams in finite spaces. In Proceedings of the 5th Annual International Symposium on Voronoi Diagrams in Science and Engineering, vol. 2, 44--56."},{"key":"e_1_2_2_3_1","volume-title":"Proceedings of the 13th International Meshing Roundtable, 109--120","author":"Chen L.","year":"2004","unstructured":"Chen , L. 2004 . Mesh smoothing schemes based on optimal Delaunay triangulations . In Proceedings of the 13th International Meshing Roundtable, 109--120 . Chen, L. 2004. Mesh smoothing schemes based on optimal Delaunay triangulations. In Proceedings of the 13th International Meshing Roundtable, 109--120."},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/7529.8927"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/325334.325182"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1002\/nla.476"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144599352836"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1179352.1141915"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/1012001"},{"key":"e_1_2_2_10_1","volume-title":"Proceedings of the Vision Modeling and Visualization Conference","author":"Hiller S.","year":"2001","unstructured":"Hiller , S. , Deussen , O. , and Keller , A . 2001. Tiled blue noise samples . In Proceedings of the Vision Modeling and Visualization Conference 2001 , IOS Press, 265--272. Hiller, S., Deussen, O., and Keller, A. 2001. Tiled blue noise samples. In Proceedings of the Vision Modeling and Visualization Conference 2001, IOS Press, 265--272."},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1080\/2151237X.2006.10129217"},{"key":"e_1_2_2_12_1","first-page":"45","article-title":"Efficient illumination by high dynamic range images. In Proceedings of the 14th Eurographics Workshop on Rendering","volume":"44","author":"Kollig T.","year":"2003","unstructured":"Kollig , T. , and Keller , A. 2003 . Efficient illumination by high dynamic range images. In Proceedings of the 14th Eurographics Workshop on Rendering , Eurographics Association , vol. 44 , 45 -- 50 . Kollig, T., and Keller, A. 2003. Efficient illumination by high dynamic range images. In Proceedings of the 14th Eurographics Workshop on Rendering, Eurographics Association, vol. 44, 45--50.","journal-title":"Eurographics Association"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1179352.1141916"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1183287.1183296"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2007.01100.x"},{"key":"e_1_2_2_16_1","unstructured":"Liu Y. Wang W. L&amp;#233;vy B. Sun F. Yan D.-M. Lu L. and Yang C. 2008. On centroidal Voronoi tessellation --- energy smoothness and fast computation. Tech. rep. Hong-Kong University and INRIA-ALICE Project Team.  Liu Y. Wang W. L&amp;#233;vy B. Sun F. Yan D.-M. Lu L. and Yang C. 2008. On centroidal Voronoi tessellation --- energy smoothness and fast computation. Tech. rep. Hong-Kong University and INRIA-ALICE Project Team."},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1982.1056489"},{"key":"e_1_2_2_18_1","volume-title":"Graphics Interface '92","author":"McCool M.","unstructured":"McCool , M. , and Fiume , E . 1992. Hierarchical Poisson disk sampling distributions . Graphics Interface '92 , 94--105. McCool, M., and Fiume, E. 1992. Hierarchical Poisson disk sampling distributions. Graphics Interface '92, 94--105."},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/37401.37410"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1002\/9780470317013"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1186562.1015750"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1275808.1276475"},{"key":"e_1_2_2_23_1","unstructured":"Pharr M. and Humphreys G. 2004. Physically Based Rendering: From Theory to Implementation. Morgan Kaufmann.   Pharr M. and Humphreys G. 2004. Physically Based Rendering: From Theory to Implementation . Morgan Kaufmann."},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/508530.508537"},{"key":"e_1_2_2_25_1","volume-title":"Proceedings of the 12th International Meshing Roundtable, 215--224","author":"Surazhsky V.","unstructured":"Surazhsky , V. , Alliez , P. , and Gotsman , C . 2003. Isotropic remeshing of surfaces: A local parameterization approach . In Proceedings of the 12th International Meshing Roundtable, 215--224 . Surazhsky, V., Alliez, P., and Gotsman, C. 2003. Isotropic remeshing of surfaces: A local parameterization approach. In Proceedings of the 12th International Meshing Roundtable, 215--224."},{"key":"e_1_2_2_26_1","volume-title":"New Approaches to Circle Packing in a Square","author":"Szab","unstructured":"Szab &amp;#243;, P. G., Mark &amp;#243;t, M. C., Csendes , T. , Specht , E. , Casado , L. G. , and Garc &amp;#237;a, I. 2007. New Approaches to Circle Packing in a Square . Springer . Szab&amp;#243;, P. G., Mark&amp;#243;t, M. C., Csendes, T., Specht, E., Casado, L. G., and Garc&amp;#237;a, I. 2007. New Approaches to Circle Packing in a Square. Springer."},{"key":"e_1_2_2_27_1","volume-title":"Digital halftoning","author":"Ulichney R.","unstructured":"Ulichney , R. 1987. Digital halftoning . MIT Press . Ulichney, R. 1987. Digital halftoning. MIT Press."},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1399504.1360619"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/RT.2007.4342600"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.6867716"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1531326.1531392","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1531326.1531392","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:23:12Z","timestamp":1750249392000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1531326.1531392"}},"subtitle":["a variant of Lloyd's method"],"short-title":[],"issued":{"date-parts":[[2009,7,27]]},"references-count":30,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2009,7,27]]}},"alternative-id":["10.1145\/1531326.1531392"],"URL":"https:\/\/doi.org\/10.1145\/1531326.1531392","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,7,27]]},"assertion":[{"value":"2009-07-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}