{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T12:20:15Z","timestamp":1768738815788,"version":"3.49.0"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2022,10,31]],"date-time":"2022-10-31T00:00:00Z","timestamp":1667174400000},"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. Algorithms"],"published-print":{"date-parts":[[2022,10,31]]},"abstract":"<jats:p>\n            This article considers the question of how to succinctly approximate a multidimensional convex body by a polytope. Given a convex body\n            <jats:italic>K<\/jats:italic>\n            of unit diameter in Euclidean\n            <jats:italic>d<\/jats:italic>\n            -dimensional space (where\n            <jats:italic>d<\/jats:italic>\n            is a constant) and an error parameter \u03b5 &gt; 0, the objective is to determine a convex polytope of low combinatorial complexity whose Hausdorff distance from\n            <jats:italic>K<\/jats:italic>\n            is at most \u03b5. By\n            <jats:italic>combinatorial complexity<\/jats:italic>\n            , we mean the total number of faces of all dimensions. Classical constructions by Dudley and Bronshteyn\/Ivanov show that\n            <jats:italic>O<\/jats:italic>\n            (1\/\u03b5\n            <jats:sup>\n              (\n              <jats:italic>d<\/jats:italic>\n              -1)\/2\n            <\/jats:sup>\n            ) facets or vertices are possible, respectively, but neither achieves both bounds simultaneously. In this article, we show that it is possible to construct a polytope with\n            <jats:italic>O<\/jats:italic>\n            (1\/\u03b5\n            <jats:sup>\n              (\n              <jats:italic>d<\/jats:italic>\n              -1)\/2\n            <\/jats:sup>\n            ) combinatorial complexity, which is optimal in the worst case.\n          <\/jats:p>\n          <jats:p>Our result is based on a new relationship between \u03b5-width caps of a convex body and its polar body. Using this relationship, we are able to obtain a volume-sensitive bound on the number of approximating caps that are \u201cessentially different.\u201d We achieve our main result by combining this with a variant of the witness-collector method and a novel variable-thickness layered construction of the economical cap covering.<\/jats:p>","DOI":"10.1145\/3559106","type":"journal-article","created":{"date-parts":[[2022,9,10]],"date-time":"2022-09-10T12:56:58Z","timestamp":1662814618000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Optimal Bound on the Combinatorial Complexity of Approximating Polytopes"],"prefix":"10.1145","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0650-8991","authenticated-orcid":false,"given":"Rahul","family":"Arya","sequence":"first","affiliation":[{"name":"Department of Electrical Engineering and Computer Science, University of California, Berkeley, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0939-4192","authenticated-orcid":false,"given":"Sunil","family":"Arya","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, The Hong Kong University of Science and Technology, Clear Water Bay, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9807-028X","authenticated-orcid":false,"given":"Guilherme D.","family":"da Fonseca","sequence":"additional","affiliation":[{"name":"Aix-Marseille Universit\u00e9 and LIS, Marseille cedex 09, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3290-8932","authenticated-orcid":false,"given":"David","family":"Mount","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Institute for Advanced Computer Studies, University of Maryland, College Park, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,11,11]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-016-0363-x"},{"key":"e_1_3_2_3_2","volume-title":"Combinatorial and Computational Geometry","author":"Agarwal P. K.","year":"2005","unstructured":"P. K. Agarwal, S. Har-Peled, and K. R. Varadarajan. 2005. Geometric approximation via coresets. In Combinatorial and Computational Geometry, J. E. Goodman, J. Pach, and E. Welzl (Eds.). MSRI Publications, Berkeley, CA."},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1963-0143105-7"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/2261250.2261305"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.3"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SoCG.2017.10"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-016-9856-5"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.18"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA.2018.3"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-009-9140-z"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-012-9412-x"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02293050"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01452053"},{"key":"e_1_3_2_15_2","first-page":"21","article-title":"The technique of M-regions and cap-coverings: A survey","volume":"65","author":"B\u00e1r\u00e1ny I.","year":"2000","unstructured":"I. B\u00e1r\u00e1ny. 2000. The technique of M-regions and cap-coverings: A survey. Rend. Circ. Mat. Palermo 65 (2000), 21\u201338.","journal-title":"Rend. Circ. Mat. Palermo"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/453\/08796"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-016-0207-y"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1006\/aima.1999.1904"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1006\/jath.1999.3413"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02573971"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00967115"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10958-008-9144-x"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.20382\/jocg.v9i2a2"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-57155-8_252"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132564"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.20382\/jocg.v7i2a6"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1016\/0021-9045(74)90120-8"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-019-00075-0"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511566172"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1112\/S0025579300002655"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1515\/form.1993.5.281"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-0348-0439-4_9"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574061"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-008-0669-4"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1112\/S0025579300002850"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.STACS.2014.578"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-247X(87)90197-1"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1215\/00127094-00000010X"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1948-09022-X"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.24033\/asens.2482"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3559106","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3559106","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:00:46Z","timestamp":1750186846000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3559106"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,31]]},"references-count":39,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,10,31]]}},"alternative-id":["10.1145\/3559106"],"URL":"https:\/\/doi.org\/10.1145\/3559106","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,10,31]]},"assertion":[{"value":"2020-03-11","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-05-31","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-11-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}