Abstract
This paper presents a novel method for the exact reconstruction of $d$-dimensional convex polytopes from a finite set of their integral moments. By leveraging the BBaKLP formulas from discrete geometry and Prony’s method from signal processing, the authors demonstrate that the vertices of a polytope can be uniquely identified even when the internal density is an unknown polynomial. The algorithm operates in polynomial time for rational polytopes and offers a significant advancement over traditional numerical or dimensionally restricted approaches.
Introduction
The "Inverse Moment Problem" is a classic challenge in mathematical imaging and geophysics: can the geometry of an object be recovered from its moments? Moments—weighted averages such as mass, center of gravity, and moments of inertia—provide a global description of a shape. Recovering the specific coordinates of an object's boundaries from these global descriptors is essential for applications ranging from computed tomography (CT) to gravimetry and signal processing.
Historically, solving this problem in dimensions higher than two has proven difficult. Existing methodologies often rely on voxel-based approximations, are restricted to uniform densities, or require "slicing" 3D objects into 2D layers. This paper introduces a general, exact solution for convex polytopes in arbitrary dimensions, accommodating non-uniform, polynomial densities.
Methodology
The proposed method eschews traditional numerical integration (quadrature) in favor of a discrete geometric framework. The reconstruction process is built upon three mathematical pillars:
1. The BBaKLP Formulas
Named after Brion, Barvinok, Khovanskii, Lawrence, and Pukhlikov, these identities are central to the approach. They provide an exact relationship between the integral of a function over a polytope and a sum evaluated at its vertices. This transformation effectively converts a continuous "global" problem (moments) into a discrete "local" problem (vertex coordinates).
2. Hankel Matrices and Prony’s Method
The algorithm organizes the observed moments into a square Hankel matrix. In the context of signal processing, Prony’s method is typically used to extract the frequencies of a signal from discrete samples. The authors adapt this technique to find "spatial frequencies," which correspond to the projections of the polytope’s vertices onto a specific axis.
3. Vandermonde Factorization and Root Finding
By analyzing the kernel (null space) of the Hankel matrix, the authors construct a univariate polynomial. The roots of this polynomial represent the coordinates of the vertices projected onto a chosen direction. To reconstruct the full $d$-dimensional coordinates, the algorithm takes projections in $d+1$ directions in "general position" and correlates the results to assemble the vertex set.
Key Insights
The research yields several significant theoretical insights:
- Automatic Vertex Discovery: The number of vertices ($N$) does not need to be known a priori. The algorithm determines $N$ by calculating the rank of the Hankel matrix.
- Robustness to Unknown Density: A major breakthrough is the method's ability to handle non-uniform mass distributions. If the density is a polynomial, the vertices can be recovered even if the specific coefficients of that polynomial are unknown.
- Linear Recurrence Relations: The core realization is that the moments of a polytope satisfy a linear recurrence. This allows the application of linear algebra tools to extract geometric data from continuous integrals.
- Frugality and Efficiency: Reconstructing an $N$-vertex polytope in $d$ dimensions requires only $O(DN)$ moments (where $D$ is the degree of the density polynomial). This is significantly more efficient than grid-based or sampling-heavy reconstruction methods.
Results and Complexity
The authors provide rigorous proofs for the uniqueness and complexity of the reconstruction. For rational polytopes—those with vertices at rational coordinates—the reconstruction can be achieved in polynomial time using the LLL (Lenstra–Lenstra–Lovász) algorithm for root finding. Unlike approximation methods that produce voxelated outputs, this algorithm retrieves the exact vertex coordinates.
Limitations and Future Directions
While the method is a significant step forward, it currently assumes the polytope is convex. Extending the framework to non-convex shapes or objects with curved boundaries remains an open challenge. Additionally, while the authors propose a "univariate representation" to mitigate numerical errors, Hankel-based methods are inherently sensitive to noise. Future work will likely focus on increasing the robustness of the algorithm for real-world, noisy datasets (such as experimental CT scans) and developing deterministic methods for selecting optimal projection directions.
Summary updated