🔢 mathematics

Finding the convex envelope of a boundary datum using random geometric graphs

This paper demonstrates that the unique solution to a specific equation defined on a random geometric graph converges to the convex envelope of a boundary datum as the number of points increases, provided the connection radius satisfies appropriate assumptions.

Original authors: Aurelia Deshayes, Nicolás Frevenza, Alfredo Miranda, Julio D. Rossi

Published 2026-03-24

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Aurelia Deshayes, Nicolás Frevenza, Alfredo Miranda, Julio D. Rossi

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Filling in the Blanks

Imagine you have a piece of paper with a circle drawn on it. Outside the circle, the paper is covered in a smooth, colorful landscape (like a hill or a valley). Inside the circle, the paper is blank.

Your goal is to fill in the blank circle. However, you have a strict rule: The shape you draw inside must be "convex."

In plain English, "convex" means it can't have any dips, valleys, or caves. If you stretch a rubber band around the edge of your drawing, the rubber band should never cut into the shape. It's like a smooth hill or a bowl that only curves one way.

The paper asks: How do we figure out exactly what the smooth, convex shape inside the circle should look like, just by looking at the edges?

The Problem: Too Many Points, Not Enough Rules

Mathematicians have known for a long time how to solve this if you have a perfect, continuous map. But in the real world (and in computer science), we rarely have a perfect map. Instead, we have a cloud of scattered dots (random points) inside the circle, and we know the values (heights) of the dots on the edge, but not the ones in the middle.

We want to guess the values of the middle dots so that the whole picture looks like a perfect, smooth, convex hill.

The Solution: A Game of "Random Walks"

The authors propose a clever way to solve this using a game played on a computer.

1. The Setup: The Neighborhood

Imagine the scattered dots are houses in a city. We draw a circle around every house. If another house is inside that circle, they are "neighbors."

The Rule: You can only walk to a neighbor if they are close to you.

2. The Game: The Controller

