Halving lines and measure concentration in the plane
Rom Pinchasi · 2009
Given a set P of n points in the plane and a collection of k halving lines of P l1, ..., lk, indexed according to the increasing order of their slopes, we denote by d(lj,lj+1) the number of points in P that lie above lj+1 and below lj. We prove an upper bound of 3nk1/3 for the sum sumj=1k-1d(lj,lj+1). We show how this problem is related to the halving lines problem and provide several consequences about measure concentration in R2.