research
∙
08/01/2023
Approximately: Independence Implies Vertex Cover
We observe that a (1-)-approximation algorithm to Independent Set, th...
share
research
∙
06/03/2023
On the Budgeted Hausdorff Distance Problem
Given a set P of n points in the plane, and a parameter k, we present...
research
∙
06/02/2023
No-dimensional Tverberg Partitions Revisited
Given a set P ⊂^d of n points, with diameter , and a parameter ∈ (0,1), ...
research
∙
01/06/2023
On the Width of the Regular n-Simplex
Consider the regular n-simplex Δ_n - it is formed by the convex-hull of ...
research
∙
08/24/2022
Halving by a Thousand Cuts or Punctures
For point sets P_1, …, P_, a set of lines L is halving if any face of t...
research
∙
08/07/2022
Revisiting Random Points: Combinatorial Complexity and Algorithms
Consider a set P of n points picked uniformly and independently from [0,...
research
∙
07/14/2022
Computing Optimal Kernels in Two Dimensions
Let P be a set of n points in ℝ^2. A subset C⊆ P is an ε-kernel of P if ...
research
∙
01/05/2022
Approximation Algorithms for Maximum Matchings in Geometric Intersection Graphs
We present a (1- ε)-approximation algorithms for maximum cardinality mat...
research
∙
01/05/2022
Sparsifying Disk Intersection Graphs for Reliable Connectivity
The intersection graph induced by a set of n disks can be dense. It is ...
research
∙
01/05/2022
Local Spanners Revisited
For a set of points P ⊆ℝ^2, and a family of regions , a local t-spanner ...
research
∙
12/29/2021
On the Number of Incidences when Avoiding the Klan
Given a set of points P and a set of regions 𝒪, an incidence is a pair (...
research
∙
10/27/2021
On Competitive Permutations for Set Cover by Intervals
We revisit the problem of computing an optimal partial cover of points b...
research
∙
06/09/2021
On Clusters that are Separated but Large
Given a set P of n points in ^d, consider the problem of computing k sub...
research
∙
05/22/2021
How Packed Is It, Really?
The congestion of a curve is a measure of how much it zigzags around loc...
research
∙
03/16/2021
On Undecided LP, Clustering and Active Learning
We study colored coverage and clustering problems. Here, we are given a ...
research
∙
01/26/2021
Sampling a Near Neighbor in High Dimensions – Who is the Fairest of Them All?
Similarity search is a fundamental algorithmic primitive, widely used in...
research
∙
07/20/2020
Stabbing Convex Bodies with Lines and Flats
We study the problem of constructing weak -nets where the stabbing eleme...
research
∙
07/19/2020
Shortest Secure Path in a Voronoi Diagram
We investigate the problem of computing the shortest secure path in a Vo...
research
∙
07/17/2020
Reliable Spanners for Metric Spaces
A spanner is reliable if it can withstand large, catastrophic failures i...
research
∙
07/17/2020
Improved Approximation Algorithms for Tverberg Partitions
Tverberg's theorem states that a set of n points in ^d can be partiti...
research
∙
04/11/2020
Submodular Clustering in Low Dimensions
We study a clustering problem where the goal is to maximize the coverage...
research
∙
03/01/2020
The Maximum-Level Vertex in an Arrangement of Lines
Let L be a set of n lines in the plane, not necessarily in general posit...
research
∙
12/07/2019
Covering Polygons by Min-Area Convex Polygons
Given a set of disjoint simple polygons σ_1, ..., σ_n, of total complexi...
research
∙
12/03/2019
Fast Algorithms for Geometric Consensuses
Let P be a set of n points in ^d in general position. A median hyperplan...
research
∙
12/03/2019
Sometimes Reliable Spanners of Almost Linear Size
Reliable spanners can withstand huge failures, even when a linear number...
research
∙
12/02/2019
Proof of Dudley's Convex Approximation
We provide a self contained proof of a result of Dudley [Dud64] which sh...
research
∙
10/16/2019
Some Geometric Applications of Anti-Chains
We present an algorithmic framework for computing anti-chains of maximum...
research
∙
06/06/2019
Near Neighbor: Who is the Fairest of Them All?
In this work we study a fair variant of the near neighbor problem. Namel...
research
∙
03/15/2019
Smallest k-Enclosing Rectangle Revisited
Given a set of n points in the plane, and a parameter k, we consider the...
research
∙
03/08/2019
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...
research
∙
11/16/2018
A Spanner for the Day After
We show how to construct (1+ε)-spanner over a set P of n points in R^d t...
research
∙
10/30/2018
Coresets for k-Means and k-Median Clustering and their Applications
In this paper, we show the existence of small coresets for the problem...
research
∙
10/03/2018
Two (Known) Results About Graphs with No Short Odd Cycles
Consider a graph with n vertices where the shortest odd cycle is of leng...
research
∙
09/28/2018
On Locality-Sensitive Orderings and their Applications
For any constant d and parameter ε > 0, we show the existence of (roughl...
research
∙
08/09/2018
Few Cuts Meet Many Point Sets
We study the problem of how to breakup many point sets in R^d into small...
research
∙
08/08/2018
Separators for Planar Graphs that are Almost Trees
We prove that a connected planar graph with n vertices and n+μ edges has...
research
∙
01/09/2018
Stabbing pairwise intersecting disks by five points
We present an O(n) expected time algorithm and an O(n n) deterministic ...
research
∙
12/08/2017
How to Net a Convex Shape
We revisit the problem of building weak -nets for convex ranges over...
research
∙
12/08/2017
Decomposing arrangements of hyperplanes: VC-dimension, combinatorial dimension, and point location
We re-examine parameters for the two main space decomposition technique...
research
∙
11/20/2017
Edge Estimation with Independent Set Oracles
We study the problem of estimating the number of edges in a graph with a...
research
∙
10/11/2017
Grid peeling and the affine curve-shortening flow
In this paper we study an experimentally-observed connection between two...
research
∙
09/23/2017
A Simple Algorithm for Computing a Cycle Separator
We present a linear time algorithm for computing a cycle separator in a ...
research
∙
06/06/2017
On Separating Points by Lines
Given a set P of n points in the plane, its separability is the minimum ...
research
∙
07/02/2002