Now, imagine a player (let's call him "The Controller") standing on one of the houses inside the blank circle.

The Goal: The Controller wants to minimize the "cost" of the game. The cost is determined by the value of the house where the game eventually stops (which must be on the edge of the circle).
The Move: The Controller picks a neighbor. But here is the twist: The game doesn't just move to that neighbor. It flips a coin.
- Heads: The game moves to the neighbor the Controller picked.
- Tails: The game moves to the "mirror image" of that neighbor (the point directly opposite the Controller, at the same distance).
The Strategy: The Controller tries to pick a neighbor such that, no matter if it's Heads or Tails, the average value of the two possible next spots is as low as possible.

3. The Magic Connection

The paper proves that if you play this game over and over again with thousands of random dots, and the dots get closer and closer together (like zooming in on a high-resolution photo), the "best strategy" for the Controller reveals the perfect convex shape.

The game naturally "learns" to smooth out the bumps and fill in the blanks to create that perfect convex hill, without anyone explicitly telling it to be smooth.

The Technical "Secret Sauce"

To make this work, the authors had to solve a few tricky problems:

The "Mirror" Problem: In a random cloud of dots, if you pick a neighbor to the North, there probably isn't a perfect dot to the South to mirror it.
- The Fix: The authors invented a way to find the "closest available neighbor" to act as the mirror. They proved that as long as you have enough dots, this "approximate mirror" is good enough.
The "Super-Connectivity" Rule: The dots need to be close enough together so that every single dot has neighbors in every direction (North, South, East, West, and everywhere in between). If the dots are too far apart, the game gets stuck or the shape breaks. The authors calculated the exact math for how close the dots need to be for this to happen.

Why Does This Matter?

This isn't just a math puzzle. This method is a bridge between Random Graphs (networks of random points) and Partial Differential Equations (complex formulas used to model physics, finance, and engineering).

Real World Use: Imagine you have a 3D scan of a damaged car part. You know the shape of the edges, but the middle is missing. This algorithm could "fill in" the missing metal in a way that is physically realistic (convex) and mathematically perfect.
Machine Learning: This is related to "semi-supervised learning," where a computer tries to learn from a few labeled examples (the edge dots) to guess the labels of thousands of unlabeled data points (the middle dots).

Summary Analogy

Think of the Convex Envelope as a tight rubber sheet stretched over a set of pegs (the boundary data).

The Random Graph is a grid of tiny sensors scattered under the sheet.
The Game is a way for the sensors to talk to each other. Each sensor asks its neighbors, "What is the average height of the sheet above us?"
By playing this game, the sensors collectively figure out exactly how the rubber sheet should sag (or not sag) to create the smoothest, most convex shape possible.

The paper proves that if you have enough sensors and they are close enough together, this "game of chance" will always converge to the mathematically perfect answer.

1. Problem Statement

The paper addresses the problem of approximating the convex envelope of a given boundary datum $f$ inside a bounded, strictly convex domain $D \subset \mathbb{R}^d$ ( $d \geq 2$ ).

Mathematical Formulation: The convex envelope $u^*$ is defined as the supremum of all convex functions $v$ in $D$ such that $v \leq f$ on the boundary $\partial D$ .
PDE Characterization: The convex envelope is the unique viscosity solution to the Dirichlet problem:
$\begin{cases} -\lambda_1(D^2 u)(x) = 0 & x \in D \\ u(x) = f(x) & x \in \partial D \end{cases}$
where $\lambda_1(D^2 u)$ denotes the smallest eigenvalue of the Hessian matrix of $u$ . The condition $\lambda_1(D^2 u) \geq 0$ is equivalent to convexity.
Goal: To construct a discrete approximation of this solution using a Random Geometric Graph (RGG) generated by a cloud of random points, and to prove that the discrete solution converges to the continuous convex envelope as the number of points $n \to \infty$ .

2. Methodology

A. Random Geometric Graph Setup

Point Cloud: A sequence of independent and identically distributed (i.i.d.) uniform random points $X_1, \dots, X_n$ is sampled in $[0, 1]^d$ .
Graph Structure: A graph $G_n$ is formed where vertices are the sampled points. An edge exists between $x$ and $y$ if $|x - y| < r_n$ , where $r_n$ is a connection radius decreasing to 0 as $n \to \infty$ .
Regime: The authors work in the superconnectivity regime, defined by the condition:
$\frac{n r_n^d}{\log n} \to \infty \quad \text{as } n \to \infty.$
This ensures the graph is asymptotically connected with probability one. A stronger condition (Equation 1.6) is imposed for the convergence proofs: $\sqrt{n} r_n^{2d} / \log n \to \infty$ .

B. The Game-Theoretic Formulation

The authors interpret the discrete approximation as the value function of a one-player game played on the graph:

State Space: The game starts at a vertex $x_0$ inside the domain $D_n = C_n \cap D$ (where $C_n$ is the largest connected component).
Moves: At each step, the player (controller) chooses a neighbor $y$ from an annulus $N_x^{\delta_n}$ (points at distance roughly $r_n$ from $x$ ).
Randomness: The next state $x_{k+1}$ is chosen with probability $1/2$ to be either the chosen neighbor $y$ or its approximate reflection $y_x$ (the point in the graph closest to the geometric reflection $2x - y$ ).
Termination: The game ends when the token hits the boundary set $B_n = C_n \cap D^c$ . The player pays the cost $f(x_\tau)$ .
Objective: The player aims to minimize the expected payoff. The value function $u_n(x)$ is defined as the infimum of expected payoffs over all strategies.

C. Discrete Equation (Dynamic Programming Principle)

The game value $u_n$ satisfies the following discrete equation (Dynamic Programming Principle - DPP):
$u_n(x) = \min_{y \in N_x^{\delta_n}} \left( \frac{1}{2} u_n(y) + \frac{1}{2} u_n(y_x) \right), \quad x \in D_n$
with boundary condition $u_n(x) = f(x)$ for $x \in B_n$ .

Heuristic: The term $\frac{1}{2}u(y) + \frac{1}{2}u(y_x) - u(x)$ approximates the second-order directional derivative $\frac{1}{2} \langle D^2 u(x) z, z \rangle r_n^2$ . Minimizing over directions $z$ approximates the smallest eigenvalue $\lambda_1(D^2 u)$ .

3. Key Contributions

Probabilistic Control of Geometry:
The paper provides rigorous probabilistic estimates (using Talagrand's concentration inequalities and Bousquet's refinement) to ensure that for sufficiently large $n$ , the random graph has "neighbors in all directions" within the annulus $N_x^{\delta_n}$ . This is crucial for the discrete operator to approximate the continuous Hessian eigenvalue in every direction.
Well-Posedness of the Discrete Problem:
The authors prove that the DPP has a unique solution on the random graph. This is established via:
- A Comparison Principle for sub- and super-solutions.
- The Perron method to prove existence.
- Proof that the game terminates almost surely (finite hitting time).
Convergence to the Viscosity Solution:
The main theoretical result is the proof that the discrete game values, when extended to the continuous domain via nearest-neighbor interpolation, converge uniformly to the unique viscosity solution of the continuous convex envelope problem.

4. Main Results

Theorem 1 (Discrete Well-Posedness): Under the parameter conditions (specifically Eq. 1.6), the game value $u_n$ is the unique solution to the DPP almost surely for large $n$ .
Theorem 2 (Convergence): Let $u$ be the unique viscosity solution to the continuous problem (1.8). Let $\tilde{u}_n$ be the extension of the discrete game value to $D$ . Then, as $n \to \infty$ , $\tilde{u}_n \to u$ uniformly on $D$ with probability one.
Regularity: The proof relies on establishing that the discrete operator is a consistent approximation of the PDE operator (Lemma 6) and that the boundary data is attained continuously (Lemma 7).

5. Significance and Implications

Bridging PDEs and Graph Learning: The paper contributes to the growing field of understanding Partial Differential Equations (PDEs) as continuum limits of graph-based learning algorithms. It specifically addresses the convex envelope, a non-linear operator, which is more complex than standard Laplacian-based semi-supervised learning.
Game-Theoretic Interpretation: It provides a concrete stochastic game interpretation for the convex envelope, extending the "Tug-of-War" game framework (typically used for the $p$ -Laplacian) to the first eigenvalue of the Hessian.
Robustness to Randomness: The results demonstrate that even with a random, unstructured point cloud, one can recover a deterministic, smooth geometric object (the convex envelope) provided the sampling density and connection radius satisfy specific scaling laws.
Optimal Regime: The authors identify that the "superconnectivity" regime is necessary to ensure the graph is dense enough to approximate directional derivatives in all directions, a condition stricter than simple connectivity.

In summary, the paper successfully constructs a discrete, probabilistic algorithm for computing convex envelopes and provides a rigorous mathematical proof of its convergence to the continuous solution, leveraging tools from probability theory, graph theory, and the theory of viscosity solutions.