Abstract

The smallest enclosing circle problem asks for the circle of smallest radius enclosing a given set of finite points on the plane. This problem was introduced in 1857 by J. J. Sylvester. After more than a century, the problem remains very active. This paper is the continuation of our effort in shedding new light to classical geometry problems using advanced tools of convex analysis and optimization. We propose and study the following generalized version of the smallest enclosing circle problem: given a finite number of nonempty closed convex sets in a reflexive Banach space, find a ball with the smallest radius that intersects all of the sets.

Author information

Contact details are reproduced from the original publication and may be historical.

Nguyen Mau Nam

Dept. of Mathematics, The University of Texas - Pan American, Edinburg, TX 78539–2999, U.S.A.

nguyenmn@utpa.edu

Juan Salinas

Dept. of Mathematics, The University of Texas - Pan American, Edinburg, TX 78539–2999, U.S.A.

jsalinasn@broncs.utpa.edu

Keywords

  • Convex analysis
  • convex optimization
  • generalized differentiation
  • smallest enclosing ball problem
  • smallest intersecting ball problem
  • subgradient-type algorithms

Mathematics Subject Classification

49J52, 49J53, 90C31

References

  1. D. Bertsekas, A. Nedic, A. Ozdaglar: Convex Analysis and Optimization, Athena Scientific, Belmont (2003).Google Scholar
  2. J. M. Borwein, A. S. Lewis: Convex Analysis and Nonlinear Optimization: Theory and Examples, 2nd Ed., Springer, New York (2006).https://doi.org/10.1007/978-0-387-31256-9Google Scholar
  3. M. Bounkhel, L. Thibault: On various notions of regularity of sets in nonsmooth analysis, Nonlinear Anal. 48 (2002) 223–246.https://doi.org/10.1016/S0362-546X(00)00183-8Google Scholar
  4. S. Boyd, L. Xiao, A. Mutapcic: Subgradient methods, Lecture notes, Stanford University (2003).Google Scholar
  5. J. Burke, M. C. Ferris, M. Quian: On the Clarke subdifferential of the distance function of a closed set, J. Math. Anal. Appl. 166 (1992) 199–213.https://doi.org/10.1016/0022-247X(92)90336-CGoogle Scholar
  6. D. Cheng, X. Hu, C. Martin: On the smallest enclosing balls, Commun. Inf. Syst. 6 (2006) 137–160.https://doi.org/10.4310/CIS.2006.v6.n2.a3Google Scholar
  7. L. Drager, J. Lee, C. Martin: On the geometry of the smallest circle enclosing a finite set of points, J. Franklin Inst. 344 (2007) 929–940.https://doi.org/10.1016/j.jfranklin.2007.01.003Google Scholar
  8. D. Gisch, J. M. Ribando: Apollonius problem: A study of solutions and their connections, Amer. J. Undergrad. Res. 3 (2004) 15–26.https://doi.org/10.33697/ajur.2004.010Google Scholar
  9. J.-B. Hiriart-Urruty, C. Lemaréchal: Convex Analysis and Minimization Algorithms I. Fundamentals, Springer, Berlin (1993).https://doi.org/10.1007/978-3-662-02796-7Google Scholar
  10. A. D. Ioffe, V. M. Tichomirov: Theory of Extremal Problems, North-Holland, Amsterdam (1979).Google Scholar
  11. G. M. Lee, N. N. Tam, N. D. Yen: Quadratic Programming and Affine Variational Inequalities: A Qualitative Study, Springer, New York (2005).Google Scholar
  12. B. S. Mordukhovich: Variational Analysis and Generalized Differentiation, I: Basic Theory, II: Applications, Fundamental Principles of Mathematical Sciences 330 and 331, Springer, Berlin (2006).Google Scholar
  13. B. S. Mordukhovich, N. M. Nam: Subgradients of minimal time functions under minimal requirements, J. Convex Analysis 18 (2011) 915–947.https://doi.org/10.68381/jca18058Google Scholar
  14. B. S. Mordukhovich, N. M. Nam: Applications of variational analysis to a generalized Fermat-Torricelli problem, J. Optim. Theory Appl. 148 (2011) 431–454.https://doi.org/10.1007/s10957-010-9761-7Google Scholar
  15. B. S. Mordukhovich, N. M. Nam, J. Salinas: Solving a generalized Heron problem by means of convex analysis, Amer. Math. Monthly 119 (2012) 87–99.https://doi.org/10.4169/amer.math.monthly.119.02.087Google Scholar
  16. F. Nielsen, R. Nock: Approximating smallest enclosing balls with applications to machine learning, Int. J. Comput. Geom. Appl. 19 (2009) 389–414.https://doi.org/10.1142/S0218195909003039Google Scholar
  17. J. J. Sylvester: A question in the geometry of situation, Quart. J. Pure Appl. Math. 1 (1857) 79.Google Scholar
  18. E. Welzl: Smallest enclosing disks (balls ellipsoids), in: New Results and New Trends in Computer Science (Graz, 1991), H. Maurer (ed.), Lecture Notes in Comput. Sci. 555, Springer, Berlin (1991) 359–370.https://doi.org/10.1007/BFb0038202Google Scholar
  19. R. T. Rockafellar: Convex Analysis, Princeton University Press, Princeton (1970).https://doi.org/10.1515/9781400873173Google Scholar

Suggested citation

N. M. Nam, T. A. Nguyen, J. Salinas. “Applications of Convex Analysis to the Smallest Intersecting Ball Problem.” Journal of Convex Analysis 19 (2012), No. 2, 497–518. https://doi.org/10.68381/jca19027

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 2012. Rights now held by Banach Press LLC.