Sharp Extremal Bounds for Angular Occupancy (Behind the Curtains)

you can find the full paper here

First Attempts, and the Limits of Energy

When I first began thinking about angular occupancy, I wasn’t looking for a brand-new problem. I was chasing a theme that has long fascinated me in discrete geometry: how do we measure the geometric richness of a finite set of points?

This fascination is not unique to me. Erdős, way back in 1946, posed the distinct distances problem: given n points in the plane, how many distinct distances can they determine? That question alone gave birth to entire decades of work in combinatorial geometry. Later, Fishburn and Füredi asked about distinct angles, while Pach and Sharir studied repeated angles. Each time, the same underlying itch was being scratched: when you place points in the plane, what kinds of diversity can they generate?

Why angles, why bins?

It was natural to think of angles — after all, distances and directions had already been well studied. But if you go straight for “distinct angles,” you run into two problems:

The number of distinct angles is sensitive to exact coincidences. A regular polygon, for instance, collapses many triples of points into the same handful of angle values.
The problem has a binary feel: either two angles are the same or not. There’s no way to measure approximate similarity.

That second issue especially bothered me. In real-world data (say, point clouds in computer vision), one doesn’t care if two angles differ by 0.0001 radians — they’re practically the same. Yet the combinatorial definition treats them as distinct.

So I thought: what if we introduce a resolution parameter ε? Partition the interval [0, π] into bins of length ε, and simply count how many bins get “hit” by at least one angle.

This leads to the angular occupancy function Fε(A). For a finite point set A ⊂ R², Fε(A) counts the number of ε-bins containing at least one angle ∠(u, v, w). It interpolates between two regimes:

As ε → 0, you recover the number of distinct exact angles.
As ε grows, you only measure the large-scale spread of angles.

I liked this parameter because it captured the multi-scale nature of geometric diversity. It was neither too rigid nor too fuzzy.

The universal bound

The first paper I wrote on this (“On ε-Angle Classes Determined by Planar Point Sets”) was largely about establishing some basic theory. The central result was a universal bound:

F_\varepsilon(A) \;=\; O\big(\min\{1/\varepsilon, n^2\}\big).

The reasoning is simple:

There are only about 1/ε bins in total.
A classical result tells us there are at most O(n²) distinct exact angles from n points.

So whichever of these two is smaller dominates.

At the time, this felt like a solid starting point. But soon the dissatisfaction crept in: is this bound sharp? Do there exist point sets that actually realize Θ(min{1/ε, n²}) occupancy, or is the universal estimate wastefully loose?

This question became the heartbeat of the sequel paper, “Sharp Extremal Bounds for Angular Occupancy.” But before I could get there, I had to wander through quite a few dead ends.

First attempts at sharpness

At first, I thought sharpness might come from regular polygons. After all, regular structures often serve as extremal examples in discrete geometry. The hope was that for small ε, each distinct angle of a polygon would fall into its own bin, maximizing occupancy.

But regular polygons betray you quickly. They have too much symmetry. Once ε crosses the threshold π/n, distinct angles start to collapse into the same bin. The occupancy Fε(A) falls drastically — sometimes down to O(n). So rather than being extremal maximizers, polygons turned out to be extremal minimizers in some regimes.

That was an early lesson in humility: symmetry, which is so beautiful in geometry, often works against you in extremal problems. Symmetry means coincidences, and coincidences kill diversity.

Another natural idea was the integer grid. With n = m² points on an m × m grid, there are many triples, and the directions are tied to rational slopes. Surely that would yield a huge variety of angles?

But grids also collapsed too much. Angles repeat along lattice directions, and multiplicities balloon. Instead of spreading uniformly across bins, triples pile up into a smaller set of angle values.

So two of the most “obvious” candidates — polygons and grids — gave me the exact opposite of what I wanted. If extremal sets existed, they had to be somewhere else.

The energy method

At this point, I leaned on the main analytic tool I had from the first paper: the energy inequality.

Recall that for each bin j we define xj(A), the number of triples landing in that bin. The angular energy is

E(A) \;=\; \sum_j x_j(A)^2.

Cauchy–Schwarz gives the bound

F_\varepsilon(A) \;\ge\; \frac{X(A)^2}{E(A)},

where X(A) = n(n−1)(n−2) ≈ n³ is the total number of triples.

The philosophy here is simple: if triples are uniformly distributed across bins, energy is small and occupancy is large. If triples cluster, energy is big and occupancy is small.

