Home | Bookmarks | Papers | Blog |

Papers, Research

- Proximity in the age of distraction: Robust approximate
nearest neighbor search.

Talk in CG seminar in Tel-Aviv Univ. 11/9/2016. - Beyond planarity: On geometric intersection graphs, 1/11/16. Presented in SODA 2016.
- Quasi-Polynomial Time Approximation Scheme for Sparse Subsets of Polygons - Talk in discrete math seminar in KAIST. 6/2/2014.
- Finding
haystacks (and similar structures) in geometry

In Workshop: Barriers in Computational Complexity II.

August 29, 2010. Princeton, NJ.

(The talk is different than the one given in TAU.) - Summer school - Madalgo, Aarhus, Denmark. August 16-19, 2010.
- New
Constructions of SSPDs and their Applications.

15-June-2010, in SoCG 2010, Snowbird, Utah.

[pdf] source. - Finding haystacks (and similar structures) in
geometry.

23-May-2010. in SharirFest, Tel-Aviv University.

[pdf] source. - Approximating the Frechet Distance for Realistic Curves in Near Linear Time.
- Approximation
Algorithms for Maximum Independent Set of Pseudo-Disks

[slides].

June 10, 2009, Aarhus, Denmark. SoCG 09. - On set cover in geometric settings
[PDF].

A survey on geometric set covering problem and what is known about it.

- On Approximate Halfspace Range Counting and Relative
eps-Approximations, with B. Aronov and M. Sharir. SoCG
07.

Paper (unmerged version), Slides, and slides source. - Embeddings of Surfaces, Curves, and Moving Points in
Euclidean Space, with P. Agarwal and H. Yu. SoCG 07.

Paper, slides, and slides source. - Fast Construction of Nets in Low Dimensional Metrics,
and Their Applications, with Manor Mendel. SoCG
05.

Paper, slides and slides source. - Smaller Coresets for
**k**-Median and**k**-Means Clustering, with Akash Kushal. SoCG 05. Paper, slides, and slides source. - On Coresets
and Shape Fitting in High Dimensions. In IST seminar in
CalTech.

Slides, slides source and abstract. - The coresets omnibus. In EWCG 2005 spring school.
- How fast is the k-means Method?, with B. Sadri. In SODA 05.
- On Approximating the Depth and Related Problems, with B. Aronov. In SODA 05.
- Coresets for k-Means and k-Median Clustering and their Applications, 2004.
- On Finding a Guard that Sees Most and a Shop that Sells Most, 2004.
- On Coresets and Shape Fitting in High Dimensions, 2003.
- Job talk. 2000.

SoCG talk (6/10/2014): black, and white.

"The problem received the title of `Buridan's sheep.' The biological code was taken from a young merino sheep, by the Casparo-Karpov method, at a moment when the sheep was between two feeding troughs full of mixed fodder. This code, along with additional data about sheep in general, was fed into CODD. The machine was required: a) to predict which trough the merino would choose, and b) to give the psychophysiological basis for this choice."

-- The mystery of the hind leg, Arkady and Boris Strugatsky

Last modified: Mon Jun 16 07:02:02 CDT 2014