Geometric Radius Bounding and Sandwiching

21 concepts5 papers1 proposal

When dealing with complex geometric spaces—whether they represent high-dimensional datasets, optimization landscapes, or arbitrary spatial shapes—working directly with exact boundaries is often computationally intractable or mathematically elusive. To bypass this complexity, a powerful strategy across geometry, machine learning, and optimization is to "sandwich" or bound these intricate sets using simpler, well-understood geometric primitives like spheres, ellipsoids, or universal covering shapes.

The core intuition behind this research direction is simple: by finding tight upper and lower bounds on the radius or diameter of an enclosing primitive, we can drastically narrow the "uncertainty gap" of the underlying problem. This geometric tightening transforms intractable combinatorial and non-convex problems into highly efficient, solvable formulations.

Narrowing the Uncertainty Gap in Set Coverings

Consider a classic problem in combinatorial geometry: what is the minimum diameter $d_k$ required for $k$ subsets to completely cover any arbitrary planar set of unit diameter? This is a generalization of the Borsuk problem. Because the target set can take an infinite variety of shapes, finding the exact value of $d_k$ is notoriously difficult.

To establish a reliable upper bound on $d_k$, researchers shift their focus from the infinite space of arbitrary shapes to a single, well-defined geometry known as a universal covering set. A universal covering set (such as a regular hexagon with trimmed corners) is a fixed shape that is mathematically proven to be capable of covering any planar set of unit diameter.

[ Arbitrary Unit-Diameter Set ] 
           ⊆  [ Universal Covering Set (e.g., Trimmed Hexagon) ]
                       │
                       ▼ (Optimized Geometric Partitioning)
           [ n Smaller Sub-regions ] ──► Max Diameter = Proven Upper Bound

As shown by Tolmachev et al. (2021), if you can divide this universal covering set into $n$ smaller sub-regions, the diameter of the largest sub-region in your partition serves as a guaranteed upper bound for the $n$-set covering problem. By designing highly optimized geometric partitions, the authors successfully narrowed the discrepancy between the theoretical lower and upper bounds by up to 48% for various configurations. To scale this approach, Tolmachev et al. (2022) introduced sub-optimal partitioning algorithms that systematically refine these diameter estimates for higher dimensions and larger numbers of subsets, demonstrating how localized geometric partitioning tames global structural uncertainty.

Pairwise Distances and Convex Radius Estimation

In machine learning, geometric bounding is central to the generalization performance of Support Vector Machines (SVMs). Standard SVMs maximize the classification margin, but advanced formulations—known as radius-margin SVMs—simultaneously minimize the radius of the smallest sphere enclosing the data. Minimizing this radius prevents the model from overestimating the spread of the data, which significantly improves feature selection and classification accuracy.

However, calculating the exact minimal enclosing sphere often introduces non-convexity or forces the use of loose linear approximations that fail as the dimensionality of the feature space grows.

To overcome this, Kalousis et al. proposed a shift in perspective: approximating the data-enclosing radius using the maximum pairwise distance between data points. Why does this work?

  1. Tighter Bounds: The maximum distance between any two points in a dataset provides a strictly tighter and more accurate estimation of data spread than traditional linear relaxations.
  2. Convexity: Unlike direct minimal-enclosing-sphere formulations, the pairwise distance metric can be integrated into a fully convex optimization framework.

By bounding the radius via pairwise distances, the authors created algorithms ($R-SVM^+$ and $R-SVM^+_\mu$) that remain stable and highly performant even in exceptionally high-dimensional spaces.

Ellipsoidal Sandwiching in Optimization Landscapes

In continuous optimization, the challenge is often to navigate a complex search space bounded by a polytope or an intersection of multiple quadratic constraints. Here, the geometric primitive of choice for sandwiching the space is the Dikin ellipsoid, which is constructed locally using logarithmic barrier functions.

┌────────────────────────────────────────┐
│  Polytope Search Space                 │
│      ┌──────────────────────────┐      │
│      │  Outer Dikin Ellipsoid   │      │
│      │    ┌────────────────┐    │      │
│      │    │  Target Set    │    │      │
│      │    └────────────────┘    │      │
│      └──────────────────────────┘      │
└────────────────────────────────────────┘

In the context of exact convex minimization, Lee et al. demonstrated that the Dikin ellipsoid can effectively sandwich a polytope of interest. This sandwiching provides a rigorous structural guarantee: it ensures that the optimal solution (even an integer minimizer) is trapped within a manageable, well-defined volume. By using this geometric guarantee to guide cutting-plane methods, the algorithm can efficiently re-center its search space without relying on expensive covariance-based sampling, slashing the theoretical runtime for general convex minimization down to a highly practical $\tilde{O}(n^4)$.

When the search space is defined by the intersection of multiple ellipsoids, the precision of the outer bounding radius dictates the performance guarantee of the optimization algorithm. Zhang et al. focused on this exact relationship in quadratic programming. Through a detailed mathematical analysis of logarithmic barrier functions, the authors corrected a long-standing geometric bound on the outer Dikin ellipsoid radius from $m$ to $\sqrt{m^2 + m}$. Because this new bound is proven to be the tightest possible for the problem, it directly sharpens the theoretical approximation guarantees for algorithms solving non-convex quadratic programs under convex quadratic constraints.

Key Foundational Work

Covering Planar Sets (2021) — contributed 5 concept elements to this direction.
Convex formulations of radius-margin based Support Vector Machines (2013) — contributed 2 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_pairwise_distance_radius_approximation_4a85ddd8,
  title = {pairwise distance radius approximation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/pairwise-distance-radius-approximation/rdr_4a85ddd8a8e74bb99076b42e93b53fe5},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_pairwise_distance_radius_approximation_4a85ddd8_v1,
  title = {pairwise distance radius approximation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/pairwise-distance-radius-approximation/rdr_4a85ddd8a8e74bb99076b42e93b53fe5/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake