272 citations · 611 across the 76 of their papers we have counts for
7 papers · 1 filter
On the Set Multi-Cover Problem in Geometric Settings
Chandra Chekuri, Kenneth L. Clarkson, Sariel Har-Peled
We consider the set multi-cover problem in geometric settings. Given a set of points P and a collection of geometric shapes (or sets) F, we wish to find a minimum cardinality subse…
Relative -Approximations in Geometry
Sariel Har-Peled, Micha Sharir
We re-examine the notion of relative $(p,\eps)$-approximations, recently introduced in [CKMS06], and establish upper bounds on their size, in general range spaces of finite VC-dime…
Carnival of Samplings: Nets, Approximations, Relative and Sensitive
Sariel Har-Peled
We survey several results known on sampling in computational geometry.
Being Fat and Friendly is Not Enough
Sariel Har-Peled
We show that there is no $(1+\eps)$-approximation algorithm for the problem of covering points in the plane by minimum number of fat triangles of similar size (with the minimum ang…
Randomized Incremental Construction of Compressed Quadtrees
Sariel Har-Peled
We present a simple randomized incremental algorithm for building compressed quadtrees. The resulting algorithm seems to be simpler than previously known algorithms for this task.
Approximating Spanning Trees with Low Crossing Number
Sariel Har-Peled
We present a linear programming based algorithm for computing a spanning tree of a set of points in , such that its crossing number is $O(\min(t \log n, n^{1-1/d…