On an approximate minimax circle closest to a set of points |
| |
| Affiliation: | 1. Graduate School of Engineering, The University of Tokyo, Bunkyo-ku, Tokyo 113-8654, Japan;2. Research Center for Advanced Science and Technology, The University of Tokyo, Meguro-ku, Tokyo 153-8904, Japan;3. CIT UPC, UPC BarcelonaTech Technology Center, Carrer de Jordi Girona 31, Barcelona, Spain;4. Catalonia Institute for Energy Research (IREC), 08930 Sant Adrià del Besòs, Barcelona, Spain;1. Research Institute for Energy Conservation, National Institute of Advanced Industrial Science and Technology (AIST), Central 2, 1-1-1 Umezono, Tsukuba, Ibaraki 305-8568, Japan;2. Global Zero Emission Research Center, National Institute of Advanced Industrial Science and Technology (AIST), Central 2, 1-1-1 Umezono, Tsukuba, Ibaraki 305-8568, Japan |
| |
| Abstract: | We show how the Chebychev minimax criterion for finding a circle closest to a set of points can be approximated well by standard linear programming procedures.Scope and purposeProblems that arise in location theory and in the quality control of manufactured parts (drilled holes, shaped spheres) call for finding an annulus of minimum width that encompasses a set of points. For the two-dimensional case, this is equivalent to determining a closest “deviation” circle with center (x0,y0) and radius r0 such that the maximum radial distance of the points to the circumference of the deviation circle is minimized. The required annulus (narrowest ring) is formed by two circles, centered at (x0,y0), that inscribe and circumscribe the given set of points. We suggest that our linear-programming procedure be used to approximate this annulus as, unlike exact methods, it is stable, fast, and generalizes readily to higher-dimensional point sets. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
