272 citations · 371 across the 32 of their papers we have counts for
5 papers · 2 filters
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…
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…