A Simple Proof of Optimal Epsilon Nets

Description

Showing the existence of small-sized epsilon-nets has been the subject of investigation for almost 30 years, starting from the breakthrough of Haussler and Welzl (1987). Following a long line of successive improvements, recent results have settled the question of the size of the smallest epsilon-nets for set systems as a function of their so-called shallow cell complexity. In this paper we give a short proof of this theorem in the space of a few elementary paragraphs. This immediately implies all known cases of results on unweighted epsilon-nets studied for the past 28 years, starting from the result of Matou\v{s}ek, Seidel and Welzl (SoCG 1990) to that of Clarkson and Varadarajan (DCG 2007) to that of Varadarajan (STOC 2010) and Chan et al. (SODA 2012) for the unweighted case, as well as the technical and intricate paper of Aronov et al. (SIAM Journal on Computing, 2010). We find it quite surprising that such a simple elementary approach was missed in all earlier work, as all ingredients were already known in 1991.

Abstract

International audience

Additional details