Geoscience Reference
In-Depth Information
D
, i.e., we have transformed the problem
with distance d
e
g
to a problem with vertical distance which can be solved by linear
programming as above. Transforming an optimal hyperplane H
0
for the resulting
problem back to T
1
.H
0
/ gives an optimal solution to the problem with distance
d
e
g
. Details can be found in Schöbel (
1999a
,
1996
).
for any hyperplane H and any point v
2
R
7.3.5.3
Enhancing the Enumeration for Line Location
with Euclidean Distance
For the Euclidean distance, the minsum straight line problem has received a
lot of attention. Many of the ideas proposed here could also be used for other
distance functions (see Schieweck and Schöbel
2012
); nevertheless they have been
investigated mainly for the Euclidean case. Algorithms rely on Theorems
7.3
and
7.4
and use the representation of the problem in the dual space.
The Euclidean minsum straight line problem with unit weights can be solved
by sweeping along the so called
median trajectory
in the dual space (see
Yamamoto et al.
1988
). The median trajectory is the point-wise median of the
lines T
H
.v
j
/;j
D
1;:::;n,seeFig.
7.4
for the median trajectory in our example.
The breakpoints on the median trajectory coincide with lines passing through two
of the existing points and satisfying the halving property. Hence, the complexity
of the approach depends on the number h.n/ of halving lines. In Yamamoto et al.
(
1988
) the complexity of the approach is given as O(log
2
.n/h.n/) which can be
improved to O(log.n/h.n/) (see Schieweck and Schöbel
2012
) by substituting the
algorithm for dynamic convex hulls of Overmars and van Leeuwen (
1981
)bythe
newer O(log.n/) algorithm of Brodal and Jacob (
2002
).
Note that the order of h.n/ is not known yet. It has been shown that the number
of halving lines is in O(n
4=3
)(seeDey
1998
) yielding an O(n
4=3
log.n/) approach
for the line location problem with Euclidean distance. The best known lower bound
for the Euclidean minsum line location problem is ǝ.nlogn/ using reduction from
L
4
L
3
L
1
L
2
Fig. 7.4
The median
trajectory for the example of
Fig.
7.2
L
5
