Geoscience Reference
In-Depth Information
in dual space and may be interpreted as the weighted bisectors of the lines T
H
.v
j
/
and T
H
.v
i
/. Taking the intersection of these regions with the regions R.H
;H
/
of the proof of Theorem
7.4
, we obtain quasiconcavity on the resulting (smaller)
cells. This yields that the extreme points of these new cells are a finite dominating
set.
t
This FDS allows an algorithm to solve the ordered line location problem in
O(n
4
), see Lozano and Plastria (
2009
) for the Euclidean case. The problem of
locating a hyperplane minimizing the Euclidean ordered median function has been
investigated in Kapelushnik (
2008
) where its equivalence to searching within the
levels of an arrangement is shown. The resulting algorithm runs in O(n
2D
) where its
complexity is reduced to O(n
DCminfD1;KC1g
)ifK
Djf
j
D
1;:::;n
W
j
6D
0
gj
.
A special case concerns the k-centrum line location problem, in which the sum of
distances from the line to the k most distant points is minimized. It is also an ordered
median problem and has been treated in Lozano et al. (
2010
). The methodology
is similar to the approach of the general ordered median problem and exploits
quasiconcavity of the objective function in the cells mentioned above. For smooth
norms, it is shown that the resulting finite dominating set consists of lines either
passing through two existing points or being at equal weighted distance from three
of them. Based on this, an O(.k
C
log n/n
3
) algorithm is proposed for computing all
t-centrum lines for 1
t
k. For unweighted points, Kapelushnik (
2008
) suggests
an algorithm that finds a k-centrum line in the plane in time O (n log n
C
nk
).
7.3.7
Some Extensions of Line and Hyperplane Location
Problems
7.3.7.1
Obnoxious Line and Hyperplane Location
Instead of
minimizing
the distances to the existing points, one may also consider
an obnoxious problem in which the new facility should be as far away from the
existing points as possible. A rather general approach for obnoxious line location is
presented in Lozano et al. (
2013
) in which a weighted ordered median function is
maximized. More precisely, the problem treated is the following: Given a connected
polygonal set S in the plane, the goal is to find a line which intersects S and
maximizes the sum of ordered weighted Euclidean distances to the existing points.
For such problems, the authors are again able to derive a finite dominating set which
yields an O(n
4
) algorithm for the general Euclidean anti-ordered median case, and
an O(n
2
) algorithm for the case of the Euclidean anti-median line. The case of
locating an obnoxious plane (i.e., finding the widest empty slab through a set of
existing points V ) has been considered in Díaz-Bánez et al. (
2006a
). Also here, a
finite dominating set could be identified leading to an algorithm in time O(n
3
).
