Geoscience Reference
In-Depth Information
the representation may change every time .x
a
i
/
.x
a
j
/ becomes 0 for some
i;j
2f
1;:::;n
g
with i
¤
j. Next, we analyze the sets where the representation of
the objective function as a weighted sum stays unchanged.
Definition 10.2
The set B
.a
i
;a
j
/ consisting of points
f
x
W
w
i
.x
a
i
/
D
w
j
.x
a
j
/;i
¤
j
g
is called bisector of a
i
and a
j
with respect to .
As an illustration of Definition
10.2
one can see in Fig.
10.1
the bisector line for
the points a
1
and a
2
with the `
1
-norm. The set of bisectors builds a subdivision of
the plane (very similar to the well-known order-k Voronoi diagrams, see the topic
Okabe et al.
1992
). The cells of this subdivision will be called from now on ordered
regions. We formally introduce this concept.
Definition 10.3
Given a permutation
2
P
.1;:::;n/, the ordered region O
is
the following set
2
W
w
1
.x
a
1
/
:::
w
n
.x
a
n
/
g
:
O
Df
x
2
R
Observe that these regions need not be convex sets, see Fig.
10.1
. The ordered
regions play a very important role in the algorithmic approach developed for solving
the problem. Moreover, under the above hypothesis the overall number of ordered
regions in the planar case is O.n
4
G
2
/, see Rodríguez-Chía et al. (
2000
) for further
details. The importance of these regions is that the ordered median function has
a unique linear representation within the intersection of any ordered region with
any elementary convex set. The sets resulting of these intersections are called
generalized elementary convex sets and it is known that the entire set of optimal
solutions of problem (
10.4
) always coincides with some generalized elementary
convex sets, see Puerto and Fernández (
2000
) for further details.
Although the set of optimal solutions of problem (
10.4
) always coincides with
a generalized elementary convex set, the large number of these regions and their
intricate geometry requires some kind of good generation and enumeration schemes
to derive an algorithm. This approach is possible in the plane for polyhedral
gauges. One can easily derive an appealing geometrical algorithm to solve these
problems in the plane. Compute the subdivision of the plane induced by the lines
defining the fundamental directions of the gauges and the bisectors. Observe that
this construction can be efficiently performed using any algorithm to generate
subdivisions induced by arrangements of hyperplanes, see Edelsbrunner (
1987
).
The complexity of computing the ordered regions and its number is O.n
4
G
2
/.Next,
one needs to evaluate the objective function in each vertex of the subdivision. Each
evaluation can be done in O.
nG
log
nG
/. This results in an algorithm that solves the
problem in the plane with a complexity of O.n
5
G
3
log
nG
/.
In what follows we present an alternative, intuitive solution approach for the
polyhedral version of the ordered median problem that consists in a enumerative
algorithm that solves a linear program per visited ordered region. In order to do that,
we first obtain some interesting properties of the following linear program where O
is an ordered region defined by the permutation :
