×

Consistency method for measurements of the support function of a convex body in the metric of \(L_\infty\). (English. Russian original) Zbl 1386.52002

Mosc. Univ. Math. Bull. 72, No. 4, 161-164 (2017); translation from Vestn. Mosk. Univ., Ser. I 72, No. 4, 27-31 (2017).
Summary: A new algorithm is proposed for estimation of convex body support function measurements in \(L_\infty\) metric, which allows us to obtain the solution in quadratic time (with respect to the number of measurements) not using linear programming. The rate of convergence is proved to be stable for quite weak conditions on input data. This fact makes the algorithm robust for a wider class of problems than it was previously. The implemented algorithm is stable and predictable unlike other existing support function estimation algorithms. Implementation details and testing results are presented.

MSC:

52A20 Convex sets in \(n\) dimensions (including convex hypersurfaces)
90C05 Linear programming
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)

Software:

Ipopt
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] J. L. Prince and A. S. Willsky, “Reconstructing Convex Sets from Support Line Measurements,” IEEE Trans. Pattern Anal. and Machine Intel. 12 (4), 377 (1990). · doi:10.1109/34.50623
[2] A. S. Lele, S. R. Kulkarni, and A. S. Willsky, “Convex-Polygon Estimation from Support-Line Measurements and Applications to Target Reconstruction from Laser-Radar Data,” J. Opt. Soc. Amer. A. 9 (10), 1693 (1992). · doi:10.1364/JOSAA.9.001693
[3] J. Gregor and F. R. Rannou, “Least-Squares Framework for Projection {MRI} Reconstruction,” Proc. SPIE. 4322, 888 (2001). · doi:10.1117/12.431168
[4] J. Gregor and F. R. Rannou, “Three-Dimensional Support Function Estimation and Application for Projection Magnetic Resonance Imaging,” Int. J. Imaging Systems and Technol. 12 (1), 43 (2002). · doi:10.1002/ima.10007
[5] I. A. Palachev, “The Method of Exclusion of Redundant Restrictions in the Problem of Body Reconstruction from its Support Function Measurements,” Vychisl. Metody Program. 16, 348 (2015).
[6] R. J. Gardner and M. Kiderlen, “A New Algorithm for 3D Reconstruction from Support Functions,” IEEE Trans. Pattern Anal. and Machine Intel. 31 (3), 556 (2009). · doi:10.1109/TPAMI.2008.190
[7] A. Wachter and L. T. Biegler, “On the Implementation of a Primal-Dual Interior Point Filter Line Search Algorithm for Large-Scale Nonlinear Programming,” Math. Program. 106 (1), 25 (2006). · Zbl 1134.90542 · doi:10.1007/s10107-004-0559-y
[8] A. Wachter and L. T. Biegler, “Line Search Filter Methods for Nonlinear Programming: Local Convergence,” SIAM J. Optim. 16 (1), 32 (2005). · Zbl 1115.90056 · doi:10.1137/S1052623403426544
[9] A. Wachter and L. T. Biegler, “Line Search Filter Methods for Nonlinear Programming: Motivation and Global Convergence,” SIAM J. Optim. 16 (1), 1 (2005). · Zbl 1114.90128 · doi:10.1137/S1052623403426556
[10] O. Devillers, “The Delaunay Hierarchy,” Int. J. Foundations of Computer Science. 13, 163 (2002). · Zbl 1066.68138 · doi:10.1142/S0129054102001035
[11] D. Attali and J.-D. Boissonnat, “A Linear Bound on the Complexity of the Delaunay Triangulation of Points on Polyhedral Surfaces,” Discr. and Comp. Geom. 31 (3), 369 (2004). · Zbl 1063.68100 · doi:10.1007/s00454-003-2870-4
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.