**Small-size ε-Nets for Axis-Parallel Rectangles and Boxes**

*Boris Aronov, Esther Ezra and Micha Sharir*

We show the existence of ε-nets of size O((1/ε) log log (1/ε)) for planar point sets and axis-parallel rectangular ranges. The same bound holds for points in the plane with "fat" triangular ranges, and for point sets in 3-space and axis-parallel boxes; these are the first known non-trivial bounds for these range spaces. Our technique also yields improved bounds on the size of ε-nets in the more general context considered by Clarkson and Varadarajan. For example, we show the existence of ε-nets of size O((1/ε) log log log (1/ε)) for the "dual" range space of "fat" regions and planar point sets. Plugging our bounds into the technique of Brönnimann and Goodrich, we obtain improved approximation factors (computable in randomized polynomial time) for the hitting set or the set cover problems associated with the corresponding (primal or dual) range spaces.

**Private Coresets**

*Dan Feldman, Amos Fiat, Haim Kaplan and Kobbi Nissim*

We forge a link between coresets, that have found use in a vast host of geometric settings, and differentially private databases that can answer any number of queries without compromising privacy — queries of the same class well approximated by the coreset. Such queries imply efficient privacy preserving optimization algorithms for a wide range of optimization problems but are also of independent interest. We give (computationally inefficient) transformations from any coreset for queries with low generalized sensitivity to differentially private databases for the same queries. This greatly extends the work of Blum, Ligett, and Roth [BLR08], and McSherry and Talwar [MT07].

We define the notion of*private coresets*, which are simultaneously both coresets*and*differentially private. We produce*computationally efficient*private coresets for k-median and k-mean in R^{d}, i.e., efficient differentially private databases for such queries. Private coresets also imply efficient coalition proof mechanisms and error resilient data structures.

Unlike coresets which only have a multiplicative approximation factor, we prove that private coresets must have a (small) additive error.

**Explicit construction of a small ε-net for linear threshold functions**

*Yuval Rabani and Amir Shpilka*

We give explicit constructions of ε nets for linear threshold functions on the binary cube and on the unit sphere. The size of the constructed nets is polynomial in the dimension n and in 1/ε. To the best of our knowledge no such constructions were previously known. Our results match, up to the exponent of the polynomial, the bounds that are achieved by probabilistic arguments.

As a corollary we also construct subsets of the binary cube that have size polynomial in n and covering radius of n/2 - c\sqrt{n log n}, for any constant c. This improves upon the well known construction of dual BCH codes that only guarantee covering radius of n/2 - c\sqrt{n}.

**Every planar graph is the intersection graph of segments in the plane**

*Jeremie Chalopin and Daniel Goncalves*

Given a set S of segments in the plane, the intersection graph of S is the graph with vertex set S in which two vertices are adjacent if and only if the corresponding two segments intersect. We prove a conjecture of Scheinerman (PhD Thesis, Princeton University, 1984) that every planar graph is the intersection graph of some segments in the plane.

## Tuesday, February 10, 2009

### STOC accepted CG papers

The list of STOC 2009 accepted papers was posted on Friday. Happily, they also provided an html version with abstracts. Below are the computational geometry related papers I noticed on the list (and then happily stole from the html source).

Subscribe to:
Post Comments (Atom)

## No comments:

Post a Comment