Tag Archives: Discrepency

A Discrepancy Problem for Planar Configurations

Yaacov Kupitz and Micha A. Perles asked:

What is the smallest number C such that for every configuration of n points in the plane there is a line containing two or more points from the configuration for which the difference between the number of points on the two sides of the line is at most C?

We will refer to the conjecture that C is bounded as Kupitz-Perles conjecture. It was first conjectured that C=1, but Noga Alon gave an example with C=2. It is not known if C is bounded and, in fact, no example with C>2 is known.

Alon’s example

Kupitz himself proved that C \le n/3, Alon proved that C \le K\sqrt n, Perles showed that C \le K\log n, and Rom Pinchasi showed that C \le K\log \log n. This is the best known upper bound.  (K is a constant.) Pinchasi’s result asserts something a little stronger: whenever you have n  points in the plane, not all on a line, there is a line containing two or more of the points such that in each open half plane there are at least n/2-K\log \log n points. 

The proof uses the method of allowable sequences developed by Eli Goodman and Ricky Pollack. Another famous application of this method is a theorem of Ugnar asserting that 2n points in the plane which are not on the same line determine at least 2n directions. Continue reading