Geoscience Reference
In-Depth Information
the uniform-gap on a circle problem (Yamamoto et al.
1988
). We conclude that the
question for an optimal algorithm for this problem is still open.
The Euclidean line location problem with arbitrary weights can be solved in
O(n
2
), see Lee and Ching (
1985
).
For the Euclidean minmax line location problem the relation to transversal theory
is exploited leading to an optimal O(n log n) algorithm for the case with arbitrary
weights (Edelsbrunner
1985
).
7.3.6
Ordered Median Line and Hyperplane Location Problem
A rather general objective function in location theory is the ordered median function
(see Nickel and Puerto
2005
, or Chap.
10
). For tackling ordered median line location
problems, one can combine the ideas of the preceding results on minsum and
minmax location.
Theorem 7.8 (FDS for Ordered Line Location)
(See Lozano and Plastria
2009
for the Planar Euclidean Case) Let
d
be derived from a norm and let
n
2
.Then
there exists a solution
l
to the ordered line location problem w.r.t distance
d
that
satisfies at least one of the following conditions:
l
passes through two of the existing points.
l
passes through one of the existing points and is at same weighted distance
from two of the existing points.
l
is at the same weighted distance from three of the existing points.
There exist two pairs of existing points
v
j
;v
j
0
2
V
and
v
k
;v
k
0
2
V
such that
w
j
d.l
;v
j
/
D
w
j
0
d.l
;v
j
0
/
and w
k
d.l
;v
k
/
D
w
k
0
d.l
;v
k
0
/;
i.e.,
l
is at the same weighted distance from both points of each of the two pairs.
Sketch of Proof
The theorem has been shown in Lozano and Plastria (
2009
)forthe
ordered Euclidean line location problem, but also holds for all distances derived
from norms: Again, we look at the regions in dual space in which the order of the
distances from the line to the existing points does not change, i.e., in which
d.H
a;b
;v
j
/
D
d.H
a;b
;v
i
/
does not hold for any j
6D
i. These regions are hence bounded by the affine linear
sets
.a;b/
W
w
j
j
a
t
v
j
C
b
j
ı
.a/
Df
.a;b/
W
w
j
j
a
t
v
j
C
b
jD
w
i
j
a
t
v
i
C
b
jg
D
w
i
j
a
t
v
i
C
b
j
ı
.a/
