Certified Efficient Global Roundness Evaluation
- PDF / 1,391,791 Bytes
- 22 Pages / 439.37 x 666.142 pts Page_size
- 64 Downloads / 155 Views
Certified Efficient Global Roundness Evaluation Frank Schöpfer1 · Alexey Chernov1 Received: 27 September 2019 / Accepted: 19 May 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract We propose and analyze a global search algorithm for the computation of the minimum zone sphericity (circularity) error of a given set. The formulation is valid in any dimension and covers both finite sets of data points as well as infinite sets like polygonal chains or triangulations of surfaces. We derive theoretical estimates for the cost to reach a desired accuracy, and validate the performance of the algorithm with various numerical experiments. Keywords Circularity error · Global optimization · Minimum zone · Minimum width annulus · Roundness evaluation · Sphericity error Mathematics Subject Classification 90C26 · 90C90
1 Introduction In metrology applications (e.g., quality and wearing assessment of industrial rollers) an object is considered round enough, if all measurement points on its surface lie between two spheres (cirlces) around a common center, such that the difference of their radii is smaller than some prescribed tolerance. This complies with ANSI Y14.5 and ISO 1101 standards [1,2]. The roundness of any set S ⊂ Rd may be defined as the smallest possible difference of radii for a suitable center. A precise definition of the corresponding optimization problem will be given in the next section.
Communicated by Horst Martini.
B
Frank Schöpfer [email protected] Alexey Chernov [email protected]
1
Institut für Mathematik, Carl von Ossietzky Universität Oldenburg, 26111 Oldenburg, Germany
123
Journal of Optimization Theory and Applications
The problem of computing the roundness is also known as the problem of computing the minimum radial separation, the minimum zone sphericity (circularity) error, or the minimum-width shell (annulus). Computational geometry algorithms that compute exact solutions for finite sets S with n points are mostly based on Voronoi diagrams [3–7]. In the plane, they have worst case O(n 2 )-time behavior, but there are also subquadratic O(n 3/2+β )-time algorithms [8] for arbitrarily small β > 0. Under special assumptions on the set S even (expected) linear time can be achieved with linear programming techniques [9], see also [10]. In [11] it was noted that the general complexity to compute an exact solution in any dimension d is O(n floor(d/2)+1 ). No estimates on the constants involved are given, but they generally depend exponentially on d. Indeed, as pointed out in [12], even in the plane, algorithms, that compute exact global solutions, are rather inefficient for large n. Therefore, it is of practical interest to develop algorithms, that efficiently compute approximate global minimizers of the roundness problem for any prescribed accuracy ε > 0, especially, if the roundness of many manufactured objects has to be evaluated. Since the roundness problem may have several local minima, standard local optimization methods cannot guarantee to find global mi
Data Loading...
