Miniball
The smallest enclosing ball of balls: combinatorial structure and algorithms 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≤d+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. 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
(Source: http://plato.asu.edu)
Keywords for this software
References in zbMATH (referenced in 44 articles , 1 standard article )
Showing results 1 to 20 of 44.
Sorted by year (- Cavaleiro, Marta; Alizadeh, Farid: A dual simplex-type algorithm for the smallest enclosing ball of balls (2021)
- Choi, Jongmin; Jeong, Dahye; Ahn, Hee-Kap: Covering convex polygons by two congruent disks (2021)
- Limbeck, Jan; Bisdom, Kevin; Lanz, Fabian; Park, Timothy; Barbaro, Eduardo; Bourne, Stephen; Kiraly, Franz; Bierman, Stijn; Harris, Chris; Nevenzeel, Keimpe; den Bezemer, Taco; van Elk, Jan: Using machine learning for model benchmarking and forecasting of depletion-induced seismicity in the Groningen gas field (2021)
- Marrinan, Tim; Absil, P.-A.; Gillis, Nicolas: On a minimum enclosing ball of a collection of linear subspaces (2021)
- An, Nguyen Thai; Nam, Nguyen Mau; Qin, Xiaolong: Solving (k)-center problems involving sets based on optimization techniques (2020)
- Bauer, U.; Edelsbrunner, H.; Jabłoński, G.; Mrozek, M.: Čech-Delaunay gradient flow and homology inference for self-maps (2020)
- Clarkson, Kenneth L.; Gärtner, Bernd; Lengler, Johannes; Szedlák, May: Random sampling with removal (2020)
- Fauvin, Françoise; Roux, Jean-Christophe; Monnet, Pierre; Feulvarch, Eric: Fast estimation of the shear stress amplitude for fatigue life analysis of metals (2020)
- Alimov, A. R.; Tsar’kov, I. G.: Chebyshev centres, Jung constants, and their applications (2019)
- Castro, Paula M.; Dapena, Adriana; Souto-Salorio, María J.; Tarrío-Tobar, Ana D.: Algorithms for determining relative position between spheroids and hyperboloids with one sheet (2019)
- Pronzato, Luc: On the elimination of inessential points in the smallest enclosing ball problem (2019)
- Weber, Tobias; Sager, Sebastian; Gleixner, Ambros: Solving quadratic programs to high precision using scaled iterative refinement (2019)
- Kociumaka, Tomasz; Pachocki, Jakub W.; Radoszewski, Jakub; Rytter, Wojciech; Waleń, Tomasz: On the string consensus problem and the Manhattan sequence consensus problem (2018)
- Gagolewski, Marek: Penalty-based aggregation of multidimensional data (2017)
- Jiang, Yi; Luo, Chuan; Ling, Shenggui: An efficient cutting plane algorithm for the smallest enclosing circle problem (2017)
- Toth, Csaba D. (ed.); Goodman, Jacob E. (ed.); O’Rourke, Joseph (ed.): Handbook of discrete and computational geometry (2017)
- Dearing, P. M.; Belotti, Pietro; Smith, Andrea M.: A primal algorithm for the weighted minimum covering ball problem in (\mathbbR^n) (2016)
- Liu, Ya-Feng; Diao, Rui; Ye, Feng; Liu, Hong-Wei: An efficient inexact Newton-CG algorithm for the smallest enclosing ball problem of large dimensions (2016)
- Nedělková, Zuzana; Lindroth, Peter; Strömberg, Ann-Brith; Patriksson, Michael: Integration of expert knowledge into radial basis function surrogate models (2016)
- Nguyen Thai An; Giles, Daniel; Nguyen Mau Nam; Rector, R. Blake: The log-exponential smoothing technique and Nesterov’s accelerated gradient method for generalized Sylvester problems (2016)