{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T13:41:02Z","timestamp":1768743662359,"version":"3.49.0"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2017,1,18]],"date-time":"2017-01-18T00:00:00Z","timestamp":1484697600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2017,1,18]],"date-time":"2017-01-18T00:00:00Z","timestamp":1484697600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1117259"],"award-info":[{"award-number":["CCF-1117259"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1618866"],"award-info":[{"award-number":["CCF-1618866"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002920","name":"Research Grants Council, University Grants Committee","doi-asserted-by":"publisher","award":["610012"],"award-info":[{"award-number":["610012"]}],"id":[{"id":"10.13039\/501100002920","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2017,12]]},"DOI":"10.1007\/s00454-016-9856-5","type":"journal-article","created":{"date-parts":[[2017,1,18]],"date-time":"2017-01-18T15:10:09Z","timestamp":1484752209000},"page":"849-870","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["On the Combinatorial Complexity of Approximating Polytopes"],"prefix":"10.1007","volume":"58","author":[{"given":"Sunil","family":"Arya","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guilherme D.","family":"da Fonseca","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3290-8932","authenticated-orcid":false,"given":"David M.","family":"Mount","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,1,18]]},"reference":[{"issue":"4","key":"9856_CR1","doi-asserted-by":"publisher","first-page":"606","DOI":"10.1145\/1008731.1008736","volume":"51","author":"PK Agarwal","year":"2004","unstructured":"Agarwal, P.K., Har-Peled, S., Varadarajan, K.R.: Approximating extent measures of points. J. ACM 51(4), 606\u2013635 (2004)","journal-title":"J. ACM"},{"issue":"2","key":"9856_CR2","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1090\/S0002-9947-1963-0143105-7","volume":"106","author":"GE Andrews","year":"1963","unstructured":"Andrews, G.E.: A lower bound for the volumes of strictly convex bodies with many boundary points. Trans. Am. Math. Soc. 106(2), 270\u2013279 (1963)","journal-title":"Trans. Am. Math. Soc."},{"issue":"3","key":"9856_CR3","doi-asserted-by":"publisher","first-page":"398","DOI":"10.1007\/s00454-009-9140-z","volume":"41","author":"S Arya","year":"2009","unstructured":"Arya, S., Malamatos, T., Mount, D.M.: The effect of corners on the complexity of approximate range searching. Discrete Comput. Geom. 41(3), 398\u2013443 (2009)","journal-title":"Discrete Comput. Geom."},{"key":"9856_CR4","doi-asserted-by":"crossref","unstructured":"Arya, S., da\u00a0Fonseca, G.D., Mount, D.M.: Optimal area-sensitive bounds for polytope approximation. In: Proceedings of the 28th Annual ACM Symposium on Computational Geometry, pp. 363\u2013372 (2012)","DOI":"10.1145\/2261250.2261305"},{"key":"9856_CR5","doi-asserted-by":"crossref","unstructured":"Arya, S., da\u00a0Fonseca, G.D., Mount, D.M.: Optimal approximate polytope membership. In: Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (2017, to appear)","DOI":"10.1137\/1.9781611974782.18"},{"issue":"4","key":"9856_CR6","doi-asserted-by":"publisher","first-page":"711","DOI":"10.1007\/s00454-012-9412-x","volume":"47","author":"S Arya","year":"2012","unstructured":"Arya, S., Mount, D.M., Xia, J.: Tight lower bounds for halfspace range searching. Discrete Comput. Geom. 47(4), 711\u2013730 (2012)","journal-title":"Discrete Comput. Geom."},{"issue":"4","key":"9856_CR7","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1007\/BF01452053","volume":"285","author":"I B\u00e1r\u00e1ny","year":"1989","unstructured":"B\u00e1r\u00e1ny, I.: Intrinsic volumes and $$f$$-vectors of random polytopes. Math. Ann. 285(4), 671\u2013699 (1989)","journal-title":"Math. Ann."},{"key":"9856_CR8","first-page":"21","volume":"65","author":"I B\u00e1r\u00e1ny","year":"2000","unstructured":"B\u00e1r\u00e1ny, I.: The technique of $$M$$-regions and cap-coverings: a survey. Rend. Circ. Mat. Palermo Suppl. 65, 21\u201338 (2000)","journal-title":"Rend. Circ. Mat. Palermo Suppl."},{"key":"9856_CR9","doi-asserted-by":"crossref","unstructured":"B\u00e1r\u00e1ny, I.: Extremal problems for convex lattice polytopes: a survey. In: Goodman, J.E., Pach, J., Pollack, R. (eds.) Surveys on Discrete and Computational Geometry. Contemporary Mathematics, vol. 453, pp. 87\u2013103. American Mathematical Society, Providence (2008)","DOI":"10.1090\/conm\/453\/08796"},{"issue":"2","key":"9856_CR10","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1112\/S0025579300015266","volume":"35","author":"I B\u00e1r\u00e1ny","year":"1988","unstructured":"B\u00e1r\u00e1ny, I., Larman, D.G.: Convex bodies, economic cap coverings, random polytopes. Mathematika 35(2), 274\u2013291 (1988)","journal-title":"Mathematika"},{"issue":"2","key":"9856_CR11","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1006\/aima.1999.1904","volume":"153","author":"K B\u00f6r\u00f6czky Jr","year":"2000","unstructured":"B\u00f6r\u00f6czky Jr., K.: Approximation of general smooth convex bodies. Adv. Math. 153(2), 325\u2013341 (2000)","journal-title":"Adv. Math."},{"issue":"2","key":"9856_CR12","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/BF02573971","volume":"10","author":"H Br\u00f6nnimann","year":"1993","unstructured":"Br\u00f6nnimann, H., Chazelle, B., Pach, J.: How hard is halfspace range searching? Discrete Comput. Geom. 10(2), 143\u2013155 (1993)","journal-title":"Discrete Comput. Geom."},{"issue":"5","key":"9856_CR13","doi-asserted-by":"publisher","first-page":"852","DOI":"10.1007\/BF00967115","volume":"16","author":"EM Bronshteyn","year":"1976","unstructured":"Bronshteyn, E.M., Ivanov, L.D.: The approximation of convex sets by polyhedra. Sib. Math. J. 16(5), 852\u2013853 (1976)","journal-title":"Sib. Math. J."},{"issue":"6","key":"9856_CR14","doi-asserted-by":"publisher","first-page":"727","DOI":"10.1007\/s10958-008-9144-x","volume":"153","author":"EM Bronstein","year":"2008","unstructured":"Bronstein, E.M.: Approximation of convex sets by polytopes. J. Math. Sci. 153(6), 727\u2013762 (2008)","journal-title":"J. Math. Sci."},{"key":"9856_CR15","doi-asserted-by":"crossref","unstructured":"Clarkson, K.L.: Algorithms for polytope covering and approximation. In: Proceedings of the Third International Workshop Algorithms and Data Structures, pp. 246\u2013252 (1993)","DOI":"10.1007\/3-540-57155-8_252"},{"key":"9856_CR16","doi-asserted-by":"crossref","unstructured":"Clarkson, K.L.: Building triangulations using $$\\varepsilon $$-nets. In: Proceedings of the 38th Annual ACM Symposium on Theory Computing, pp. 326\u2013335 (2006)","DOI":"10.1145\/1132516.1132564"},{"key":"9856_CR17","doi-asserted-by":"crossref","unstructured":"Devillers, O., Glisse, M., Goaoc, X.: Complexity analysis of random geometric structures made simpler. In: Proceedings of the 29th Annual ACM Symposium on Computational Geometry, pp. 167\u2013176 (2013)","DOI":"10.1145\/2462356.2462362"},{"issue":"3","key":"9856_CR18","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1016\/0021-9045(74)90120-8","volume":"10","author":"RM Dudley","year":"1974","unstructured":"Dudley, R.M.: Metric entropy of some classes of sets with differentiable boundaries. J. Approx. Theory 10(3), 227\u2013236 (1974)","journal-title":"J. Approx. Theory"},{"issue":"1","key":"9856_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1112\/S0025579300002655","volume":"17","author":"G Ewald","year":"1970","unstructured":"Ewald, G., Larman, D.G., Rogers, C.A.: The directions of the line segments and of the $$r$$-dimensional balls on the boundary of a convex body in Euclidean space. Mathematika 17(1), 1\u201320 (1970)","journal-title":"Mathematika"},{"key":"9856_CR20","unstructured":"Fejes T\u00f3th, L.: Approximation by polygons and polyhedra. Bull. Am. Math. Soc. 54(4), 431\u2013438 (1948)"},{"issue":"6","key":"9856_CR21","first-page":"521","volume":"5","author":"PM Gruber","year":"1993","unstructured":"Gruber, P.M.: Asymptotic estimates for best and stepwise approximation of convex bodies II. Forum Math. 5(6), 521\u2013538 (1993)","journal-title":"Forum Math."},{"key":"9856_CR22","volume-title":"Geometric Approximation Algorithms. Mathematical Surveys and Monographs","author":"S Har-Peled","year":"2011","unstructured":"Har-Peled, S.: Geometric Approximation Algorithms. Mathematical Surveys and Monographs, vol. 173. American Mathematical Society, Providence, RI (2011)"},{"key":"9856_CR23","unstructured":"John, F.: Extremum problems with inequalities as subsidiary conditions. In: Studies and Essays Presented to R. Courant on his 60th Birthday, pp. 187\u2013204. Interscience, New York (1948)"},{"issue":"2","key":"9856_CR24","doi-asserted-by":"publisher","first-page":"269","DOI":"10.2307\/1969800","volume":"56","author":"AM Macbeath","year":"1952","unstructured":"Macbeath, A.M.: A theorem on non-homogeneous lattices. Ann. Math. 56(2), 269\u2013293 (1952)","journal-title":"Ann. Math."},{"issue":"2","key":"9856_CR25","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1112\/S0025579300002850","volume":"17","author":"P McMullen","year":"1970","unstructured":"McMullen, P.: The maximum numbers of faces of a convex polytope. Mathematika 17(2), 179\u2013184 (1970)","journal-title":"Mathematika"},{"issue":"2","key":"9856_CR26","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0925-7721(95)00006-U","volume":"5","author":"JSB Mitchell","year":"1995","unstructured":"Mitchell, J.S.B., Suri, S.: Separation and approximation of polyhedral objects. Comput. Geom. 5(2), 95\u2013114 (1995)","journal-title":"Comput. Geom."},{"issue":"2","key":"9856_CR27","doi-asserted-by":"publisher","first-page":"470","DOI":"10.1016\/0022-247X(87)90197-1","volume":"128","author":"R Schneider","year":"1987","unstructured":"Schneider, R.: Polyhedral approximation of smooth convex bodies. J. Math. Anal. Appl. 128(2), 470\u2013474 (1987)","journal-title":"J. Math. Anal. Appl."}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-016-9856-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-016-9856-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-016-9856-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,17]],"date-time":"2020-05-17T06:36:38Z","timestamp":1589697398000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-016-9856-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,1,18]]},"references-count":27,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,12]]}},"alternative-id":["9856"],"URL":"https:\/\/doi.org\/10.1007\/s00454-016-9856-5","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,1,18]]},"assertion":[{"value":"18 July 2016","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 December 2016","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 December 2016","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 January 2017","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}