At first, I thought this inequality might be enough to prove sharpness. But no — the bound is too coarse. For example, in highly structured sets, the energy explodes, and the inequality degenerates.

So I tried to refine it. I asked: what if we consider higher moments, not just the quadratic one? That is, define

E_k(A) = \sum_j x_j(A)^k,

and apply Hölder’s inequality. This gives a family of bounds:

F_\varepsilon(A) \;\ge\; \left(\frac{X(A)^k}{E_k(A)}\right)^{1/(k-1)}.

This looked promising on paper. In particular, when xj’s are very uneven, higher moments penalize the concentration more strongly.

But when I tried to apply it concretely, I realized I was stuck in the same trap: without a priori bounds on angle multiplicities, I couldn’t control E_k(A) sharply enough. The energy method was powerful, but only if I could combine it with something else.

That was the next turning point: I needed to understand multiplicities.

Deterministic Constructions and the Randomness Trick

By the time I’d beaten the energy method into every shape I could think of, I was running in circles. The math was clean — those inequalities looked pretty — but they didn’t bite hard enough. They told me “if you spread your triples out nicely, you’ll do well,” but they didn’t tell me how to guarantee that spread.

The missing piece was clear: multiplicity control. How many triples can pile up into the same exact angle value? If that number is small, then automatically you’re forced to spread across many bins. If that number is huge, occupancy collapses.

This led me to hunt for point sets where angle multiplicities stay low.

Multiplicity: the villain behind the scenes

Let’s pause for a second. Suppose you have n points. That’s about n³ ordered triples. Now, if an angle value gets repeated with multiplicity, say, n² times, that’s catastrophic. It means an enormous fraction of triples are sitting on just one bin once you introduce ε. Your occupancy tanks.

Regular polygons are the poster child here: lots of triples collapse into the same handful of angles like π/3, π/2, etc. That’s why polygons are terrible for maximizing occupancy.

So the golden rule became: don’t let any angle value show up too often.

Two concentric circles: the first win

The first clean construction I found was almost embarrassingly simple. Put n/2 equally spaced points on the unit circle, and the other n/2 equally spaced on a larger concentric circle.

At first glance, this feels like just another symmetric setup. But here’s the magic: for any apex v, if you fix an angle θ, then the rays forming that angle basically determine u and w uniquely, up to two choices per circle. That means you get at most 4 triples per apex per angle value. Multiply by n apices, and suddenly multiplicity is ≤ 4n.

That’s linear! Exactly what I wanted.

The consequence? The number of distinct exact angles is at least n³ / (4n) ≈ n². Which means the number of occupied bins Fε(A) is at least min{n², 1/ε}. In other words: bang, we hit the universal upper bound from below.

I remember the rush when I worked this out. I’d spent weeks trying clever inequalities, and here the answer was staring me in the face: just put the points on two circles. Sometimes geometry rewards you for being simple.

Convex position: another clean case

Once the two-circle trick worked, I looked around for other families with small multiplicity. The most natural candidate was points in convex position.

Take n points around a convex curve (say, a slightly perturbed convex polygon to avoid degeneracies). Then around any apex v, the rays uv for u ∈ A{v} appear in circular order. For a fixed angle θ, at most two pairs of rays can realize it — one clockwise, one counterclockwise. So per apex you get at most 2 triples. Multiply across all n apices, and again multiplicity ≤ 2n.

Boom: another family that guarantees Fε(A) = Ω(min{n², 1/ε}).

At this point, I felt I had solid evidence: the universal bound is actually sharp. We had deterministic families that saturate it in both regimes.

But there was still a nagging problem: structured sets like grids. I kept circling back to them, because grids are so central in discrete geometry. They’re the “go-to” construction. And yet, they seemed hopelessly bad for occupancy because of all the angle coincidences.

Then came the breakthrough: what if we just mess them up a little?

Shaking the grid

This was one of those “shower thoughts.” I was frustrated with the grid’s coincidences, and I thought: okay, but coincidences are fragile. If you wiggle the points even a tiny bit, those exact equalities should disappear.

So I considered a random perturbation model: take an m × m integer grid (so n = m² points), and independently shift each point by a tiny random vector (say, inside a small disk of radius n⁻C).

The idea is that randomness kills coincidences while preserving the large-scale structure. Suddenly, angles that used to coincide now differ by just enough to fall into separate bins.

This turned into one of the most enjoyable parts of the whole project — mixing probability with geometry.

The density trick

The key was to prove that for any fixed triple (u, v, w), the angle ∠(u+ξu, v+ξv, w+ξw) has a smooth probability density across [0, π], bounded above and below.

