From Circles to Convex Bodies: Approximating Curved Shapes by Polytopes

This survey article explores the universal $N^{-2/(d-1)}$ decay rate for approximating smooth convex bodies by polytopes with $N$ faces, tracing the concept from classical circle approximations to modern results on random polytopes, projection-based distances, and open problems regarding sharp constants and dimension dependence.

The Gist

Imagine you are trying to build a perfect model of a smooth, round apple using only flat, square pieces of cardboard. You have a limited budget: you can only use N pieces of cardboard (where N is the number of faces on your shape).

This paper, written by Steven Hoehner, is a guide to answering a very specific question: How close can you get to the perfect apple if you are forced to use a limited number of flat pieces?

Here is the breakdown of the paper's big ideas, translated into everyday language.

1. The "Flat vs. Curved" Problem

In the real world, most things we care about (balls, eggs, planets) are curved. But computers and math algorithms love straight lines and flat surfaces (polytopes). To make a computer understand a ball, we have to approximate it with a shape made of flat faces, like a soccer ball (which is actually a polyhedron made of hexagons and pentagons).

The paper asks: If I give you N flat faces, how much "error" (how much of the apple's shape will be missing or extra) will you have?

2. The Magic Number: Why $N$ Matters

The most striking discovery in this field is a "universal rule" for how fast the error shrinks as you add more cardboard pieces.

• In 2D (A Circle): If you approximate a circle with a polygon, the error shrinks very fast. If you double the number of sides, the error gets much smaller. Specifically, the error is proportional to $1/N^2$.
• In 3D (A Ball): If you approximate a ball with a polyhedron, the error shrinks slower.
• In General (d-Dimensions): The paper explains that the error always shrinks at a rate of $N^{-2/(d-1)}$.

The Analogy:
Imagine the surface of the ball is a giant pizza crust.

1. The Flatness: A flat piece of cardboard can't hug a curve perfectly. It leaves a tiny gap. The size of this gap depends on how "curvy" the pizza is. Mathematically, this gap is related to the square of the distance between the flat piece and the curve.
2. The Spreading: If you have $N$ pieces of cardboard to cover a 3D ball, you are spreading them over a 2D surface (the skin of the ball). The size of each piece is roughly $1/N$.
3. The Result: You multiply the "gap size" (which is squared) by the "number of pieces." This math dance always results in that specific exponent: $2/(d-1)$.

It's like saying: "No matter how you slice it, the difficulty of approximating a curve with flat pieces follows this exact recipe."

3. The "Random" Surprise

You might think you need a genius mathematician to carefully place every single flat piece to get the best result. You might think you need to calculate exactly where the curve is tightest.

The Surprise: The paper shows that randomness works almost as well as perfection.

If you throw $N$ points randomly onto the surface of the ball and connect them to make a shape, the resulting "random polytope" is almost as good as the best possible shape you could have designed by hand.

• The Catch: The random points shouldn't be thrown completely evenly. They should be thrown more often where the surface is curvier. But even with a simple random approach, you get incredibly close to the best possible result.

4. The "Stress Test": Why the Ball is the Hardest

The paper explains why the perfect sphere (the Euclidean ball) is the ultimate "boss level" for this problem.

• The Bumpy Rock: Imagine a rock with some flat spots and some very curvy spots. You can put your flat cardboard pieces on the flat spots easily. You only need to be careful on the curvy parts. You can "spend" your pieces where they are needed most.
• The Perfect Ball: A perfect ball has the same curve everywhere. There are no "easy" spots. You have to spread your $N$ pieces perfectly evenly. Because you can't cheat by focusing on the hard parts, the ball represents the worst-case scenario. If you can approximate a ball well, you can approximate almost anything else.

5. Looking at Shadows (The "Projection" Idea)

So far, we've talked about measuring the error by volume (how much space is missing) or surface area (how much skin is missing).

The paper introduces a new, clever way to measure error: Shadows.
Imagine shining a light on your apple and your cardboard model from every possible angle.

• If the shadow of the apple and the shadow of the cardboard model look the same from every angle, the shapes are very similar.
• This "Shadow Metric" is robust. It doesn't care if there is a tiny dent in one specific spot; it cares about the average look of the shape from all directions.
• The paper shows that for a ball, this shadow method gives the same "magic rate" of improvement as the volume method.

6. What's Still a Mystery? (Open Problems)

Even though we know the "rate" (the exponent), we don't know all the details. It's like knowing a car can go 100 mph, but not knowing exactly how much fuel it uses.

• The Constants: We know the formula is roughly $C \times N^{-2/(d-1)}$, but we don't know the exact value of C for high dimensions.
• The Gap: There is a gap between the best possible theoretical answer and the best answer we can actually calculate right now.
• The "Middle" Shapes: We know how to handle shapes with a fixed number of corners or a fixed number of flat faces. But what if we fix the number of "edges" or other middle parts? That's still a puzzle.

Summary

This paper is a tour guide through the math of approximating smooth curves with flat blocks.

1. The Rule: The error drops at a predictable speed based on the dimension of the space.
2. The Hero: The perfect sphere is the hardest shape to approximate because it's curvy everywhere.
3. The Hero's Tool: Randomly placing points is surprisingly effective.
4. The New Lens: Measuring shapes by their "shadows" gives a very stable way to compare them.

It's a beautiful example of how geometry, probability, and optimization all come together to solve a simple question: "How many flat pieces do I need to make a round thing?"

Technical Summary

Here is a detailed technical summary of the survey article "From Circles to Convex Bodies: Approximating Curved Shapes by Polytopes" by Steven Hoehner.

1. Problem Statement

The central problem addressed in the paper is the polytopal approximation of smooth, strictly convex bodies in $\mathbb{R}^d$. Specifically, the author investigates how well a convex body $K$ with a smooth ($C^2_+$) boundary can be approximated by a polytope $P$ with a limited number of faces (complexity $N$).

The core question is: What is the asymptotic rate of decay of the approximation error as $N \to \infty$?
The paper explores this across different "metrics" (ways of measuring error), such as:

• Hausdorff distance: Worst-case directional error.
• Symmetric difference: Volume difference ($\text{vol}(K \triangle P)$).
• Surface area deviation: Boundary difference.
• Intrinsic volume metrics: Average error in projections (shadows).

The survey aims to explain the emergence of a "universal exponent" governing these errors and to compare deterministic best-approximation strategies with probabilistic (random) constructions.

2. Methodology and Theoretical Framework

The paper synthesizes geometry, combinatorics, and probability theory to analyze approximation errors. The methodology relies on three main axes:

1. Metric Axis: Analyzing different error functionals (Hausdorff, symmetric difference, intrinsic volumes).
2. Positioning Axis: Considering whether the polytope is inscribed ($P \subset K$), circumscribed ($P \supset K$), or in an arbitrary position.
3. Complexity Axis: Constraining the polytope by the number of vertices, facets, or intermediate faces.

Key Analytical Tools:

• Local Geometry (Spherical Caps): The paper uses a heuristic computation on the unit sphere to derive the error scaling. It models the local boundary of a convex body as a paraboloid (or spherical cap). The volume of a cap of height $h$ scales as $h^{(d+1)/2}$, while the base diameter scales as $h^{1/2}$.
• Curvature Integrals: The leading constants in asymptotic formulas are shown to depend on the affine surface area and other curvature-weighted integrals (e.g., $\int_{\partial K} \kappa(x)^\alpha d\mu$).
• Metric Entropy: For Hausdorff approximation, the paper references bounds derived from covering numbers (Dudley, Bronshtein, Ivanov).
• Random Polytopes: The paper analyzes the expected error of polytopes formed by the convex hull of $N$ random points sampled from the boundary, comparing this to the theoretical minimum (best approximation).

3. Key Contributions and Results

A. The Universal Exponent $2/(d-1)$

The most significant finding is the derivation of the universal decay rate for smooth, strictly convex bodies:
$$\text{Error} \asymp N^{-\frac{2}{d-1}}$$

• Derivation: This exponent arises from the product of two factors:
  1. Quadratic Deviation: A smooth boundary deviates from a tangent hyperplane quadratically (parabolic law), contributing a factor of $h^2$ to the local error.
  2. Dimensional Partitioning: $N$ faces partition a $(d-1)$-dimensional boundary into patches of diameter $\rho \asymp N^{-1/(d-1)}$.
  3. Synthesis: The local volume error per patch scales as $\rho^{d+1} \asymp (N^{-1/(d-1)})^{d+1} = N^{-(d+1)/(d-1)}$. Summing over $N$ patches yields $N \cdot N^{-(d+1)/(d-1)} = N^{-2/(d-1)}$.

B. Sharp Asymptotics and Curvature Dependence

The paper details precise asymptotic formulas where the error is not just $O(N^{-2/(d-1)})$, but converges to a specific constant determined by the body's geometry:

• Symmetric Difference (Inscribed/Circumscribed):
  $$\inf_{P} \text{vol}(K \triangle P) \sim C_d \cdot (\text{Affine Surface Area}(K))^{\frac{d+1}{d-1}} \cdot N^{-\frac{2}{d-1}}$$
  The constant involves Delone triangulation numbers ($\text{del}_{d-1}$) or Voronoi tiling numbers ($\text{div}_{d-1}$), which represent optimal local tilings of the boundary.
• Arbitrary Position: When containment is dropped, the error constant improves significantly (by a factor of dimension) due to the possibility of "overshooting" and "undershooting" canceling out. This introduces Laguerre-Delone and Laguerre-Voronoi constants ($\text{ldel}, \text{ldiv}$).

C. Random Polytopes are Near-Optimal

A major contribution is the demonstration that random polytopes (convex hulls of random boundary points) achieve the same asymptotic order as the best possible deterministic polytopes.

• Optimal Sampling: The error is minimized when points are sampled with a density proportional to $\kappa(x)^{1/(d+1)}$ (where $\kappa$ is Gauss-Kronecker curvature).
• Result: With optimal sampling, the expected error of a random polytope matches the sharp constant of the best inscribed polytope asymptotically.

D. The Euclidean Ball as a Benchmark

The paper establishes the Euclidean ball ($B^d_2$) as the "hardest" case for approximation.

• Macbeath's Theorem: Among bodies of fixed volume, ellipsoids (and thus the ball) maximize the approximation error for inscribed polytopes.
• Reasoning: The ball has constant curvature, preventing the optimizer from concentrating faces in high-curvature regions. This forces a uniform distribution of faces, revealing the worst-case dimension dependence of the constants.

E. Intrinsic Volume Metrics (Projection-Based Distances)

The survey introduces a newer perspective: comparing bodies by their shadows (projections).

• Intrinsic Volumes ($V_j$): These generalize volume ($V_d$), surface area ($V_{d-1}$), and mean width ($V_1$).
• Simultaneous Optimality: For the Euclidean ball, there exists a single polytope that is asymptotically optimal for all intrinsic volume metrics simultaneously. This is unique to bodies with constant curvature.

4. Significance and Open Problems

Significance:

• Unification: The paper unifies disparate results in convex geometry, showing that volume, surface area, and Hausdorff errors all share the same fundamental scaling law driven by curvature and dimension.
• Algorithmic Implications: It validates the use of random sampling (Monte Carlo methods) for generating high-quality approximations in high-dimensional optimization and stochastic geometry, as they are nearly as good as computationally expensive deterministic constructions.
• Geometric Insight: It highlights the deep connection between local curvature, global approximation error, and combinatorial tiling constants (Delone/Voronoi).

Open Problems Highlighted:

1. Sharp Constants: Determining the exact values of dimension-dependent constants (like $\text{ldel}_{d-1}$) for high dimensions.
2. The "ldel Gap": Closing the gap between the known upper and lower bounds for the Laguerre-Delone constant in arbitrary position approximation.
3. Projection Metrics: Developing sharp asymptotic theories for intrinsic volume metrics $\delta_j$ in arbitrary positions.
4. Intermediate Faces: Extending sharp results to polytopes constrained by the number of $k$-faces (where $1 < k < d-1$).
5. Universality of the Ball: Determining if the Euclidean ball remains the "hardest" body to approximate for all metrics, particularly in circumscribed or arbitrary position settings.

Conclusion

Steven Hoehner's survey provides a comprehensive roadmap of polytopal approximation, moving from the classical 2D case to high-dimensional phenomena. It establishes that while the rate of convergence ($N^{-2/(d-1)}$) is universal for smooth bodies, the constants are deeply tied to the body's curvature and the combinatorial geometry of optimal tilings. The work underscores the power of probabilistic methods in geometry and identifies the Euclidean ball as the critical test case for understanding the limits of approximation in high dimensions.