Lower bounds for data structures with space close to maximum imply circuit lower bounds

Viola, Emanuele

doi:10.4086/toc.2019.v015a018

Abstract Let$$p_{1},\ldots ,p_{n}$$

p_{1}, \dots, p_{n}

be a set of points in the unit square and let$$T_{1},\ldots ,T_{n}$$

T_{1}, \dots, T_{n}

be a set of$$\delta $$

δ

-tubes such that$$T_{j}$$

T_{j}

passes through$$p_{j}$$

p_{j}

. We prove a lower bound for the number of incidences between the points and tubes under a natural regularity condition (similar to Frostman regularity). As a consequence, we show that in any configuration of points$$p_{1},\ldots , p_{n} \in [0,1]^{2}$$

p_{1}, \dots, p_{n} \in {[0, 1]}^{2}

along with a line$$\ell _{j}$$

ℓ_{j}

through each point$$p_{j}$$

p_{j}

, there exist$$j\neq k$$

j \neq k

for which$$d(p_{j}, \ell _{k}) \lesssim n^{-2/3+o(1)}$$

d (p_{j}, ℓ_{k}) ≲ n^{- 2 / 3 + o (1)}

. It follows from the latter result that any set of$$n$$

n

points in the unit square contains three points forming a triangle of area at most$$n^{-7/6+o(1)}$$

n^{- 7 / 6 + o (1)}

. This new upper bound for Heilbronn’s triangle problem attains the high-low limit established in our previous work arXiv:2305.18253.

More Like this