The nonlinear programming problem of finding the minimum covering ball of a finite set of points in Rn, with a positive weight corresponding to each point, is solved by a directional search method. At each iteration, the search path is either a ray or the arc of a circle and is determined by bisectors of points. Each step size along the search path is determined explicitly. The primal algorithm is shown to search along the farthest point Voronoi diagram of the given points. We provide computational results that show the efficiency of the algorithm when compared to general convex nonlinear optimization solvers.

A primal algorithm for the weighted minimum covering ball problem in Rn

Belotti P.;
2016-01-01

Abstract

The nonlinear programming problem of finding the minimum covering ball of a finite set of points in Rn, with a positive weight corresponding to each point, is solved by a directional search method. At each iteration, the search path is either a ray or the arc of a circle and is determined by bisectors of points. Each step size along the search path is determined explicitly. The primal algorithm is shown to search along the farthest point Voronoi diagram of the given points. We provide computational results that show the efficiency of the algorithm when compared to general convex nonlinear optimization solvers.
2016
TOP
Minimum covering ball
Min–max location
Nonlinear programming
One-center location
Voronoi diagram
File in questo prodotto:
File Dimensione Formato  
dearing-coveringball.pdf

Accesso riservato

: Publisher’s version
Dimensione 1.26 MB
Formato Adobe PDF
1.26 MB Adobe PDF   Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11311/1163782
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 2
social impact