Geoscience Reference
In-Depth Information
7.3.7.2
Locating
p
Lines or Hyperplanes
As in point facility location it is also possible to study the problem of locating p
lines or hyperplanes H
1
;:::;H
P
. In this setting, every existing point is served by
its closest line. We may either minimize the sum of distances
X
n
f
1
.H
1
;:::;H
p
/
D
w
j
min
qD1;:::;p
d.H
q
;v
j
/
(7.15)
jD1
or the maximum distance
f
max
.H
1
;:::;H
p
/
D
max
jD1;:::;n
w
j
min
qD1;:::;p
d.H
q
;v
j
/
(7.16)
from the existing points to their closest lines. Minimizing the sum of distances
is called
p-minsum-hyperplane location problem
and minimizing the maximum
distance to a set of p hyperplanes is called
p-minmax-hyperplane location problem
.
Locating p lines has important applications in statistics with latent classes, and also
provides an alternative approach for clustering, called
projective clustering
(see,
e.g., Har-Peled and Varadarajan
2002
; Deshpande et al.
2006
).
Both problems are known to be NP-hard for most reasonable distance mea-
sures (see Megiddo and Tamir
1982
). However, since each of the p hyperplanes
H
1
;:::;H
p
to be located is a minsum (or minmax) hyperplane for the set of points
V
q
Df
v
2f
v
1
;:::;v
n
gW
d.H
q
;v/
d.H
q
0
;v/for all q
0
D
1;:::;p
g
the results on the finite dominating sets of Theorems
7.4
and
7.7
still hold:
Theorem 7.9
Given
p
2
N
and a set of existing points
V
.
If
n
D
then there exists an optimal solution to the p-minsum-hyperplane
location problem in which each hyperplane passes through
D
existing points.
If
n
D
C
1
then there exists an optimal solution to the p-minmax-hyperplane
location problem in which each of hyperplane is at maximum distance from
D
C
1
existing points.
Hence, enumeration approaches based on such an FDS are possible, however,
the number of candidates to be enumerated is of order O(n
D
). Recently, such an
enumeration approach for the p-minsum line location problem has been enhanced
by computing lower bounds and using them to discard elements from the FDS, see
Schieweck (
2013
). The idea is to cluster the demand points and find a line which
minimizes the sum of distances to the resulting demand regions. This problem is not
easier than the original problem, but since the number of demand regions is much
smaller than n it can be solved quicker.
Based on the FDS, another approach is possible: The problem may be trans-
formed to a p-median or p-center problem on a bipartite graph with O(
j
FDS
j
) nodes.
