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

Introduction

In fields such as robotics and control engineering, determining the "reachable set" of a system is a fundamental challenge. For a drone or spacecraft, the reachable set represents all possible future states given uncertain initial conditions or parameters. Mathematically, this involves finding the image $f(\mathcal{X})$ of a set $\mathcal{X}$ under a smooth mapping function $f$.

Computing this set directly is often computationally intractable. A common practical approach is to sample points $x_i$ from the input set $\mathcal{X}$, compute their images $f(x_i)$, and construct their convex hull—the smallest convex shape containing the sampled points. While effective in practice, providing rigorous theoretical guarantees (error bounds) on how closely this estimate approximates the true convex hull has been difficult. Previous bounds were often too conservative or relied on the assumption that the output set was "well-behaved" (e.g., having a positive reach), an assumption that fails when the mapping causes the set to self-intersect.

Theoretical Framework: Smoothness and Submersions

This research introduces a framework based on differential geometry that shifts the focus from the potentially complex geometry of the output set to the properties of the input set and the mapping function.

$r$-Smoothness

The authors assume the input set $\mathcal{X}$ is $r$-smooth. Geometrically, this means that a ball of radius $r$ can roll freely along both the interior and exterior of the set's boundary without being obstructed by sharp corners or narrow passages.

Illustration of r-smoothness where a ball of radius R rolls along the boundary of set X.

The Concept of Reach

Traditional geometric proofs often rely on the "reach" of a set—the distance from the set to its medial axis. When a mapping $f$ causes a set to fold or self-intersect, the reach of the resulting image $f(\mathcal{X})$ can drop to zero, rendering standard bounds inapplicable.

The reach of a set X, defined by the distance to its medial axis Med(X).

Submersion Mappings

The study focuses on "submersions"—smooth maps that do not "collapse" dimensions in a way that introduces sharp corners into the convex hull. This class of functions is sufficiently broad to encompass many physical and dynamical systems.

The Quadratic Error Bound

The core contribution of this work is the proof of a quadratic error bound. The authors demonstrate that the Hausdorff distance $d_H$ (a metric for shape similarity) between the true convex hull and the sampled estimate is $O(\delta^2)$, where $\delta$ represents the maximum distance between samples on the boundary of $\mathcal{X}$.

Specifically, Theorem 1.1 provides the explicit formula: $$d_H \leq \frac{1}{2} \left(\frac{\bar{L}}{r} + \bar{H}\right) \delta^2$$ where $r$ is the smoothness of the input set, and $\bar{L}, \bar{H}$ are Lipschitz constants related to the function and its derivative. This represents a significant improvement over standard linear "Lipschitz" bounds ($O(\delta)$). In practical terms, doubling the sampling density results in a fourfold reduction in error.

Key Insights

  • Geometric Healing: Even if the image $f(\mathcal{X})$ is non-convex or self-intersecting, the boundary of its convex hull remains a smooth manifold. This allows the application of differential geometry tools that would otherwise be invalid.
  • Boundary Importance: The estimation error is primarily determined by the sampling density on the boundary of the input set, rather than its interior.
  • Efficiency: The tighter bound justifies using significantly fewer samples to achieve required safety and precision guarantees.

Applications and Results

The theoretical findings were validated through numerical simulations:

  • Spacecraft Planning: In a simulation of a spacecraft with uncertain payload mass and disturbances, the new bound showed that 100 samples provided the same precision guarantee that would have required 3,300 samples under older, more conservative bounds.
  • Computational Performance: The increased efficiency allowed robust trajectory optimization to be performed in 200ms, a massive improvement over the 25 seconds required by previous methods.

Limitations and Future Work

The current theory assumes noise-free samples exactly on the boundary of $\mathcal{X}$ and perfect knowledge of the mapping $f$. Future research may address the impact of noisy data and extend the framework to non-submersion mappings or non-convex approximations like Delaunay complexes.

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 tighter and more general error bounds than the state of the art. 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