Geoscience Reference
In-Depth Information
In the geometric interpretation, the result means that the annulus of minimal
width covering all points has two points on its inner circumference and two points
on its outer circumference (Rivlin
1979
).
It also shows that the center point of a minimax circle is either a vertex of the
(nearest neighbor) Voronoi diagram or of the farthest neighbor Voronoi diagram
or lies at an intersection point of both diagrams (Le and Lee
1991
; García-López
et al.
1998
).
For the unweighted problem, Ebara et al. (
1989
) use this result and present
an enumeration algorithm with runtime in O(n
2
). If the points in V are given in
an angular order, García-López et al. (
1998
) present an algorithm which runs in
O(n log n) and which can even be improved to O(n) if the points in V are the vertices
of a convex polygon. This is in particular helpful for solving the out-of-roundness
problem (see Sect.
7.4.1
), since the measurements are taken along the manufactured
part in angular order in this case. A gradient search heuristic is provided in Drezner
et al. (
2002
) and global optimization methods were used in Drezner and Drezner
(
2007
) who use the Big-Triangle-Small-Triangle method (based on Drezner and
Suzuki
2004
) for its solution. Randomized and approximation algorithms are also
possible, see Agarwal et al. (
2004
,
1999
).
More references on the computation of Euclidean minmax circles can be found
in García-López et al. (
1998
) and in Brimberg et al. (
2009a
).
7.4.4.3
Location of a Minmax Circle with Rectangular Distance
Gluchshenko (
2008
) and Gluchshenko et al. (
2009
) consider the minimal annulus
problem for the rectangular distance. This means, the circle to be located is a
diamond, and the distances from the given points to the circle are measured in the
rectangular norm. The following is an important result.
Theorem 7.13 (FDS for the Rectangular Minmax Circle)
(Gluchshenko et al.
2009
) There exists a minmax circle whose center point is a center point of a smallest
enclosing square.
This means the set of all center points of smallest enclosing squares (which can
be determined easily) is an FDS. Based on this, Gluchshenko et al. (
2009
)develop
an optimal O(n log n) algorithm for finding a minmax circle with respect to the
rectangular norm.
Recently, the problem in which the annulus may also be rotated has been
considered in Mukherjee et al. (
2013
)whereanO(n
2
log n) algorithm has been
proposed.
