{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,1]],"date-time":"2025-11-01T02:43:43Z","timestamp":1761965023015,"version":"3.41.0"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2018,7,20]],"date-time":"2018-07-20T00:00:00Z","timestamp":1532044800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2019,4]]},"DOI":"10.1007\/s00454-018-0019-8","type":"journal-article","created":{"date-parts":[[2018,7,20]],"date-time":"2018-07-20T13:53:20Z","timestamp":1532094800000},"page":"595-625","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["( $$\\delta ,{\\varepsilon }$$ \u03b4 , \u03b5 )-Ball Approximation of a Shape: Definition and Complexity"],"prefix":"10.1007","volume":"61","author":[{"given":"Dominique","family":"Attali","sequence":"first","affiliation":[]},{"given":"Tuong-Bach","family":"Nguyen","sequence":"additional","affiliation":[]},{"given":"Isabelle","family":"Sivignon","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,7,20]]},"reference":[{"key":"19_CR1","doi-asserted-by":"crossref","unstructured":"Agarwal, P.K., Pan, J.: Near-linear algorithms for geometric hitting sets and set covers. In: Proceedings of the 30th Annual Symposium on Computational Geometry (SOCG\u201914), pp. 271\u2013279. ACM, New York (2014)","DOI":"10.1145\/2582112.2582152"},{"key":"19_CR2","doi-asserted-by":"crossref","unstructured":"Amenta, N., Kolluri, R.K.: Accurate and efficient unions of balls. In: Proceedings of the 16th Annual Symposium on Computational Geometry (SCG\u201900), pp. 119\u2013128. ACM, New York (2000)","DOI":"10.1145\/336154.336193"},{"key":"19_CR3","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/b106657_6","volume-title":"Mathematical Foundations of Scientific Visualization, Computer Graphics, and Massive Data Exploration","author":"D Attali","year":"2009","unstructured":"Attali, D., Boissonnat, J.-D., Edelsbrunner, H.: Stability and computation of medial axes: a state-of-the-art report. In: M\u00f6ller, T., Hamann, B., Russell, R.D. (eds.) Mathematical Foundations of Scientific Visualization, Computer Graphics, and Massive Data Exploration, pp. 109\u2013125. Springer, Berlin (2009)"},{"key":"19_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1007\/3-540-45749-6_19","volume-title":"Algorithms\u2014ESA 2002","author":"E Berberich","year":"2002","unstructured":"Berberich, E., Eigenwillig, A., Hemmer, M., Hert, S., Mehlhorn, K., Sch\u00f6mer, E.: A computational basis for conic arcs and boolean operations on conic polygons. In: M\u00f6hring, R., Raman, R. (eds.) Algorithms\u2014ESA 2002. Lecture Notes in Computer Science, vol. 2461, pp. 174\u2013186. Springer, Berlin (2002)"},{"issue":"1","key":"19_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/966131.966132","volume":"23","author":"G Bradshaw","year":"2004","unstructured":"Bradshaw, G., O\u2019Sullivan, C.: Adaptive medial-axis approximation for sphere-tree construction. ACM Trans. Graph (TOG) 23(1), 1\u201326 (2004)","journal-title":"ACM Trans. Graph (TOG)"},{"issue":"4","key":"19_CR6","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1007\/BF02570718","volume":"14","author":"H Br\u00f6nnimann","year":"1995","unstructured":"Br\u00f6nnimann, H., Goodrich, M.T.: Almost optimal set covers in finite VC-dimension. Discrete Comput. Geom. 14(4), 463\u2013479 (1995)","journal-title":"Discrete Comput. Geom."},{"key":"19_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1007\/978-3-642-10210-3_5","volume-title":"Combinatorial Image Analysis","author":"A Broutta","year":"2009","unstructured":"Broutta, A., Coeurjolly, D., Sivignon, I.: Hierarchical discrete medial axis for sphere-tree construction. In: Wiederhold, P., Barneva, R.P. (eds.) Combinatorial Image Analysis. Lecture Notes in Computer Science, vol. 5852, pp. 56\u201367. Springer, Berlin (2009)"},{"issue":"6","key":"19_CR8","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1142\/S0218195909003118","volume":"19","author":"S Cabello","year":"2009","unstructured":"Cabello, S., De Berg, M., Giannopoulos, P., Knauer, C., Van Oostrum, R., Veltkamp, R.C.: Maximizing the area of overlap of two unions of disks under rigid motion. Int. J. Comput. Geom. Appl. 19(6), 533\u2013556 (2009)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"19_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1007\/BFb0030817","volume-title":"Computing and Combinatorics","author":"T Calamoneri","year":"1995","unstructured":"Calamoneri, T., Petreschi, R.: An efficient orthogonal grid drawing algorithm for cubic graphs. In: Du, D.-Z., Li, M. (eds.) Computing and Combinatorics. Lecture Notes in Computer Science, vol. 959, pp. 31\u201340. Springer, Berlin (1995)"},{"issue":"6","key":"19_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1111\/cgf.12270","volume":"33","author":"F Cazals","year":"2014","unstructured":"Cazals, F., Dreyfus, T., Sachdeva, S., Shah, N.: Greedy geometric algorithms for collection of balls, with applications to geometric spproximation and molecular coarse-graining. Comput. Graph. Forum 33(6), 1\u201317 (2014)","journal-title":"Comput. Graph. Forum"},{"issue":"9","key":"19_CR11","doi-asserted-by":"publisher","first-page":"1384","DOI":"10.1016\/j.patrec.2010.09.002","volume":"32","author":"J Chaussard","year":"2011","unstructured":"Chaussard, J., Couprie, M., Talbot, H.: Robust skeletonization using the discrete $$\\lambda $$ \u03bb -medial axis. Pattern Recognit. Lett. 32(9), 1384\u20131394 (2011)","journal-title":"Pattern Recognit. Lett."},{"issue":"4","key":"19_CR12","doi-asserted-by":"publisher","first-page":"304","DOI":"10.1016\/j.gmod.2005.01.002","volume":"67","author":"F Chazal","year":"2005","unstructured":"Chazal, F., Lieutier, A.: The $$\\lambda $$ \u03bb -medial axis. Graph. Models 67(4), 304\u2013331 (2005)","journal-title":"Graph. Models"},{"issue":"3","key":"19_CR13","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1287\/moor.4.3.233","volume":"4","author":"V Chvatal","year":"1979","unstructured":"Chvatal, V.: A greedy heuristic for the set-covering problem. Math. Oper. Res. 4(3), 233\u2013235 (1979)","journal-title":"Math. Oper. Res."},{"issue":"3","key":"19_CR14","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1109\/TPAMI.2007.54","volume":"29","author":"D Coeurjolly","year":"2007","unstructured":"Coeurjolly, D., Montanvert, A.: Optimal separable algorithms to compute the reverse Euclidean distance transformation and discrete medial axis in arbitrary dimension. IEEE Trans. Pattern Anal. Mach. Intell. 29(3), 437\u2013448 (2007)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"19_CR15","doi-asserted-by":"crossref","unstructured":"Culver, T., Keyser, J., Manocha, D.: Accurate computation of the medial axis of a polyhedron. In: Proceedings of the 5th ACM Symposium on Solid Modeling and Applications (SMA\u201999), pp. 179\u2013190. ACM, New York (1999)","DOI":"10.1145\/304012.304030"},{"issue":"5","key":"19_CR16","doi-asserted-by":"publisher","first-page":"552","DOI":"10.1016\/j.orl.2013.06.014","volume":"41","author":"PJ Rezende de","year":"2013","unstructured":"de Rezende, P.J., Miyazawa, F.K., Sasaki, A.T.: A PTAS for the disk cover problem of geometric objects. Oper. Res. Lett. 41(5), 552\u2013555 (2013)","journal-title":"Oper. Res. Lett."},{"issue":"2","key":"19_CR17","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/S0010-4485(03)00061-7","volume":"36","author":"TK Dey","year":"2004","unstructured":"Dey, T.K., Zhao, W.: Approximate medial axis as a Voronoi subcomplex. Comput. Aid. Des. 36(2), 195\u2013202 (2004)","journal-title":"Comput. Aid. Des."},{"key":"19_CR18","series-title":"Mathematical Sciences Research Institute Publications","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1017\/9781009701259.015","volume-title":"Combinatorial and Computational Geometry","author":"H Edelsbrunner","year":"2005","unstructured":"Edelsbrunner, H., Koehl, P.: The geometry of biomolecular solvation. In: Goodman, J.E., Pach, J., Welzl, E. (eds.) Combinatorial and Computational Geometry. Mathematical Sciences Research Institute Publications, vol. 52, pp. 243\u2013275. Cambridge University Press, Cambridge (2005)"},{"key":"19_CR19","doi-asserted-by":"publisher","first-page":"418","DOI":"10.1090\/S0002-9947-1959-0110078-1","volume":"93","author":"H Federer","year":"1959","unstructured":"Federer, H.: Curvature measures. Trans. Am. Math. Soc. 93, 418\u2013491 (1959)","journal-title":"Trans. Am. Math. Soc."},{"key":"19_CR20","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/j.matchar.2015.05.023","volume":"106","author":"J Feinauer","year":"2015","unstructured":"Feinauer, J., Spettl, A., Manke, I., Strege, S., Kwade, A., Pott, A., Schmidt, V.: Structural characterization of particle systems using spherical harmonics. Mater. Charact. 106, 123\u2013133 (2015)","journal-title":"Mater. Charact."},{"key":"19_CR21","doi-asserted-by":"crossref","DOI":"10.1201\/9781420035315","volume-title":"Handbook of Discrete and Computational Geometry","author":"G Fejes T\u00f3th","year":"2004","unstructured":"Fejes T\u00f3th, G.: Packing and covering. In: Goodman, J.E., O\u2019Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, 2nd edn. Chapman & Hall\/CRC, Boca Raton (2004)","edition":"2"},{"issue":"4","key":"19_CR22","doi-asserted-by":"publisher","first-page":"826","DOI":"10.1137\/0132071","volume":"32","author":"MR Garey","year":"1977","unstructured":"Garey, M.R., Johnson, D.S.: The rectilinear Steiner tree problem is NP-complete. SIAM J. Appl. Math. 32(4), 826\u2013834 (1977)","journal-title":"SIAM J. Appl. Math."},{"key":"19_CR23","doi-asserted-by":"crossref","unstructured":"Har-Peled, S.: Geometric Approximation Algorithms. Mathematical Surveys and Monographs, vol. 173. American Mathematical Society, Providence (2011)","DOI":"10.1090\/surv\/173"},{"key":"19_CR24","volume-title":"Algebr. Topol.","author":"A Hatcher","year":"2002","unstructured":"Hatcher, A.: Algebr. Topol. Cambridge University Press, Cambridge (2002)"},{"issue":"3","key":"19_CR25","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1109\/2945.466717","volume":"1","author":"PM Hubbard","year":"1995","unstructured":"Hubbard, P.M.: Collision detection for interactive graphics applications. IEEE Trans. Vis. Comput. Graph. 1(3), 218\u2013230 (1995)","journal-title":"IEEE Trans. Vis. Comput. Graph."},{"issue":"3","key":"19_CR26","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1145\/231731.231732","volume":"15","author":"PM Hubbard","year":"1996","unstructured":"Hubbard, P.M.: Approximating polyhedra with spheres for time-critical collision detection. ACM Trans. Graph. (TOG) 15(3), 179\u2013210 (1996)","journal-title":"ACM Trans. Graph. (TOG)"},{"issue":"3","key":"19_CR27","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"DS Johnson","year":"1974","unstructured":"Johnson, D.S.: Approximation algorithms for combinatorial problems. Comput. Syst. Sci. 9(3), 256\u2013278 (1974)","journal-title":"Comput. Syst. Sci."},{"key":"19_CR28","doi-asserted-by":"publisher","first-page":"665","DOI":"10.2307\/2371320","volume":"61","author":"R Kershner","year":"1939","unstructured":"Kershner, R.: The number of circles covering a set. Am. J. Math. 61, 665\u2013671 (1939)","journal-title":"Am. J. Math."},{"issue":"4","key":"19_CR29","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1145\/1778765.1778838","volume":"29","author":"B Miklos","year":"2010","unstructured":"Miklos, B., Giesen, J., Pauly, M.: Discrete scale axis representations for 3D geometry. ACM Trans. Graph. (TOG) 29(4), 101 (2010)","journal-title":"ACM Trans. Graph. (TOG)"},{"key":"19_CR30","unstructured":"Nguyen, T.-B., Sivignon, I.: Epsilon-covering: a greedy optimal algorithm for simple shapes. In: Canadian Conference on Computational Geometry, Vancouver, pp. 187\u2013194 (2016)"},{"key":"19_CR31","unstructured":"Pach, J. (ed.): New Trends in Discrete and Computational Geometry. Algorithms and Combinatorics, vol. 10. Springer, Berlin (2012)"},{"issue":"3","key":"19_CR32","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1111\/1467-8659.1530129","volume":"15","author":"V Ranjan","year":"1996","unstructured":"Ranjan, V., Fournier, A.: Matching and interpolation of shapes using unions of circles. Comput. Graph. Forum 15(3), 129\u2013142 (1996)","journal-title":"Comput. Graph. Forum"},{"key":"19_CR33","volume-title":"Image Analysis and Mathematical Morphology","author":"J Serra","year":"1982","unstructured":"Serra, J.: Image Analysis and Mathematical Morphology, vol. 1. Academic Press, New York (1982)"},{"key":"19_CR34","unstructured":"Wein, R., Zukerman, B.: Exact and efficient construction of planar arrangements of circular arcs and line segments with applications. Tech. Rep. ACS-TR-121200-01. Tel Aviv University (2006)"},{"key":"19_CR35","unstructured":"Wein, R., Berberich, E., Fogel, E., Halperin, D., Hemmer, M., Salzman, O., Zukerman, B.: 2D Arrangements. CGAL: Computational Geometry Algorithms Library"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-018-0019-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-018-0019-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-018-0019-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,5]],"date-time":"2025-07-05T22:48:08Z","timestamp":1751755688000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-018-0019-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7,20]]},"references-count":35,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,4]]}},"alternative-id":["19"],"URL":"https:\/\/doi.org\/10.1007\/s00454-018-0019-8","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2018,7,20]]},"assertion":[{"value":"4 July 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 May 2018","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 June 2018","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 July 2018","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}