Halving lines
About this app
n points in the plane: how many lines through two of them split the rest exactly in half? Place and drag points, all halving lines glow live; Lovász's rotating line counts them as changes; record sets from a search; log-log chart against Dey's n^{4/3}. New: at most C·n^{4/3−ε}, openai/math family 183 (formalised in Lean).
What it is about
Take n points in the plane, no three on a line, with n even. A line through two of the points is halving if exactly (n−2)/2 of the others lie on each side. How many halving lines can a point set have at most? The question is part of the k-set problem in computational geometry. There are always at least n/2; from above, Tamal Dey lowered the bound to n^(4/3) in 1998, and the exponent has stood since. The best constructions lie far below, at n·e^(c√log n). An AI-generated preprint in github.com/openai/math (family 183) claims at most C·n^(4/3−ε), with constants that are not specified. The catalogue lists the main theorem as formalised in Lean; the preprint is not peer-reviewed.
What the app shows
You place and drag points, and every halving line lights up live. Presets include convex position with exactly n/2 halving lines, random points and record sets from a long search. A rotating line shows Lovász’s viewpoint: in every direction there is a line that halves the points, and as it turns it switches its pair exactly at the halving lines. A log-log chart compares your values with n/2, n^(4/3) and n^(3/2). The app draws no curve for the new bound, because the proof gives no numerical values.
Try it yourself
Start with convex position and drag single points inwards: the number of halving lines goes up. Run the search, which moves points and keeps every improvement. Start the rotating line and count how often it changes its pair during half a turn. With an odd number of points there are no halving pairs. How fast such counts can grow with n is not something any search can decide; only the proof does that.
Frequently asked questions
- What is a halving line?
- For n points in general position (n even), a halving line is a line through two of the points that splits the remaining n−2 points into two equal halves. How many there are depends on the arrangement. In convex position there are exactly n/2.
- What is the k-set problem?
- A k-set is a subset of k points that can be separated from the rest by a line. The k-set problem asks for the maximum number of such subsets a set of n points can have. Halving lines correspond to the case k ≈ n/2 and are the hardest core of the problem.
- Has Dey’s n^(4/3) bound for halving lines been improved?
- An AI-generated preprint in the catalogue github.com/openai/math (family 183) claims that every sufficiently large set has at most C·n^(4/3−ε) halving lines, with absolute but unspecified constants. The catalogue lists the main theorem as formalised in Lean. The preprint has not yet been peer-reviewed, and the gap to the best construction remains large.
- What can I try out in this app?
- You place, drag and remove points and see every halving line live. A rotating line counts them as switches, and a search finds point sets with many halving lines. A chart compares your values with the known bounds.
Subject: Open problems, solved by AI
More from Open problems, solved by AI
- Anderson localisation: 2D vs. 3D (3D)
- Barker sequences and circulant Hadamard matrices
- Barnette's conjecture: a round trip over every polyhedron (3D)
- Birkhoff billiards: only the ellipse has no gaps
- Cardy's formula — percolation in a random tiling
- The plane is not five-colourable (Hadwiger–Nelson)
- Double-dimer loops and CLE₄
- Triangular billiards — irrational angles mix (3D)
A VisuApp by heyprof: interactive, free in your browser, no sign-up. What is a VisuApp? · All apps