Abstract

We introduce and study the following problem and its further generalizations: given two finite collections of sets in a normed space, find a ball whose center lies in a given constraint set with the smallest radius that encloses all the sets in the first collection and intersects all the sets in the second one. This problem can be considered as a generalized version of the Sylvester smallest enclosing circle problem introduced in the 19th century by Sylvester which asks for the circle of smallest radius enclosing a given set of finite points in the plane. We also consider a generalized version of the Fermat-Torricelli problem: given two finite collections of sets in a normed space, find a point in a given constraint set that minimizes the sum of the farthest distances to the sets in the first collection and shortest distances (distances) to the sets in the second collection.

Author information

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

Nguyen Mau Nam

Fariborz Maseeh Dept. of Mathematics and Statistics, Portland State University, Portland, OR 97202, U.S.A.

mau.nam.nguyen@pdx.edu

Keywords

  • Sylvester smallest enclosing circle problem
  • Fermat-Torricelli problem
  • smallest enclosing ball problem
  • smallest intersecting ball problem

Mathematics Subject Classification

49J52, 49J53, 90C31

References

  1. J. Alonso, H. Martini, M. Spirova: Minimal enclosing discs, circumcircles, and circumcenters in normed planes. I, Comput. Geom. 45 (2012) 258–274.https://doi.org/10.1016/j.comgeo.2012.01.007Google Scholar
  2. V. Boltynski, H. Martini, V. Soltan: Geometric Methods and Optimization Problems, Kluwer, Dordrecht (1999).https://doi.org/10.1007/978-1-4615-5319-9Google Scholar
  3. 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
  4. 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
  5. R. Deville, V. E. Zizler: Farthest points in w∗ − compact sets, Bull. Austral. Math. Soc. 38 (1988) 433–439.https://doi.org/10.1017/S0004972700027817Google Scholar
  6. 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
  7. 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
  8. K. S. Lau: Farthest points in weakly compact sets, Isr. J. Math. 22 (1975) 168–174.https://doi.org/10.1007/BF02760164Google Scholar
  9. H. Martini, K. J. Swanepoel, G. Weiss: The Fermat-Torricelli problem in normed planes and spaces, J. Optim. Theory Appl. 115 (2002) 283–314.https://doi.org/10.1023/A:1020884004689Google Scholar
  10. B. S. Mordukhovich: Variational Analysis and Generalized Differentiation. I: Basic Theory, II: Applications, Grundlehren der Mathematischen Wissenschaften 330 and 331, Springer, Berlin (2006).https://doi.org/10.1007/3-540-31246-3Google Scholar
  11. B. S. Mordukhovich, N. M. Nam, C. Villalobos: The smallest enclosing ball problem and the smallest intersecting ball problem: existence and uniqueness of optimal solutions, Optim. Lett. 154 (2012) 768–791.https://doi.org/10.1007/s10957-012-0048-zGoogle Scholar
  12. B. S. Mordukhovich, N. M. Nam, J. Salinas: Applications of variational analysis to a generalized Heron problem, Appl. Anal. 91 (2012) 1915–1942.https://doi.org/10.1080/00036811.2011.604849Google Scholar
  13. 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
  14. N. M. Nam, N. T. An, J. Salinas: Applications of convex analysis to the smallest intersecting ball problem, J. Convex Analysis 19 (2012) 497–518.https://doi.org/10.68381/jca19027Google Scholar
  15. N. M. Nam, N. Hoang, N. T. An: A generalized Sylvester problem and a generalized Fermat-Torricelli problem for Euclidean balls, preprint.Google 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, Q. J. Pure Appl. Math. 1 (1857) 79.Google Scholar
  18. T. V. Tan: An extension of the Fermat-Torricelli problem, J. Optim. Theory Appl. 146 (2010) 735–744.https://doi.org/10.1007/s10957-010-9686-1Google Scholar
  19. E. Welzl: Smallest enclosing disks (balls ellipsoids), in: 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

Suggested citation

N. M. Nam, N. Hoang. “A Generalized Sylvester Problem and a Generalized Fermat-Torricelli Problem.” Journal of Convex Analysis 20 (2013), No. 3, 669–687. https://doi.org/10.68381/jca20038

Download BibTeXPublished by Heldermann Verlag.

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