Geoscience Reference
In-Depth Information
Location of line segments has been considered in Imai et al. (
1992
), Agarwal
et al. (
1993
), Efrat and Sharir (
1996
) for the Euclidean minmax problem, and in
Schöbel (
1997
) for the minsum problem with vertical distances. In both the cases it
is possible to determine a finite dominating set; the latter case can be transformed to
a restricted line location problem.
Recently, locating line segments received new interest within the following
problem: A line segment and a point facility are to be located simultaneously. In
this setting, the line segment can be used to speed up traveling in the plane in which
a new point facility should be built. The problem has been treated in the plane,
using rectangular distances in Espejo and Rodríguez-Chía (
2011
,
2012
)wherea
characterization of optimal solutions was used to derive an algorithm. This could be
improved in Díaz-Bánez et al. (
2013
)toanO(n
3
) approach. These approaches are
based on a finite dominating set which can be obtained by reduction of the location
problem to a finite number of simpler optimization problems.
7.5.1.1
The Widest Empty 1-Corner Corridor in the Plane
An
empty corridor
in the plane is an open region bounded by two parallel polygonal
chains that does not contain any of the existing points V
Df
v
1
;:::;v
n
g
,andthat
partitions the existing points into two non-empty parts. This can be interpreted as an
obnoxious dimensional location problem: locate a polygonal chain maximizing the
minimum distance to the existing facilities. Empty corridors have been of interest in
computational geometry (see e.g., Janardan and Preparata
1996
). An empty corridor
is called a
1-corner empty corridor
if each of the two bounding polygonal chains has
exactly one corner point. The problem in which the angle at the corner point is given
and fixed has been studied in Cheng (
1996
). Recently, Díaz-Bánez et al. (
2006b
)
considered the problem of locating a widest 1-corner corridor using techniques of
facility location: they were able to derive a finite dominating set consisting of locally
widest 1-corner corridors among which a solution may be chosen. Their approach
needs O(n
4
log n) time. It was further improved to O(n
3
log
2
n) time in Das et al.
(
2009
).
7.5.1.2
Two-Dimensional Facilities
Covering problems
are the most common problems in which the location of full-
dimensional facilities is considered. There exist, e.g., many papers about covering
points by a circle (i.e., locating one point x such that all given points are in a given
threshold distance from x), by a set of circles, or even by a set of aligned circles
(occurring when the center points of the circles to be located are forced to lie on
a common straight line), or circles satisfying other restrictions. Covering problems
are not reviewed here, we refer to Plastria (
2001
) or to Chap.
5
.
However, also the location of a two-dimensional facility X such that the minsum
or minmax objective function is minimized, has been considered in the literature. If
