Convexity Seminar

---

Variational computation of convex hulls for fast distance queries

Speaker: Anh Truong, MIT CSAIL

Location: Warren Weaver Hall 1302

Date: Tuesday, April 28, 2026, 11 a.m.

Synopsis:

Convex hulls and their support function representation are fundamental tools in computational geometry, enabling fast distance queries and collision detection via specialized algorithms like Gilbert-Johnson-Keerthi (GJK). Evaluating or approximating support functions for general shapes, however, remains challenging: closed-form expressions only exist for simple primitives, and existing approaches for approximation require either expensive per-query optimization or regression from precomputed samples. 

In this talk, we will discuss a characterization of the support function of any compact set as the solution to a variational problem over sublinear functions. Our formulation allows support functions, encoding convex hulls, to be recovered directly from samples of the input geometry. We derive a tractable relaxation of this variational problem and prove its convergence to the true problem. This leads to a simple algorithm for parameterizing support functions which is compatible with many common geometric representations, including meshes, point clouds, parametric surfaces, curves, and level sets. Our approach produces tight convex hull approximations and provides fast queries for applications such as distance computation, continuous collision detection, and dynamic convex hull approximation.

This talk is based on joint work with Leticia Mattos Da Silva, Nestor Guillen, Mina Konaković Luković, and Justin Solomon.