×

Fitting enclosing cylinders to data in \(\mathbb R^n\). (English) Zbl 1109.65059

The paper is devoted to the development of a simple iterative algorithm for finding a stationary point of the (nonconvex) problem of finding the smallest enclosing \((n-d)\)-cylinder to discrete data in \(\mathbb R^n\), that is a cylinder whose axis is a \(d\)-dimensional linear manifold. The algorithm considered in the paper is intended to find the smallest enclosing (usual) cylinder, when \(n=3\) and \(d=1\). It is based on the solution of a sequence of second order cone programming problems (SOCPs) for a class of problems which includes finding enclosing cylinders in \(\mathbb R^3\).
These are problems which involve the minimization of a linear objective function over the intersection of an affine set and the product of second order (quadratic) cones. The algorithm realization uses standard, readily available software. As it is stated in the paper, it converge to a stationary point of the problem, and although the rate of convergence is unpredictable, evidence for the smallest enclosing cylinder problem suggests that it is satisfactory. Much depends on the accuracy required, although this is less important in the context of genuinely error contaminated data. A starting approximation is suggested which might be favorable for finding the global solution to this non-convex problem, although guaranteeing a global solution remains a live issue.

MSC:

65K05 Numerical mathematical programming methods
65D10 Numerical smoothing, curve fitting
90C26 Nonconvex programming, global optimization
65D18 Numerical aspects of computer graphics, image analysis, and computational geometry

Software:

Mosek; SOCP; SDPT3
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Agarwal, P.K., Aronov, B., Sharir, M.: Line traversals of balls and smallest enclosing cylinders in three dimensions. Discrete Comput. Geom. 21, 373–388 (1999) · Zbl 0922.68127 · doi:10.1007/PL00009427
[2] Al-Subaihi, I., Watson, G.A.: The use of the l 1 and l norms in parametric fitting of curves and surfaces to data. Appl. Numer. Anal. Comput. Math. 1, 363–376 (2004) · Zbl 1071.65012 · doi:10.1002/anac.200410004
[3] Brenberg, R., Theobald, T.: Algebraic methods for computing smallest enclosing and circumscribing cylinders of simplices. Appl. Algebra Eng. Commun. Comput. 14, 439–460 (2004) · Zbl 1053.52002 · doi:10.1007/s00200-003-0146-0
[4] Brandenberg, R., Theobald, T.: Radii minimal projections of polytopes and constrained optimization of symmetric polynomials. Adv. Geom. 6, 71–83 (2006) · Zbl 1108.52010 · doi:10.1515/ADVGEOM.2006.005
[5] Chan, T.M.: Approximating the diameter, width, smallest enclosing cylinder, and minimum width annulus. Int. J. Comput. Geom. Appl. 12, 67–85 (2002) · Zbl 1152.68659 · doi:10.1142/S0218195902000748
[6] Gritzmann, P., Klee, V.: Computational complexity of inner and outer j-radii of polytopes in finite-dimensional normed spaces. Math. Program. 59(A), 163–213 (1993) · Zbl 0784.90076 · doi:10.1007/BF01581243
[7] Lobo, M.S., Vandenberghe, L., Boyd, S.: SOCP: Software for second-order cone programming. User’s guide. Stanford report (1997)
[8] The MOSEK optimization software. http://www.mosek.com
[9] Nelder, J.A., Mead, R.: A simplex method for function minimization. Comput. J. 7, 308–313 (1965) · Zbl 0229.65053
[10] Press, W., Teukolsky, S., Wetterling, W., Flannery, B.: Numerical Recipes in C. Cambridge University Press, Cambridge (1988) · Zbl 0661.65001
[11] Schömar, E., Sellen, J., Teichmann, M., Yap, C.: Smallest enclosing cylinders. Algorithmica 27, 170–186 (2000) · Zbl 0949.68158 · doi:10.1007/s004530010011
[12] SeDuMi: Advanced Optimization Laboratory. http://sedumi.mcmaster.ca/ (McMaster University)
[13] Suresh, K., Voelcker, H.B.: New challenges in dimensional metrology: a case study based on ”size”. Manuf. Rev. 7, 292–303 (1994)
[14] Toh, K.C., Tutuncu, R.H., Todd, M.J.: SDPT3. http://www.math.nus.edu.sg/\(\sim\)mattohkc/sdpt3.html
[15] Watson, G.A.: Approximation Theory and Numerical Methods. Wiley, Chichester (1980) · Zbl 0442.65005
[16] Watson, G.A.: The solution of generalized least squares problems. In: Schempp, W., Zeller, K. (eds.) Multivariate Approximation Theory ISNM 75, vol. 3, pp. 388–400. Birkhäuser Verlag, Basel (1985) · Zbl 0579.41027
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.