Geoscience Reference
In-Depth Information
There is also a relation to equity problems (see Gluchshenko
2008
; Drezner
and Drezner
2007
) of point facility location and to a problem in computational
geometry which is to find an annulus of smallest width. These relations are specified
in Sect.
7.4.4.1
.
In statistics, the problem is also of interest. As Nievergelt (
2002
) points out,
many attempts have been made of transferring total least squares algorithms from
hyperplane location problems to hypersphere location problems (e.g., Kasa
1976
;
Moura and Kitney
1992
;Crawford
1983
; Rorres and Romano
1997
;Späth
1997
,
1998
; Coope
1993
; Gander et al.
1994
;Nievergelt
2004
).
7.4.2
Distances Between Points and Hyperspheres
Let d be a distance derived from some norm
kk
,i.e.,d.x;y/
Dk
y
x
k
.A
circle or a sphere with respect to the norm
kk
is given by its center point x
D
.x
1
;:::;x
D
/
2
D
and its radius r>0:
R
D
W
d.x;y/
D
r
g
:
S
x;r
Df
y
2
R
D
is defined as
The distance between a sphere S
D
S
x;r
and a point v
2
R
d.S;v/
D
min
y2S
d.y;v/
and can be computed as
d.S
x;r
;v/
Dj
d.x;v/
r
j
:
The following properties of the distance can easily be shown.
Lemma 7.5 (Körner et al.
2012
;Körner
2011
)
Given a distance
d
derived from
a norm, and a point
v
2
D
, the following hold:
R
d.S
x;r
;v/
is convex and piecewise linear in
r
,
d.S
x;r
;v/
is locally convex in
.x;r/
if
v
is a point outside the sphere, and
d.S
x;r
;v/
is concave in
.x;r/
if
v
is inside the sphere.
Before analyzing minsum or minmax circles or hyperspheres, let us remark that
even the special case with only n
D
3 existing points in the plane (D
D
2)
is a surprisingly interesting problem. Within a wider context it has recently been
studied in Alonso et al. (
2012a
,
b
). Here, the circumcircle of a set of three points is
investigated (which is the optimal minmax or minsum circle for the three points).
Dependent on the norm considered, such a circumcircle need not exist, and need
not be unique. Among other results on covering problems, the work focuses on a
complete description of possible locations of the center points of such circumcircles.