This is where analysis crept in. I wrote the angle as an arccos of a normalized dot product, differentiated it, and invoked the coarea formula. It was a bit technical, but the conclusion was beautiful:

For any ε-bin away from 0 or π, the probability that a triple’s angle lands inside it is about proportional to ε.

That was the missing piece. It meant the whole thing behaved like a balls-into-bins problem: n³ triples, each “thrown” into bins with probability ≈ ε.

Expectations, regimes, and surprises

From there, the expectation calculation was straightforward. The expected number of triples per bin was about n³ε. Depending on ε, you get two regimes:

Dense regime (ε not too small): each bin has plenty of triples, so with high probability every bin is occupied. Occupancy ≈ 1/ε.
Sparse regime (ε tiny): each bin only gets a few triples, so occupancy is capped by n².

Either way, the expectation came out as Θ(min{n², 1/ε}), exactly matching the conjectured bound.

Even better: with a bit of work (second-moment arguments, Janson’s inequality), you could show concentration with high probability. So not only was the expectation right — the actual value almost always landed there.

This was one of the most satisfying results in the whole project. Randomness, which I’d originally considered as a desperate hack, turned out to exactly saturate the bound. It felt like nature was whispering: “Yes, you’re on the right track.”

A candid note

I should admit: the first time I tried to write the probabilistic argument, it was a disaster. My notes were covered in half-baked Poisson approximations and confused variance estimates. It wasn’t until I forced myself to think in terms of densities and Jacobians that things clicked.

And once it clicked, it was clean. That’s one of the paradoxes of research: the path is messy, but the final proof looks like it was inevitable all along.

Where we stood

By the end of this stage, I had:

Deterministic constructions (two circles, convex sets) proving multiplicity stays low → Ω(min{n², 1/ε}).
Random perturbations of grids proving occupancy ≈ Θ(min{n², 1/ε}) with high probability.

That was enough to strongly support the conjecture:

$F^{\max}_\varepsilon(n) \;=\; \Theta(\min\{n^2, 1/\varepsilon\}).$

But there were still loose ends. What about extremely small ε, where the naive expectation breaks down? What about incidence geometry connections? And what about grids without perturbations — can we bound their multiplicity precisely?

Those became the topics of the final stage of the journey.

Collisions, Incidences, and Open Horizons

By this point in the story, I had the main pieces in place. The two-circle construction and convex sets gave me deterministic families with low multiplicity. Randomly perturbed grids gave me probabilistic models that hit the extremal bound with high probability.

If I had stopped there, the narrative would already feel satisfying: the universal bound was not just a vague ceiling, it was actually the right scale. But I couldn’t shake two nagging questions:

What happens in the extreme sparse regime — when ε is so tiny that my expectation arguments break down?
Is there a deeper connection to incidence geometry, the Szemerédi–Trotter kind of world, that might explain multiplicities more systematically?

Both questions pulled me deeper into the weeds. And, honestly, both came with a fair share of hair-pulling.

The problem with tiny ε

Up to this point, I’d been happy saying: “Each bin gets about n³ε triples on average, so the occupancy behaves like min{n², 1/ε}.” But that hand-waving falls apart once ε becomes smaller than n⁻².

Why? Because at that scale, the expected number of triples per bin drops below 1, and the naive Poisson approximation tells you the occupancy is ≈ n³ε. But occupancy can never exceed n², no matter how small ε is. So the expectation argument overestimates.

I needed a new approach to handle this extreme case.

Thinking in terms of collisions

The trick was to reframe the question. Imagine each triple is “trying” to land in its own unique bin. If there were no overlaps, you’d get about n² occupied bins, since the number of distinct angles is Θ(n²). The only thing that reduces occupancy is collisions: two different triples landing in the same ε-bin.

So the real game was to bound the number of collisions.

This was the kind of shift that happens in research: you stop trying to push your old framework harder, and you suddenly realize the right way is to flip the perspective.

A collision-counting argument

Here’s the idea: take two triples (u, v, w) and (u′, v′, w′). What’s the probability that their angles differ by at most ε?

Thanks to the smooth density results I’d already proved, the answer is O(ε). More carefully, the joint law of (θ, θ′) has a bounded density, so the chance they fall in the same ε-bin is O(ε²).

Now count pairs of triples. There are about n⁶ of them. Multiply out: the expected number of collisions is O(n⁶ε²).

Here’s the punchline: if ε ≪ n⁻², that expectation is o(n²). In other words, with high probability, collisions don’t accumulate enough to cut occupancy below n².

