Tightening Complexity Bounds for Discrete Geometric Structures

This direction is split into other directions: existence of k-crossing matchings, tightness of geometric bounds. Its last version stays readable and citable here.

Version 1 of 187 papers98 conceptsfrozen 2026-10-04

In discrete geometry, the central challenge is often a simple question of counting: if we arrange $n$ geometric objects—lines, points, or planes—how complex is the resulting structure? While researchers can often find a rough estimate, a persistent theme across decades of work is the "gap." We might know that a structure's complexity is at least $n^2$ and at most $n^{2.1}$, but that small sliver of uncertainty, often represented by a logarithmic factor or a tiny $\epsilon$, hides fundamental truths about the nature of space.

The research direction represented here is the systematic effort to close these gaps, moving from existence proofs to "tight" bounds where the upper and lower limits finally meet.

The Complexity of Arrangements and the Epsilon Artifact

When you slice three-dimensional space with $n$ planes, you create a collection of cells. A foundational problem in the field, explored by Herbert Edelsbrunner, Leonidas J. Guibas, and Micha Sharir in The Complexity of Many Cells in Arrangements of Planes and Related Problems, is determining the total number of faces in a subset of these cells.

The intuition behind the "gap" here often stems from our tools. Many upper bounds are derived using divide-and-conquer techniques or randomized sampling (like $\epsilon$-nets). These methods are powerful but frequently introduce a "logarithmic tax"—an extra factor in the complexity that researchers suspect is an artifact of the proof rather than a property of the geometry itself. For instance, in The complexity and construction of many faces in arrangements of lines and of segments, the authors achieved a near-tight bound of roughly $O(m^{2/3}n^{2/3})$, yet a tiny $\epsilon$ remained. Closing this gap requires moving beyond general-purpose combinatorial tools to find constraints specific to the way lines and planes must intersect.

Halving Structures and the Selection Lemma

One of the most stubborn gaps in the field concerns "halving" structures. If you have a set of points, in how many ways can you split them exactly in half with a line or plane?

In Points and Triangles in the Plane and Halving Planes in Space, Boris Aronov and colleagues introduced a "Selection Lemma" to prove that if you have many triangles, there must be a point that stabs a significant fraction of them. This geometric intuition allowed them to tighten the bounds on halving planes in 3D. However, as noted by Artur Andrzejak and Emo Welzl in Halving point sets, a massive discrepancy still exists between what we can prove (upper bounds) and what we can construct (lower bounds). This suggests that our current understanding of point set partitions is still missing a "fundamental constraint" that prevents the complexity from exploding.

Duality in Piercing and Hitting Sets

A different facet of this direction involves the density of intersections. If you have a collection of convex sets where every $p$ of them contain a common point among some $q$, how many points do you need to "pierce" (intersect) every set in the collection?

This is the Hadwiger-Debrunner $(p, q)$-conjecture, famously resolved by Daniel J. Kleitman and Noga Alon in Piercing convex sets. While they proved the number of points is finite, the resulting upper bounds were "astronomical." The ongoing work in this area, such as Frank Nielsen’s work on Fast stabbing of boxes in high dimensions, seeks to reconcile the duality between the maximum number of disjoint objects and the minimum number of points needed to hit them. The gap here is a measure of our ignorance regarding the "efficiency" of geometric intersections.

Breakthroughs via the Polynomial Method

When traditional combinatorial methods stall, new mathematical frameworks sometimes provide the "missing link" to achieve perfect tightness. A landmark example is the study of "joints"—points where three non-coplanar lines intersect. For years, the upper bounds for the number of joints in $n$ lines were significantly higher than any known construction.

In On Lines, Joints, and Incidences in Three Dimensions, György Elekes, Haim Kaplan, and Micha Sharir utilized the polynomial method. By representing geometric objects as the zeros of low-degree polynomials, they were able to capture the algebraic rigidity of lines in space. This didn't just narrow the gap; it provided a sharp, optimal bound, demonstrating that the "complexity" of these structures is often governed by underlying algebraic properties that simple counting arguments miss.

Why Tightness Matters

The drive toward tight bounds is not merely a quest for numerical precision. As seen in An Optimal Algorithm for Higher-Order Voronoi Diagrams in the Plane by Timothy M. Chan and others, algorithmic efficiency is often capped by our combinatorial understanding. If we don't know the true complexity of a Voronoi diagram, we cannot know if our algorithms are truly optimal.

Whether it is narrowing the 50-year-old gap in Slicing the Hypercube or refining the constants in Quantitative Tverberg, Helly, & Carathéodory theorems, this research direction treats every logarithmic factor as a signpost pointing toward a deeper, yet-to-be-discovered geometric principle.

Papers in this version

Showing 60 of 87 papers.

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_tightening_complexity_bounds_for_discret_16c1cfdd,
  title = {Tightening Complexity Bounds for Discrete Geometric Structures},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/tightening-complexity-bounds-for-discrete-geometric-structures/rdr_16c1cfdd1b304f209e8f179680fd30c1},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_tightening_complexity_bounds_for_discret_16c1cfdd_v1,
  title = {Tightening Complexity Bounds for Discrete Geometric Structures},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/tightening-complexity-bounds-for-discrete-geometric-structures/rdr_16c1cfdd1b304f209e8f179680fd30c1/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}