×

zbMATH — the first resource for mathematics

The inverse moment problem for convex polytopes. (English) Zbl 1285.68198
Summary: We present a general and novel approach for the reconstruction of any convex \(d\)-dimensional polytope \(P\), assuming knowledge of finitely many of its integral moments. In particular, we show that the vertices of an \(N\)-vertex convex polytope in \(\mathbb R^{d}\) can be reconstructed from the knowledge of \(O(DN)\) axial moments (w.r.t. to an unknown polynomial measure of degree \(D\)), in \(d+1\) distinct directions in general position. Our approach is based on the collection of moment formulas due to Brion, Lawrence, Khovanskii-Pukhlikov, and Barvinok that arise in the discrete geometry of polytopes, combined with what is variously known as Prony’s method, or the Vandermonde factorization of finite rank Hankel matrices.

MSC:
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
52B05 Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.)
52A22 Random convex sets and integral geometry (aspects of convex geometry)
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Barvinok, A.I.: Calculation of exponential integrals. Zap. Nauč. Semin. POMI 192(5), 149-162, 175-176 (1991) · Zbl 0753.65018
[2] Barvinok, A. I., Exponential integrals and sums over convex polyhedra, Funkc. Anal. Prilozh., 26, 64-66, (1992)
[3] Barvinok, A.: Integer Points in Polyhedra. Zurich Lectures in Advanced Mathematics. European Mathematical Society (EMS), Zürich (2008) · Zbl 1154.52009
[4] Baldoni, V.; Berline, N.; Loera, J. A.; Köppe, M.; Vergne, M., How to integrate a polynomial over a simplex, Math. Comput., 80, 297-325, (2011) · Zbl 1216.68120
[5] Boley, D. L.; Luk, F. T.; Vandevoorde, D., Vandermonde factorization of a Hankel matrix, Hong Kong, 1997, Singapore · Zbl 0923.65009
[6] Basu, S., Pollack, R., Roy, M.-F.: Algorithms in Real Algebraic Geometry. Algorithms and Computation in Mathematics, vol. 10. Springer, Berlin (2003). Revised version of the first edition online at http://perso.univ-rennes1.fr/marie-francoise.roy/ · Zbl 1031.14028
[7] Beck, M., Robins, S.: Computing the Continuous Discretely: Integer-Point Enumeration in Polyhedra. Undergraduate Texts in Mathematics. Springer, New York (2007) · Zbl 1114.52013
[8] Brion, M.: Points entiers dans les polyèdres convexes. Ann. Sci. Éc. Norm. Super. 21(4), 653-663 (1988) · Zbl 0667.52011
[9] Cuyt, A.; Golub, G.; Milanfar, P.; Verdonk, B., Multidimensional integral inversion, with applications in shape reconstruction, SIAM J. Sci. Comput., 27, 1058-1070, (2005) · Zbl 1099.65128
[10] Davis, P. J., Triangle formulas in the complex plane, Math. Comput., 18, 569-577, (1964) · Zbl 0121.11801
[11] Demillo, R. A.; Lipton, R. T., A probabilistic remark on algebraic program testing, Inf. Process. Lett., 7, 192-195, (1978) · Zbl 0397.68011
[12] Elad, M.; Milanfar, P.; Golub, G. H., Shape from moments—an estimation theory perspective, IEEE Trans. Signal Process., 52, 1814-1829, (2004) · Zbl 1369.62145
[13] Golub, G. H.; Milanfar, P.; Varah, J., A stable numerical method for inverting shape from moments, SIAM J. Sci. Comput., 21, 1222-1243, (1999) · Zbl 0956.65030
[14] Grigoriev, D.; Pasechnik, D. V., Polynomial-time computing over quadratic maps. I. Sampling in real algebraic sets, Comput. Complex., 14, 20-52, (2005) · Zbl 1082.14065
[15] Lawrence, J., Polytope volume computation, Math. Comput., 57, 259-271, (1991) · Zbl 0734.52009
[16] Lenstra, A. K.; Lenstra, H. W.; Lovász, L., Factoring polynomials with rational coefficients, Math. Ann., 261, 515-534, (1982) · Zbl 0488.12001
[17] Pukhlikov, A. V.; Khovanskiĭ, A. G., The Riemann-Roch theorem for integrals and sums of quasipolynomials on virtual polytopes, Algebra Anal., 4, 188-216, (1992) · Zbl 0798.52010
[18] Schwartz, J. T., Fast probabilistic algorithms for verification of polynomial identities, J. Assoc. Comput. Mach., 27, 701-717, (1980) · Zbl 0452.68050
[19] Stanley, R.P.: Enumerative Combinatorics. Vol. 1. Cambridge Studies in Advanced Mathematics, vol. 49. Cambridge University Press, Cambridge (1997). With a foreword by Gian-Carlo Rota, Corrected reprint of the 1986 original · Zbl 0889.05001
[20] Zippel, R., Probabilistic algorithms for sparse polynomials, EUROSAM’79, Internat. Sympos., Marseille, 1979, Berlin
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.