IDEAS home Printed from https://ideas.repec.org/a/inm/ormnsc/v19y1972i1p96-104.html
   My bibliography  Save this article

The Minimum Covering Sphere Problem

Author

Listed:
  • D. Jack Elzinga

    (The Johns Hopkins University)

  • Donald W. Hearn

    (University of Florida)

Abstract

The minimum covering sphere problem, with applications in location theory, is that of finding the sphere of smallest radius which encloses a set of points in E n . For a finite set of points, it is shown that the Wolfe dual is equivalent to a particular quadratic programming problem and that converse duality holds. A finite decomposition algorithm, based on the Simplex method of quadratic programming, is developed for which computer storage requirements are independent of the number of points and computing time is approximately linear in the number of points.

Suggested Citation

  • D. Jack Elzinga & Donald W. Hearn, 1972. "The Minimum Covering Sphere Problem," Management Science, INFORMS, vol. 19(1), pages 96-104, September.
    • Handle: RePEc:inm:ormnsc:v:19:y:1972:i:1:p:96-104
    DOI: 10.1287/mnsc.19.1.96
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/mnsc.19.1.96
    Download Restriction: no
    File URL: https://libkey.io/10.1287/mnsc.19.1.96?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. O Berman & Z Drezner, 2003. "A probabilistic one-centre location problem on a network," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 54(8), pages 871-877, August.
    2. P. M. Dearing & Mark E. Cawood, 2023. "The minimum covering Euclidean ball of a set of Euclidean balls in $$I\!\!R^n$$ I R n," Annals of Operations Research, Springer, vol. 322(2), pages 631-659, March.
    3. Miren Bilbao & Sergio Gil-López & Javier Ser & Sancho Salcedo-Sanz & Mikel Sánchez-Ponte & Antonio Arana-Castro, 2014. "Novel hybrid heuristics for an extension of the dynamic relay deployment problem over disaster areas," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 22(3), pages 997-1016, October.
    4. B. Pelegrín & L. Cánovas, 1996. "An improvement and an extension of the Elzinga & Hearn's algorithm to the 1-center problem in ℝ n withl 2b -normswithl 2b -norms," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 4(2), pages 269-284, December.
    5. Pelegrin, B. & Canovas, L., 1998. "A new assignment rule to improve seed points algorithms for the continuous k-center problem," European Journal of Operational Research, Elsevier, vol. 104(2), pages 366-374, January.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ormnsc:v:19:y:1972:i:1:p:96-104. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.