AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI   Info

AG Audience

English

30 Minutes

Saarbrücken

The geometric discrepancy problem asks for sets of N points evenly distributed in the d-dimensional unit cube [0,1)^d. Here "evenly distributed" means that ideally each axis-parallel rectangles R anchored in 0 contains $N \volume(R)$ points. It is not totally obvious that for this problem methods and thinking from discrete algorithmics are useful, but in a few recent works we were successfully following this road. For example, in 2013 we showed that a random point set usually leads to a rectangle R having $\sqrt{dN}$ points too many or too few, which provided a matching lower bound to the upper bounds of Heinrich et al. (2001) and Aistleitner (2011). In this work, we regard point set constructed from partitioning the unit cube into small cubes and putting exactly one point randomly into each cube. Again by using elementary combinatorial arguments, we determine the discrepancy of such point sets. Our result improves the recent upper and lower bounds of Steinerberger and Pausinger (2016) and disproves their guess on the true order of magnitude.

Benjamin Doerr

--email hidden

passcode not visible

logged in users only