{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,13]],"date-time":"2026-08-13T11:36:56Z","timestamp":1786621016721,"version":"3.56.0"},"reference-count":82,"publisher":"Wiley","license":[{"start":{"date-parts":[[2026,8,13]],"date-time":"2026-08-13T00:00:00Z","timestamp":1786579200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"},{"start":{"date-parts":[[2026,8,13]],"date-time":"2026-08-13T00:00:00Z","timestamp":1786579200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/doi.wiley.com\/10.1002\/tdm_license_1.1"}],"funder":[{"DOI":"10.13039\/100019180","name":"HORIZON EUROPE European Research Council","doi-asserted-by":"publisher","award":["101055448"],"award-info":[{"award-number":["101055448"]}],"id":[{"id":"10.13039\/100019180","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Computer Graphics Forum"],"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>The convex hull is a central concept in computational geometry, geometry processing, and generally for summarizing sampled data. Its descriptive power suffers significantly in the presence of noise. The k\u2010hull, also known as the k\u2010depth contour in statistics, is the intersection of all half\u2010spaces that contain all but k data points, i.e. it is a convex hull ignoring k points in any direction. While it is well established theoretically, the lack of a robust and efficient algorithm, especially for the 3D case, limits applications. We combine ideas of an intuitive algorithm for the 2D case with gift wrapping and improve efficiency using established spatial data structures. The clear concept also facilitates a generalization to weighted data, allowing us to ignore points whose weights sum up to at most a given tolerance. For the case of unweighted data with unknown noise characteristics, we determine a simple heuristic for estimating k to adjust to outliers in the data. We demonstrate the effectiveness of the algorithm on the examples of computing convex hulls for data with noise and for visibility determination via convex hulls.<\/jats:p>","DOI":"10.1111\/cgf.70529","type":"journal-article","created":{"date-parts":[[2026,8,13]],"date-time":"2026-08-13T11:09:00Z","timestamp":1786619340000},"update-policy":"https:\/\/doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A practical algorithm for weighted\n                    <i>k<\/i>\n                    \u2010hulls"],"prefix":"10.1111","author":[{"ORCID":"https:\/\/orcid.org\/0009-0004-6807-4724","authenticated-orcid":false,"given":"N.","family":"Look","sequence":"first","affiliation":[{"name":"TU Berlin  Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-4803-750X","authenticated-orcid":false,"given":"H.","family":"Meyer","sequence":"additional","affiliation":[{"name":"TU Berlin  Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9854-8466","authenticated-orcid":false,"given":"M.","family":"Alexa","sequence":"additional","affiliation":[{"name":"TU Berlin  Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"311","published-online":{"date-parts":[[2026,8,13]]},"reference":[{"key":"e_1_2_9_2_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795281840"},{"key":"e_1_2_9_3_2","volume-title":"ACM SIGGRAPH 2022 Conference Proceedings","author":"Alexa M.","year":"2022"},{"key":"e_1_2_9_3_3","doi-asserted-by":"crossref","unstructured":"doi:10.1145\/3528233.3530743. 2","DOI":"10.1145\/3528233.3530743"},{"key":"e_1_2_9_4_2","unstructured":"AklS. G. ToussaintG. T.: Efficient convex hull algorithms for pattern recognition applications. InProceedings of the Fourth International Joint Conference on Pattern Recognition(Kyoto Japan November1979) pp.483\u2013487. 1"},{"key":"e_1_2_9_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2020.102856"},{"key":"e_1_2_9_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/116873.116880"},{"key":"e_1_2_9_6_3","doi-asserted-by":"crossref","unstructured":"doi:10.1145\/116873.116880. 2","DOI":"10.1145\/116873.116880"},{"key":"e_1_2_9_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/235815.235821"},{"key":"e_1_2_9_7_3","doi-asserted-by":"crossref","unstructured":"doi:10.1145\/235815.235821. 3 7","DOI":"10.1145\/235815.235821"},{"key":"e_1_2_9_8_2","volume-title":"CGAL User and Reference Manual","author":"Br\u00f6nnimann H.","year":"2025"},{"key":"e_1_2_9_9_2","doi-asserted-by":"publisher","DOI":"10.3150\/20-BEJ1229"},{"key":"e_1_2_9_9_3","unstructured":"doi:10.3150\/20\u2010BEJ1229. 2"},{"key":"e_1_2_9_10_2","doi-asserted-by":"crossref","unstructured":"ChanT. M. ChengP. ZhengD. W.: An optimal algorithm for higher\u2010order voronoi diagrams in the plane: The usefulness of nondeterminism. InProceedings of the 2024 Annual ACM\u2010SIAM Symposium on Discrete Algorithms (SODA)(2024) pp.4451\u20134463. URL:https:\/\/epubs.siam.org\/doi\/abs\/10.1137\/1.9781611977912.156","DOI":"10.1137\/1.9781611977912.156"},{"key":"e_1_2_9_10_3","doi-asserted-by":"crossref","unstructured":"doi:10.1137\/1.9781611977912.156. 7","DOI":"10.1137\/1.9781611977912.156"},{"key":"e_1_2_9_11_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1985.1057060"},{"key":"e_1_2_9_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02712873"},{"key":"e_1_2_9_12_3","doi-asserted-by":"crossref","unstructured":"doi:10.1007\/BF02712873. 3","DOI":"10.1007\/BF02712873"},{"key":"e_1_2_9_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/3414685.3417818"},{"key":"e_1_2_9_13_3","doi-asserted-by":"crossref","unstructured":"doi:10.1145\/3414685.3417818. 4","DOI":"10.1145\/3414685.3417818"},{"key":"e_1_2_9_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/3550454.3555460"},{"key":"e_1_2_9_14_3","doi-asserted-by":"crossref","unstructured":"doi:10.1145\/3550454.3555460. 4","DOI":"10.1145\/3550454.3555460"},{"key":"e_1_2_9_15_2","doi-asserted-by":"publisher","DOI":"10.1137\/0216005"},{"key":"e_1_2_9_15_3","doi-asserted-by":"crossref","unstructured":"doi:10.1137\/0216005. 2 3 4 13 14","DOI":"10.1137\/0216005"},{"key":"e_1_2_9_16_2","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-77974-2","volume-title":"Computational Geometry: Algorithms and Applications","author":"De Berg M.","year":"2008"},{"key":"e_1_2_9_16_3","unstructured":"doi:10.1007\/978\u20103\u2010540\u201077974\u20102. 14"},{"key":"e_1_2_9_17_2","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.2021.2011298"},{"key":"e_1_2_9_17_3","doi-asserted-by":"crossref","unstructured":"doi:10.1080\/01621459.2021.2011298. 2","DOI":"10.1080\/01621459.2021.2011298"},{"key":"e_1_2_9_18_2","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-61568-9","volume-title":"Algorithms in combinatorial geometry","author":"Edelsbrunner H.","year":"1987"},{"key":"e_1_2_9_19_2","unstructured":"EdelsbrunnerH. GarberA. SaghafianM.:On spheres withkpoints inside 2025. URL:http:\/\/arxiv.org\/abs\/2410.21204 arXiv:2410.21204[math] doi:10.48550\/arXiv.2410.21204. 2"},{"key":"e_1_2_9_20_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1983.1056714"},{"key":"e_1_2_9_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/77635.77639"},{"key":"e_1_2_9_21_3","doi-asserted-by":"crossref","unstructured":"doi:10.1145\/77635.77639. 5 7 13","DOI":"10.1145\/77635.77639"},{"key":"e_1_2_9_22_2","unstructured":"EdelsbrunnerH. M\u00fcckeE.:Three\u2010dimensional alpha shapes 1994. URL:https:\/\/arxiv.org\/abs\/math\/9410208 arXiv:math\/9410208. 2"},{"key":"e_1_2_9_23_2","doi-asserted-by":"publisher","DOI":"10.1137\/0215019"},{"key":"e_1_2_9_23_3","doi-asserted-by":"crossref","unstructured":"arXiv:https:\/\/doi.org\/10.1137\/0215019","DOI":"10.1137\/0215019"},{"key":"e_1_2_9_23_4","doi-asserted-by":"crossref","unstructured":"doi:10.1137\/0215019. 14","DOI":"10.1137\/0215019"},{"key":"e_1_2_9_24_2","doi-asserted-by":"publisher","DOI":"10.1080\/10618600.2023.2257781"},{"key":"e_1_2_9_25_2","unstructured":"GuptaP. NarayananA.:A (hilbert) geometric algorithm for approximating the halfspace depth of a point in a convex body 2025. URL:http:\/\/arxiv.org\/abs\/2411.01482 arXiv:2411.01482[cs] doi:10.48550\/arXiv.2411.01482. 2"},{"key":"e_1_2_9_26_2","unstructured":"Har\u2010PeledS. KaplanH. SharirM.:Approximating thek\u2010level in three\u2010dimensional plane arrangements 2016. URL:https:\/\/arxiv.org\/abs\/1601.04755 arXiv:1601.04755. 14"},{"key":"e_1_2_9_27_2","doi-asserted-by":"publisher","DOI":"10.1007\/s41060-025\u201000928\u20103"},{"key":"e_1_2_9_27_3","unstructured":"doi:10.1007\/s41060\u2010025\u201000928\u20103. 3"},{"key":"e_1_2_9_28_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(73)90020\u20103"},{"key":"e_1_2_9_29_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2013.07.023"},{"key":"e_1_2_9_30_2","doi-asserted-by":"publisher","DOI":"10.1137\/0215021"},{"key":"e_1_2_9_30_3","doi-asserted-by":"crossref","unstructured":"doi:10.1137\/0215021. 3","DOI":"10.1137\/0215021"},{"key":"e_1_2_9_31_2","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1145\/1275808.1276407","volume-title":"ACM SIGGRAPH 2007 papers","author":"Katz S.","year":"2007"},{"key":"e_1_2_9_31_3","doi-asserted-by":"crossref","unstructured":"doi:10.1145\/1275808.1276407. 2 9","DOI":"10.1145\/1275808.1276407"},{"issue":"8","key":"e_1_2_9_32_2","doi-asserted-by":"crossref","first-page":"927","DOI":"10.1177\/0278364912445831","article-title":"The KIT object models database: An object model database for object recognition, localization and manipulation in service robotics","volume":"31","author":"Kasper A.","year":"2012","journal-title":"The International Journal of Robotics Research"},{"key":"e_1_2_9_32_3","doi-asserted-by":"crossref","unstructured":"doi:10.1177\/0278364912445831. 10","DOI":"10.1177\/0278364912445831"},{"key":"e_1_2_9_33_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2015.10.004"},{"key":"e_1_2_9_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/3744642"},{"key":"e_1_2_9_34_3","doi-asserted-by":"crossref","unstructured":"doi:10.1145\/3744642. 4 5 7","DOI":"10.1145\/3744642"},{"key":"e_1_2_9_35_2","unstructured":"L\u00f6fflerM. MulzerW.: Unions of onions: preprocessing imprecise points for fast onion decomposition.Journal of Computational Geometry (2014) Vol.5No.1(2014). URL:https:\/\/jocg.org\/index.php\/jocg\/article\/view\/2923 doi:10.20382\/JOCG.V5I1A1. 3"},{"key":"e_1_2_9_36_2","doi-asserted-by":"publisher","DOI":"10.1080\/10618600.2018.1546595"},{"key":"e_1_2_9_37_2","first-page":"107","article-title":"On the number of halving lines","volume":"14","author":"Lov\u00e1sz L.","year":"1971","journal-title":"Ann. Univ. Sci. Budapest. E\u00f6tv\u00f6s Sect. Math."},{"key":"e_1_2_9_38_2","unstructured":"LiuR. ZhangH. BusbyJ.: Convex hull covering of polygonal scenes for accurate collision detection in games. InGraphics Interface(2008). URL:https:\/\/api.semanticscholar.org\/CorpusID:3137131. 1"},{"key":"e_1_2_9_39_2","doi-asserted-by":"publisher","DOI":"10.3390\/s23229135"},{"key":"e_1_2_9_40_2","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-0039-7","volume-title":"Lectures on Discrete Geometry, vol. 212 of Graduate Texts in Mathematics","author":"Matou\u0161ek J.","year":"2002"},{"key":"e_1_2_9_40_3","unstructured":"doi:10.1007\/978\u20101\u20104613\u20100039\u20107. 2"},{"key":"e_1_2_9_41_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1023208625954"},{"key":"e_1_2_9_42_2","doi-asserted-by":"publisher","DOI":"10.1002\/wics.70038"},{"key":"e_1_2_9_42_3","doi-asserted-by":"crossref","unstructured":"doi:10.1002\/wics.70038. 2","DOI":"10.1002\/wics.70038"},{"key":"e_1_2_9_43_2","doi-asserted-by":"publisher","DOI":"10.2312\/SPBG\/SPBG04\/077\u2010084"},{"key":"e_1_2_9_44_2","first-page":"1541","volume-title":"Handbook of Discrete and Computational Geometry","author":"Rousseeuw P.","year":"2018"},{"key":"e_1_2_9_45_2","volume-title":"The design and analysis of spatial data structures","author":"Samet H.","year":"1990"},{"key":"e_1_2_9_46_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009745219419"},{"key":"e_1_2_9_46_3","doi-asserted-by":"crossref","unstructured":"doi:10.1023\/A:1009745219419. 1","DOI":"10.1023\/A:1009745219419"},{"key":"e_1_2_9_47_2","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1007\/978-3-032-12840-9_14","volume-title":"Pattern Recognition","author":"Sivaprasad S.","year":"2026"},{"key":"e_1_2_9_48_2","doi-asserted-by":"publisher","DOI":"10.1145\/237218.237337"},{"key":"e_1_2_9_49_2","doi-asserted-by":"crossref","unstructured":"SchmittD. SpehnerJ.\u2010C.: k\u2010set polytopes and order\u2010k delaunay diagrams. In2006 3rd International Symposium on Voronoi Diagrams in Science and Engineering(2006) pp.173\u2013185. doi:10.1109\/ISVD.2006.43. 2","DOI":"10.1109\/ISVD.2006.43"},{"key":"e_1_2_9_50_2","unstructured":"SvenningR. SridharV.: Fast area\u2010weighted peeling of convex hulls for outlier detection. InProceedings of the 36th Canadian Conference on Computational Geometry(July2024) pp.233\u2013240. 3"},{"key":"e_1_2_9_51_2","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1145\/336154.336173","volume-title":"Proceedings of the Sixteenth Annual Symposium on Computational Geometry","author":"Sharir M.","year":"2000"},{"key":"e_1_2_9_51_3","doi-asserted-by":"crossref","unstructured":"doi:10.1145\/336154.336173. 7","DOI":"10.1145\/336154.336173"},{"key":"e_1_2_9_52_2","unstructured":"Stanford:The stanford 3d scanning repository 1994. URL:http:\/\/graphics.stanford.edu\/data\/3Dscanrep\/. 9"},{"key":"e_1_2_9_53_2","first-page":"523","volume":"2","author":"Tukey J. W.","year":"1975","journal-title":"Proceedings of the international congress of mathematicians"},{"key":"e_1_2_9_54_2","doi-asserted-by":"crossref","first-page":"452","DOI":"10.1142\/9789812831699_0011","volume-title":"Computing in Euclidean Geometry","author":"Yap C.","year":"1995"},{"key":"e_1_2_9_54_3","doi-asserted-by":"crossref","unstructured":"doi:10.1142\/9789812831699_0011. 4","DOI":"10.1142\/9789812831699_0011"},{"key":"e_1_2_9_55_2","doi-asserted-by":"publisher","DOI":"10.1093\/jrsssb\/qkaf030"},{"key":"e_1_2_9_55_3","doi-asserted-by":"crossref","unstructured":"doi:10.1093\/jrsssb\/qkaf030. 2","DOI":"10.1093\/jrsssb\/qkaf030"},{"key":"e_1_2_9_56_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11263-024\u201002117\u20104"},{"key":"e_1_2_9_56_3","unstructured":"doi:10.1007\/s11263\u2010024\u201002117\u20104. 3"},{"key":"e_1_2_9_57_2","unstructured":"ZhouQ. JacobsonA.: Thingi10K: A dataset of 10 000 3d\u2010printing models.arXiv preprint arXiv:1605.04797(2016). 7 8"}],"container-title":["Computer Graphics Forum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1111\/cgf.70529","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/full-xml\/10.1111\/cgf.70529","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1111\/cgf.70529","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,13]],"date-time":"2026-08-13T11:09:16Z","timestamp":1786619356000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1111\/cgf.70529"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,8,13]]},"references-count":82,"alternative-id":["10.1111\/cgf.70529"],"URL":"https:\/\/doi.org\/10.1111\/cgf.70529","archive":["Portico"],"relation":{},"ISSN":["0167-7055","1467-8659"],"issn-type":[{"value":"0167-7055","type":"print"},{"value":"1467-8659","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,8,13]]},"assertion":[{"value":"2026-08-13","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"e70529"}}