So in the extreme sparse regime, the lower bound Fε(A) = Ω(n²) still holds.

That was a huge relief. It meant the bound was stable across all ε, not just the “friendly” ranges.

The joy of random perturbation (again)

I can’t overstate how much randomness helped here. Without perturbation, the grid’s angles line up in exact coincidences, and you have no hope of bounding collisions cleanly. With perturbation, coincidences melt away, and you get probabilistic independence that makes the counting work.

There’s something poetic about this: order (the grid) plus a sprinkle of randomness gives you extremal behavior. Too much order, and you collapse; too much randomness, and you lose structure. But the right balance makes everything click.

Angles as incidences

With the sparse regime settled, I turned back to the bigger picture: could we frame angular occupancy in terms of incidence geometry?

Here’s the mental image: fix an apex v. Each other point u gives you a direction uv, which sits on the unit circle S¹. An angle θ at v is realized if there exist two rays separated by arc length θ.

That’s an incidence problem: points (the rays) and arcs (separations by θ). And whenever you see “points vs curves,” you start thinking of Szemerédi–Trotter, which famously bounds incidences between points and lines.

It wasn’t a one-to-one match — we were dealing with circular arcs, not lines — but the analogy was strong enough to make me suspect that incidence geometry might give sharper multiplicity bounds in structured sets like grids.

A grid conjecture

This led me to make a concrete conjecture:

In an m × m integer grid (n = m² points), every angle value is realized by at most O(n¹⁺ᵒ(1)) triples.

If that’s true, it would mean Fε(A) = Ω(min{1/ε, n²⁻ᵒ(1)}). In other words, the universal bound is sharp up to subpolynomial factors even in pure grids, no perturbation needed.

The heuristic is simple: angles in a grid correspond to rational slopes q/p. Counting triples that realize the same slope reduces to counting lattice points proportional to (p, q). And the number of such points is about m/gcd(p, q). Summing over directions gives divisor sums, which number theorists know how to handle.

I didn’t push this all the way — it gets technical fast — but I’m convinced the conjecture is true. It’s the kind of problem that probably needs a blend of combinatorial geometry and analytic number theory.

A quick tour of open problems

By the end of the paper, I had a list of “future directions” that I’m still excited about:

Exact extremal behavior. Prove once and for all that F^maxε(n) = Θ(min{1/ε, n²}). We have strong evidence, but a clean theorem covering all n and ε is still missing.
Integer grids. Either prove or disprove the multiplicity conjecture. This feels like the next logical step.
Random point sets. For i.i.d. uniform points in a convex body, can we prove sharp concentration of Fε(A)? Heuristics say yes, but a rigorous proof would be beautiful.
Higher dimensions. Angles in R³ (dihedral angles, solid angles) might show similar occupancy phenomena. What’s the right definition there?
Algorithmics. How hard is it to compute Fε(A) for a given set? Can we approximate it efficiently?
Applications. Could angular occupancy be useful as a feature in point-cloud analysis or machine learning? It measures “shape diversity” in a very geometric way.

Reflections

Looking back, what I love about this project is how it danced across different worlds:

Combinatorics: thinking about extremal constructions.
Geometry: the raw intuition about angles, polygons, circles, grids.
Probability: using perturbations, densities, collisions, concentration.
Analysis: the coarea formula, Jacobians, energy methods.
Number theory (lurking in the background): grids and rational slopes.

It was never just one tool. Every time I hit a wall, I had to shift lenses. And each shift brought a fresh perspective: from energy to multiplicity, from structure to randomness, from combinatorics to incidence geometry.

That, I think, is the real behind-the-curtains story. Research doesn’t move in straight lines. It zigzags, it stalls, it surprises you. And sometimes, the most effective step is the simplest one — like just putting points on two circles, or nudging a grid with tiny random perturbations.

Closing thought

So where does this leave us? To me, the angular occupancy function feels like it has legs. It’s not just a quirky variant of “distinct angles.” It’s a parameter that captures scale-dependent geometric diversity. It fits naturally alongside distances, directions, and incidences.

I don’t know if it’ll spark the same level of attention as the Erdős distance problem — probably not, that bar is sky-high — but I do know it opened up a landscape I hadn’t appreciated before.

And personally, that’s the joy: taking something as simple as “counting angles in bins” and discovering that it connects energy inequalities, probabilistic methods, and deep number-theoretic conjectures. That journey, with all its detours and dead ends, is exactly why I love doing this kind of math.

Arya’s Algorithms

Search This Blog