
On Clusters that are Separated but Large
Given a set P of n points in ^d, consider the problem of computing k sub...
read it

How Packed Is It, Really?
The congestion of a curve is a measure of how much it zigzags around loc...
read it

On Undecided LP, Clustering and Active Learning
We study colored coverage and clustering problems. Here, we are given a ...
read it

Sampling a Near Neighbor in High Dimensions – Who is the Fairest of Them All?
Similarity search is a fundamental algorithmic primitive, widely used in...
read it

Stabbing Convex Bodies with Lines and Flats
We study the problem of constructing weak nets where the stabbing eleme...
read it

Shortest Secure Path in a Voronoi Diagram
We investigate the problem of computing the shortest secure path in a Vo...
read it

Reliable Spanners for Metric Spaces
A spanner is reliable if it can withstand large, catastrophic failures i...
read it

Improved Approximation Algorithms for Tverberg Partitions
Tverberg's theorem states that a set of n points in ^d can be partiti...
read it

Submodular Clustering in Low Dimensions
We study a clustering problem where the goal is to maximize the coverage...
read it

The MaximumLevel Vertex in an Arrangement of Lines
Let L be a set of n lines in the plane, not necessarily in general posit...
read it

Covering Polygons by MinArea Convex Polygons
Given a set of disjoint simple polygons σ_1, ..., σ_n, of total complexi...
read it

Fast Algorithms for Geometric Consensuses
Let P be a set of n points in ^d in general position. A median hyperplan...
read it

Sometimes Reliable Spanners of Almost Linear Size
Reliable spanners can withstand huge failures, even when a linear number...
read it

Proof of Dudley's Convex Approximation
We provide a self contained proof of a result of Dudley [Dud64] which sh...
read it

Some Geometric Applications of AntiChains
We present an algorithmic framework for computing antichains of maximum...
read it

Near Neighbor: Who is the Fairest of Them All?
In this work we study a fair variant of the near neighbor problem. Namel...
read it

Smallest kEnclosing Rectangle Revisited
Given a set of n points in the plane, and a parameter k, we consider the...
read it

Active Learning a Convex Body in Low Dimensions
Consider a set P ⊆R^d of n points, and a convex body C provided via a se...
read it

A Spanner for the Day After
We show how to construct (1+ε)spanner over a set P of n points in R^d t...
read it

Coresets for kMeans and kMedian Clustering and their Applications
In this paper, we show the existence of small coresets for the problem...
read it

Two (Known) Results About Graphs with No Short Odd Cycles
Consider a graph with n vertices where the shortest odd cycle is of leng...
read it

On LocalitySensitive Orderings and their Applications
For any constant d and parameter ε > 0, we show the existence of (roughl...
read it

Few Cuts Meet Many Point Sets
We study the problem of how to breakup many point sets in R^d into small...
read it

Separators for Planar Graphs that are Almost Trees
We prove that a connected planar graph with n vertices and n+μ edges has...
read it

Stabbing pairwise intersecting disks by five points
We present an O(n) expected time algorithm and an O(n n) deterministic ...
read it

How to Net a Convex Shape
We revisit the problem of building weak nets for convex ranges over...
read it

Decomposing arrangements of hyperplanes: VCdimension, combinatorial dimension, and point location
We reexamine parameters for the two main space decomposition technique...
read it

Edge Estimation with Independent Set Oracles
We study the problem of estimating the number of edges in a graph with a...
read it

Grid peeling and the affine curveshortening flow
In this paper we study an experimentallyobserved connection between two...
read it

A Simple Algorithm for Computing a Cycle Separator
We present a linear time algorithm for computing a cycle separator in a ...
read it

On Separating Points by Lines
Given a set P of n points in the plane, its separability is the minimum ...
read it

Optimally cutting a surface into a disk
We consider the problem of cutting a set of edges on a polyhedral manifo...
read it
Sariel HarPeled
is this you? claim profile