Estimating the Convex Hull of the Image of a Set with Smooth Boundary: Error Bounds and Applications

Thomas Lew, Riccardo Bonalli, Lucas Janson, Marco Pavone

TL;DR

This paper introduces a new, significantly tighter error bound for estimating the convex hull of a set's image through a smooth function. By proving that the convex hull of an image remains smooth even when the image itself self-intersects, the authors enable more efficient and provably accurate reachability analysis and robust optimization in fields like robotics and control.

What Problem Does This Paper Address?

In many engineering tasks, we need to know the "range" of possible outcomes. For example, in robotics, we might want to know the set of all reachable states for a drone given uncertain mass and wind conditions. Mathematically, this often involves finding the convex hull of the image $f(\mathcal{X})$ of a set $\mathcal{X}$ under a non-linear map $f$.

While estimating a convex hull from samples seems straightforward, providing rigorous guarantees on the estimation error is difficult. Previous work often relied on "first-order" bounds that scale linearly with the sample density $\delta$. Furthermore, standard geometric tools often fail because even if the input set $\mathcal{X}$ is smooth, its image $f(\mathcal{X})$ can self-intersect, resulting in a "reach" of zero and breaking typical smoothness assumptions.

Figure 2: The boundary of images of sets with smooth boundary may not be smooth due to self-intersections.

Methods

The authors tackle this by assuming the map $f$ is a submersion (a map whose differential is surjective) and that the input set $\mathcal{X}$ is $r$-smooth. A set is $r$-smooth if a ball of radius $r$ can "roll freely" both inside and outside its boundary.

Figure 1(b): A ball of radius R rolls freely in X and in its complement, so X is R-smooth.

The core technical contribution is proving that while the boundary of the image $f(\mathcal{X})$ might be messy and self-intersecting, the boundary of its convex hull $H(f(\mathcal{X}))$ is guaranteed to be smooth. Leveraging this, they derive a second-order error bound for the Hausdorff distance between the true convex hull and the hull of $M$ samples. This bound is quadratic in the sample density $\delta$, meaning it vanishes much faster than previous linear bounds as you add more samples.

Datasets

The paper evaluates its theoretical findings through two primary numerical experiments:

  1. Synthetic Ellipsoid: A controlled setup where a 2D ball is mapped to an ellipsoid. This allows for direct comparison between empirical errors and the new theoretical bounds.
  2. Spacecraft Trajectory Planning: A practical application involving a spacecraft with uncertain mass and constant disturbances. The goal is to find a fuel-efficient trajectory that avoids obstacles for all possible parameter values within an uncertainty set.

Key Insights and Ideas

  • Convexity as a "Smoothing" Operator: The most elegant insight is that taking the convex hull effectively "heals" the self-intersections of the image boundary. This allows the use of differential geometry tools on the convex hull even when the underlying image is not a manifold.
  • Submersions are Sufficient: Unlike prior work that required $f$ to be a diffeomorphism (which forces the input and output dimensions to be the same), this work only requires $f$ to be a submersion. This is critical for practical applications like reachability analysis, where we often have many uncertain parameters (high-dimensional input) affecting a few state variables (lower-dimensional output).
  • Quadratic Convergence: By exploiting boundary smoothness, the authors achieve an $O(\delta^2)$ error bound. This is not just a theoretical curiosity; it means you need far fewer samples to achieve a desired level of guaranteed accuracy.

Key Results

  • Theorem 1.1: The main result provides a tight bound on the Hausdorff distance: $d_H(H(\mathcal{Y}), H(f(Z_\delta))) \le \frac{1}{2} (\frac{\bar{L}}{r} + \bar{H}) \delta^2$. This bound is $2\times$ tighter than the best previous bounds even for the simpler case where the set is already convex.
  • Empirical Validation: In numerical tests, the second-order bound was found to be an order of magnitude tighter than traditional first-order Lipschitz bounds, closely matching empirical performance.
  • Computational Efficiency: In the spacecraft planning example, the new bound allowed for a provably safe trajectory using only 100 samples. A naive bound would have required 3,300 samples to provide the same guarantee, making the optimization problem 125x slower to solve.

Limitations and Future Work

The authors acknowledge several areas for future exploration:

  • Sample Noise: The current theory assumes samples are perfectly on the boundary of $\mathcal{X}$. Real-world data often contains noise, and extending these bounds to noisy samples is a logical next step.
  • Non-Convex Reconstructions: While the convex hull is useful, some applications require reconstructing the actual non-convex set $f(\mathcal{X})$. The authors suggest their techniques might be adaptable to other estimators like tangential Delaunay complexes.
  • Weaker Regularity: Investigating whether these tight bounds hold under even weaker geometric conditions than $r$-smoothness remains an open question.

Summary updated

Abstract

We study the problem of estimating the convex hull of the image $f(X)\subset\mathbb{R}^n$ of a compact set $X\subset\mathbb{R}^m$ with smooth boundary through a smooth function $f:\mathbb{R}^m\to\mathbb{R}^n$. Assuming that $f$ is a submersion, we derive a new bound on the Hausdorff distance between the convex hull of $f(X)$ and the convex hull of the images $f(x_i)$ of $M$ sampled inputs $x_i$ on the boundary of $X$. When applied to the problem of geometric inference from a random sample, our results give error bounds that are tighter and more general than in previous work. We present applications to the problems of robust optimization, of reachability analysis of dynamical systems, and of robust trajectory optimization under bounded uncertainty.
BibTeX
@article{lew2025estimating,
  author = {Thomas Lew and Riccardo Bonalli and Lucas Janson and Marco Pavone},
  title = {{Estimating the Convex Hull of the Image of a Set with Smooth Boundary: Error Bounds and Applications}},
  journal = {Discret. Comput. Geom.},
  year = {2025},
  doi = {10.1007/s00454-024-00683-5},
}
Figure