Papex

Open problem · Mathematics · Open

Halving lines and k-sets

What is the largest number of ways a line can split n points in the plane into two equal halves, or cut off exactly k of them?

Summary

The problem was first studied by Lovász and by Erdős and co-authors, and it matters for analysing geometric algorithms. Tamal Dey proved an upper bound of O(nk^(1/3)) for k-sets, while the best lower bound, due to Tóth, is far smaller; closing the gap is open.

Source

Open, as listed by Wikipedia · Unsolved problems in mathematics. Checked 18 Nov 2026.

The status is the source’s. Papex does not decide whether a problem is solved.

Records on this problem

No public record addresses this problem yet.

More in Mathematics