Geoscience Reference
In-Depth Information
7.4.4.4
Location of a Euclidean Minmax Hypersphere
The problem of finding a minmax hypersphere in dimension D
3 was considered
in García-López et al. (
1998
). The authors give necessary and sufficient conditions
for a point to be the center point of a
locally
minimal hypersphere with respect
to f
max
. Independently, also Nievergelt (
2002
) considers the problem of locating
a hypersphere in
D
with Euclidean distance. Analogously to his approach for
minmax hyperplanes, he interprets the problem as the location of two concentric
hyperspheres with minimal distance which enclose the set V of existing points. This
results in a generalization of Theorem
7.12
to higher dimensions.
R
Theorem 7.14 (FDS for the Euclidean Minmax Hypersphere)
(Nievergelt
2002
)
There exists a Euclidean minmax hypersphere
S
which is rigidly supported by the
point set
V
, i.e., there does not exist any other pair of concentric hyperspheres
enclosing all points of
V
and passing through the same points of
V
as
S
.
Based on this property, Nievergelt (
2002
) derives a finite algorithm finding a
minmax hypersphere with respect to the Euclidean distance. A linear time .1
C
/
factor approximation algorithm for finding a Euclidean minmax hypersphere is
given in Chan (
2000
).
7.4.5
Some Extensions of Circle Location Problems
7.4.5.1
Minimizing the Sum of Squared Distances
An earlier variant of the hypersphere location problem minimizes the sum of
squared
distances of the existing points to the circle, i.e., it considers
X
n
w
j
d.S
x;r
;v
j
/
2
f
2
.S
x;r
/
D
jD1
as objective function. In Drezner et al. (
2002
) it is shown that the least squares
objective is equivalent to minimizing the variance of the distances. The problem is
(like the minsum and minmax problem) non-convex; heuristic solution approaches
are suggested. In Drezner and Drezner (
2007
) the Big-Triangle-Small-Triangle
global optimization algorithm is successfully applied.
Minimizing the sum of squared distances from the points in V to a circle has
been also considered within statistics in Kasa (
1976
), Crawford (
1983
), Moura and
Kitney (
1992
), Coope (
1993
), Gander et al. (
1994
), Rorres and Romano (
1997
),
Späth (
1997
,
1998
), and Nievergelt (
2004
).
