Geoscience Reference
In-Depth Information
Note that the problem of locating a Euclidean minmax circle in the plane is older
than the corresponding Euclidean minsum circle problem; a finite dominating set
has already been identified in Rivlin (
1979
). Its rectangular version is due to
Gluchshenko et al. (
2009
). In
D
the Euclidean minmax hypersphere location
problem has been analyzed mainly in the Euclidean case, see Nievergelt (
2002
).
R
7.4.4.1
Relation to Minimal Covering Annulus Problem and Equity
Problem
The problem of locating a minmax circle has a nice geometric interpretation. For
equally weighted points it may be interpreted as finding an annulus of minimal width
covering all existing points. This problem has been studied in computational geom-
etry, hence results on minmax circle location have been obtained independently in
location theory and in computational geometry.
In location science the minmax hypersphere location problem has an interesting
application as a point location problem. Namely, the (unweighted) center point x of
an optimal hypersphere S
x;r
minimizes the difference
jD1;:::;n
d.x;v
j
/
min
max
jD1;:::;n
d.x;v
j
/;
i.e., it minimizes the
range
to the set V . We conclude that minmax hypersphere
location problems can be interpreted as ordered median point location problems.
Therefore, the point x may be interpreted as a fair location for a service facility as
used in equity problems, see Gluchshenko (
2008
) for further results.
7.4.4.2
Location of a Euclidean Minmax Circle
Let us start with the Euclidean case in dimension D
D
2: In this case, the problem
has been discussed extensively in the literature, mainly in computational geometry
under the name of finding an annulus of smallest width. In contrast to the Euclidean
minsum circle problem, where an FDS could not be found, the following result
shows that an FDS for the (Euclidean) minmax hypersphere exists.
Theorem 7.12 (FDS for the Euclidean Minmax Circle)
(e.g., Rivlin
1979
;Brim-
berg et al.
2009a
)Let
D
D
2
and let
C
be a minmax circle with finite radius. Let
h
WD
max
jD1;:::;n
w
j
d.C;v
j
/
. Then there exist four points having distance
h
to the
circle
C
, two of them inside the circle and two of them outside the circle.
The theorem was shown for the unweighted case independently in many papers,
among others in Rivlin (
1979
), Ebara et al. (
1989
), García-López et al. (
1998
)and
it was generalized to the weighted case in Brimberg et al. (
2009a
). The result can be
interpreted in different ways:
