Geoscience Reference
In-Depth Information
restrictions on the parameters of the hyperplane can again be treated and solved in
dual space, see Krempasky (
2012
).
Another type of restriction is to force a subset of points of V to lie on, above
or below the hyperplane. Also for such problems, finite dominating sets have
been derived, see Schöbel (
2003
) for hyperplane location problems in which the
hyperplane is forced to pass through a subset of points and Plastria and Carrizosa
(
2012
) for the more general case of requiring a specified subset of points below or
above the hyperplane.
7.3.7.4
Line Location with Polyhedra as Existing Facilities
There are also a few approaches considering the location of lines when the existing
facilities are connected sets or polyhedra in
2
. The minmax problem is equivalent
to finding the thinnest strip transversal, i.e., a strip of minimal width which intersects
each of the existing polyhedra. For m polyhedra with a total of n vertices, Robert
(
1991
) and Robert and Toussaint (
1994
) solve the Euclidean problem by computing
the upper and the lower envelope of the dual representation of the existing sets
resulting in an O(n log n) approach in the unweighted case and in an O(n
2
logn)
approach in the weighted case. For the minsum problem, the algorithm works by
sweeping the dual arrangement and takes O(
mn
log m) time.
R
R
D
7.3.7.5
Line Location in
D
turns out to be a difficult problem since all of the structure
of line and hyperplane location problems gets lost. In Brimberg et al. (
2002
,
2003
)
some special cases are investigated for the case D
D
3, such as locating a vertical
line, or locating a line where the distance measure is given as the lengths of
horizontal paths. If these lengths are measured with the rectangular distance, the
problem can be reduced to two planar line location problems with vertical distance.
For the general case of locating a minsum line in
Locating a line in
R
3
, global optimization methods
such as Big-Cube-Small-Cube (Schöbel and Scholz
2010
) have been successfully
used, see Blanquero et al. (
2011
). The case of locating a minmax line in
R
D
is
known in computational geometry as smallest enclosing cylinder problem. It has
been mainly researched in
R
3
(Schömer et al.
2000
;Chan
2000
).
R
7.4
Locating Circles and Spheres
We now turn our attention to the location of hyperspheres. Again, we have given
a set of existing points V
D
with positive weights
w
j
>0;j
D
1;:::;n.
The
hypersphere location problem
is to find the center point and the radius of a
hypersphere S which minimizes the distances from its surface to the points in V .
R
