Boris Aronov, Esther Ezra and Micha Sharir, have a nice upcoming STOC paper, showing how to improve set-cover in certain geometric settings. Here, you have a set of points you need to cover by given regions in the plane (say fat triangles), and you would like to compute the minimum cardinality set of regions covering the points. Clarkson and Varadarajan showed that if the union complexity is near linear, then one can get an improved approximation. Thus, for fat triangles you get log(log(Opt)) approximation. The new paper shows that by doing a slight over-sampling, one can reduce the covering size by a log(linear union complexity overheard). Formally, if the union complexity of k regions is O(k * beta(k)), then you get a set cover of size O( Opt* log(beta(Opt))). (This paper also contain other results, using similar ideas in a more involved fashion for the dual settings of boxes and points.)

As such, for covering points by a given set of fat triangles, the new paper provides a cover by a set of size O(opt* log log log Opt).

This basic observation is simple but was missed by people working on this kind of problems (including myself). An interesting question is where else this over-sampling idea can be used?

Comments are closed.