{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,15]],"date-time":"2025-12-15T19:25:34Z","timestamp":1765826734355},"reference-count":26,"publisher":"World Scientific Pub Co Pte Lt","issue":"04n05","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2004,10]]},"abstract":"<jats:p> We develop algorithms for computing the exact smallest enclosing ball of a set of n balls in d-dimensional space. Unlike previous methods, we explicitly address small cases (n\u2264d+2), derive the necessary primitive operations and show that they can efficiently be realized with rational arithmetic. An implementation (along with a fast and robust floating-point version) is available as part of the CGAL library. <\/jats:p><jats:p> We show that Welzl's randomized linear-time algorithm for computing the ball spanned by a set of points fails to work for balls. Consequently, the existing adaptations of the method to the ball case are incorrect. In solving the small cases we may assume that the ball centers are affinely independent. Via a geometric transformation and suitable generalization, it fits into the combinatorial model of unique sink orientations whose rich structure has recently received considerable attention. One consequence is that Welzl's algorithm does work for small instances; moreover, there is a variety of pivoting methods for unique sink orientations which have the potential of being fast in practice even for high dimensions. As a by-product, we show that the problem of finding the smallest enclosing ball of balls with a fixed point on the boundary is equivalent to the problem of finding the minimum-norm point in the convex hull of a union of balls. <\/jats:p>","DOI":"10.1142\/s0218195904001500","type":"journal-article","created":{"date-parts":[[2004,10,15]],"date-time":"2004-10-15T09:11:35Z","timestamp":1097831495000},"page":"341-378","source":"Crossref","is-referenced-by-count":37,"title":["THE SMALLEST ENCLOSING BALL OF BALLS: COMBINATORIAL STRUCTURE AND ALGORITHMS"],"prefix":"10.1142","volume":"14","author":[{"given":"KASPAR","family":"FISCHER","sequence":"first","affiliation":[{"name":"Institut f\u00fcr Theoretische  Informatik, ETH Z\u00fcrich, CH-8092 Z\u00fcrich, Switzerland"}]},{"given":"BERND","family":"G\u00c4RTNER","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Theoretische  Informatik, ETH Z\u00fcrich, CH-8092 Z\u00fcrich, Switzerland"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","volume-title":"Nonlinear Programming: Theory and Applications","author":"Bazaraa M. S.","year":"1979"},{"key":"rf2","volume-title":"Geometry","volume":"1","author":"Berger M.","year":"1987"},{"key":"rf3","unstructured":"M.\u00a0B\u0103doiu and K. L.\u00a0Clarkson, Proc. Fourteenth Ann. ACM-SIAM Symp. Discrete algorithms (Society for Industrial and Applied Mathematics, 2003)\u00a0pp. 801\u2013802."},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509947"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0060"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1145\/201019.201036"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1137\/0213003"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-61568-9"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793250287"},{"key":"rf11","doi-asserted-by":"crossref","unstructured":"B.\u00a0G\u00e4rtner, Proc. 7th Ann. European Symp. Algorithms (ESA), Lecture Notes Comput. Sci.\u00a01643 (Springer-Verlag, 1999)\u00a0pp. 325\u2013338.","DOI":"10.1007\/3-540-48481-7_29"},{"key":"rf12","unstructured":"B.\u00a0G\u00e4rtner and E.\u00a0Welzl, Proc. 19th Symp. Theoret. Aspects Comput. Sci., Lecture Notes Comput. Sci.\u00a01046 (Springer-Verlag, 1996)\u00a0pp. 669\u2013387."},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45506-X_3"},{"key":"rf15","unstructured":"A.\u00a0Goel, P.\u00a0Indyk and K.\u00a0Varadarajan, Proc. Twelfth Ann. ACM-SIAM Symp. Discrete Algorithms (Society for Industrial and Applied Mathematics, 2001)\u00a0pp. 769\u2013778."},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1145\/231731.231732"},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.1145\/304893.304989"},{"key":"rf20","first-page":"1.1","volume":"8","author":"Kumar P.","journal-title":"J. Exp. Algorithmics"},{"key":"rf22","doi-asserted-by":"publisher","DOI":"10.1007\/BF01940877"},{"key":"rf23","doi-asserted-by":"publisher","DOI":"10.1137\/0212052"},{"key":"rf24","doi-asserted-by":"publisher","DOI":"10.1145\/2422.322418"},{"key":"rf25","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187750"},{"key":"rf26","volume-title":"LEDA: A Platform for Combinatorial and Geometric Computing","author":"Mehlhorn K.","year":"2000"},{"key":"rf28","volume-title":"Proc. Int. Conf. Computational Science and Its Applications (ICCSA)","volume":"3045","author":"Nielsen F.","year":"2004"},{"key":"rf29","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1025-2"},{"key":"rf30","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574375"},{"key":"rf33","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0038202"},{"key":"rf35","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022977709811"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195904001500","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:28:30Z","timestamp":1565137710000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195904001500"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,10]]},"references-count":26,"journal-issue":{"issue":"04n05","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2004,10]]}},"alternative-id":["10.1142\/S0218195904001500"],"URL":"https:\/\/doi.org\/10.1142\/s0218195904001500","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,10]]}}}