Papers
Notes ,
Other publications ,
Talks ,
Gallery .
DBLP
:
GScholar
:
arXiv
:
ORCID
"As far as I'm concerned they are all engineers. All of them."
-- Yehuda Amichai, from A Pity. We Were Such a Good Invention .
Book
Geometric approximation algorithms .
Manuscripts
Revisiting random points: Combinatorial complexity and algorithms,
with E. Harb.
Computing optimal kernels in two dimensions , with P. K. Agarwal.
Sparsifying disk intersection graphs for reliable
connectivity ,
with E. Robson .
Local spanners revisited , with
S. Ashur .
On clusters that are separated but large , with J. Rogge.
On the various depths of lines and planes, with V. Leo.
How packed is it,
really? , with T. Zhou.
Papers in Conferences
Halving by a thousand cuts or punctures ,
with D.W. Zheng. To appear in SODA 2023.
On the number of incidences when avoiding a bipartite clique ,
with T. M. Chan. To appear in SODA 2023.
Approximation algorithms for maximum matchings in geometric
intersection graphs , with E. Yang. In SoCG 22.
Improved
approximation algorithms for Tverberg partitions , with
T. Zhou. In ESA 2021.
On Undecided LP, Clustering and Active Learning , with
S. Ashur.
In SoCG 21.
Submodular clustering in low dimensions ,
with A. Backurs. In SWAT 20.
Approximate sparse linear regression , with
P. Indk and S. Mahabadi.
In ICALP 2018
.
Proximity in the age of distraction:
Robust approximate nearest neighbor search , with S. Mahabadi.
In SODA 17
.
Towards tight bounds for the streaming
set cover problem ,
with P. Indyk, S. Mahabadi, and A. Vakilian.
In PODS 16
.
Papers in Journals
In submission
A note on Stabbing Convex Bodies with Points, Lines and Flats , with
M. Jones.
In SoCG 21.
Few cuts meet many point sets ,
with M. Jones.
Did not appear yet
Reliable spanner for metric spaces ,
with M. Mendel and D. Oláh.
To appear in TALG.
In SoCG 21
.
Published
Optimal Algorithms for Geometric Centers and Depth ,
with T. M. Chan and M. Jones. SICOMP 51(3): 627-663 (2022).
Conference version is "Fast Algorithms for Geometric
Consensuses", with M. Jones, in SoCG 20.
Sometimes reliable
spanners of almost linear size ,
with K. Buchin and D. Oláh. In ESA 20. JoCG 13(1): 178-196 (2022).
The maximum-level vertex in an arrangement of lines ,
with S. Halperin, K. Mehlhorn, E. Oh, and M. Sharir.
In DCG 67, 439–461 (2022).
Sampling near
neighbors in search for fairness
(extended version ),
with
M. Aumüller, S. Har-Peled, S. Mahabadi, R. Pagh, F. Silvestri.
In CACM, 2022.
Also in TDS, SIGMOD Rec., and
NeuroIPS.
Stabbing pairwise intersecting disks by five points , WITH
H. Kaplan, W. Mulzer, L. Roditty, P. Seaworthy, M. Sharir, and M.
Willert.
Discrete Math 344(7), 2021.
Active learning a convex body in low dimensions with
M. Jones and S. Rahul.
In Algorithmica 83(6): 1885-1917, 2021
.
Also in ICALP 20 [talk ].
.
Smallest k -enclosing rectangle revisited ,
with T. M. Chan.
In DCG 66(2): 769-791, 2021.
.
Also in SoCG 19
.
Journey to the center of the point set ,
with M. Jones.
TALG
17(1): 9:1-9:21, 2021
.
Also
in SoCG 19
.
Approximate greedy clustering
and distance selection for graph metrics , with D. Eppstein and
A. Sidiropoulos. In JoCG 11(1): 629-652 (2020).
A spanner for the day after . with K. Buchin,
and D. Olah.
DCG, 64(4): 1167-1191, 2020
.
Also in SoCG 19
.
Grid peeling and the affine
curve-shortening flow , with
D. Eppstein, and G. Nivasch.
Exper. Math. 29:3, 306-316, 2020
.
Also in ALENEX 2018
.
Edge estimation with independent set oracles ,
with P. Beame,
S. N. Ramamoorthy, C. Rashtchian,
and
M. Sinha.
In TALG 16(4): 52:1-52:27, 2020
.
Also in ITCS 18
.
On locality-sensitive orderings and
their applications , with T.M. Chan and M. Jones.
SICOMP 49(3), 583–600, 2020.
Also in ITCS 19.
Decomposing
arrangements of hyperplanes: VC-dimension, combinatorial dimension,
and point location ,
with E. Ezra, H. Kaplan, and M Sharir.
DCG 64: 109–173, 2020.
On separating points by lines ,
with M. Jones.
DCG 63(3): 705–730, 2020
.
Also in SODA 18
.
Sparse approximation via generating
point sets , with A. Blum and B. Raichel.
In TALG 15(3): 32:1-32:16, 2019
.
Also in SODA 16
.
Approximation schemes for independent
set and sparse subsets of polygons , with
A. Adamaszek and A. Wiese.
In JACM 66(4): 29:1--29:40, 2019.
Partial conference version:
Quasi-polynomial time approximation scheme
for sparse subsets of polygons .
In SoCG 14
.
Robust proximity search for balls using
sublinear space , with N. Kumar.
In Algorithmica 80(1): 279-299, 2018
.
Also in FSTTCS 2014
.
Approximation algorithms for
polynomial-expansion and low-density graphs ,
with K. Quanrud.
SICOMP, 46(6): 1712–1744, 2017
Also in ESA 15
.
Geometric packing under non-uniform
constraints , with A. Ene and B. Raichel.
In SICOMP, 46(6): 1745–1784, 2017
Also in SoCG 12.
Approximating the k-level in
three-dimensional plane arrangements ,
with H. Kaplan and M. Sharir.
In A Journey
Through Discrete Mathematics: A Tribute to Jiří Matoušek .
Also in SODA 16
.
Convex hulls under uncertainty ,
with P.K. Agarwal, S. Suri, H. Yildiz, and W. Zhang.
In Algorithmica 79(2): 340-367, 2017
.
Also in ESA 14
.
Approximating the maximum
overlap of polygons under translation , with S. Roy.
In Algorithmica 78(1): 147-165,2017
.
Also in ESA 14
.
Nearest neighbor searching under
uncertainty II , with P. K. Agarwal, B. Aronov,
J. M. Phillips, K. Yi, and W. Zhang.
TALG 13(1): 3:1-3:25, 2016
.
Also in PODS 13
.
From proximity to utility: A Voronoi
partition of Pareto optima , with
H.-C. Chang and B. Raichel.
In DCG 56(3): 631-656, 2016
.
Also in SoCG 15
.
Space exploration via proximity
search , with
N. Kumar, D. Mount, and B. Raichel.
In DCG 56(2): 357-376, 2016
.
Also in SoCG 15
.
On the expected complexity of Voronoi
diagrams on terrains , with A. Driemel and B. Raichel.
In TALG 12(3): 37, 2016
.
Also in SoCG 12.
How to walk your dog in the mountains
with no magic leash ,
with A. Nayyeri, M. Salavatipour, and A. Sidiropoulos.
In DCG 55(1): 39-73, 2016
.
Also in SoCG 12.
Shortest path in a polygon using
sublinear space .
JoCG 7(2):19–45, 2016
.
Also in SoCG 15
.
On the number of edges of
fan-crossing free graphs , with O. Cheong, H. Kim, and
H.S. Kim.
Algorithmica 73(4): 673–695, 2015.
Also in ISAAC 2013.
Net and prune: A linear
time algorithm for euclidean distance problems , with
B. Raichel.
JACM 62(6): 44:1–44:35, 2015
.
Also in STOC 2013.
Approximating minimization diagrams and
generalized proximity search , with N. Kumar.
SICOMP 44(4): 944-974, 2015.
Also in FOCS 2013.
On the complexity of randomly
weighted Voronoi diagrams , with B. Raichel.
DCG 53(3): 547-568, 2015
.
Also in SoCG 14.
Down the rabbit hole: Robust proximity
search in sublinear space , with N. Kumar.
SICOMP 43(4): 1486-1511, 2014
.
Also in FOCS 2012.
Union of random Minkowski sums and
network vulnerability analysis , with P. K. Agarwal,
H. Kaplan, and M. Sharir.
DCG 52(3): 551-582, 2014
.
Minimum convex partitions and maximum empty
polytopes , with A. Dumitrescu and C. D. Tóth.
JoCG 5(1): 86-103 (2014).
Also in SWAT 2012.
The Fréchet distance revisited and
extended ,
with B. Raichel.
TALG 10 (1):3:1-3:22, 2014.
Also in SoCG 11.
Jaywalking your dog - the Fréchet
distance with shortcuts for realistic curves with noise ,
with A. Driemel.
SICOMP 42 (5), 1830-1866, 2013.
Also in SODA 12.
Embeddings of surfaces, curves, and
moving points in euclidean space
, with
P.K. Agarwal and H. Yu.
SICOMP 42 (2), 442-458, 2013.
Also in SoCG 07.
Peeling the grid , with
B. Lidicky.
SIDMA 27
(2): 650-655, 2013.
[BIB ]
Approximate nearest neighbor
search for low dimensional queries , with N. Kumar.
SICOMP 42 (1), 138-159, 2013.
Also in SODA 2011.
On the multi-cover problem in
geometric settings , with K. Clarkson and C. Chekuri.
TALG 9 (1), 2012.
Also in SoCG 09.
Approximate nearest neighbor: Towards
removing the curse of dimensionality , with P. Indyk and
R. Motwani.
ToC 8:321-350, 2012. (Special issue in the memory of
Rajeev Motwani.)
Based partially on
A replacement for
Voronoi diagrams of near linear size , in FOCS
01.
Approximation algorithms for
maximum independent set of pseudo-disks , with T. M. Chan.
DCG 48 (2): 373-392, 2012.
Also in SoCG 09.
Weighted geometric set cover
problems revisited ,
with M. Lee.
JoCG 3 (1): 65--85, 2012.
Approximating the Fréchet distance
for realistic curves in near linear time , with A. Driemel
and C. Wenk.
DCG 48 (1): 94–127, 2012.
Also in SoCG 10.
New constructions of SSPDs and their
applications , with M. A. Abam.
CGTA 45 (5–6):200--214, 2012.
Also in SoCG 10.
Relative (p,eps)-approximations in
geometry , with M. Sharir.
DCG 45 (3): 462-496, 2011.
Also in SoCG 07 (as a merged paper).
Hausdorff distance under
translation for points, disks,
and balls , with P.K. Agarwal, M. Sharir and Y. Wang.
In TALG, 6(4):1--26, 2010.
Also in SoCG 03.
On approximating the depth and related problems ,
with B. Aronov.
SICOMP 38(3): 899-921 (2008).
Also in SODA 05.
Robust shape fitting via peeling and grating coresets ,
with P.K. Agarwal and H. Yu.
DCG 39 (1-3): 38-58 (2008).
Also in SODA 06.
The orienteering Problem in the plane
revisited , with Ke Chen.
SICOMP 38: (1) 385--397, 2008.
Also in SoCG 06.
On finding a guard that sees most and
a shop that sells most , with O. Cheong and A. Efrat.
DCG 37 (4): 545-563 (2007).
Also in SODA 04.
Smaller coresets for
k-median and k-means clustering , with A. Kushal.
DCG 37 (1): 3-19, 2007.
Also on SoCG 05.
How to get close to the median
shape .
In CGTA 36 (1): 39-51, 2007.
Also in SoCG 06.
On the least median square problem ,
with J. Erickson and D. Mount.
DCG 36 (4): 593-607, 2006.
Also in SoCG 04.
Fast construction of nets
in low dimensional
metrics, and their applications , with M. Mendel. In
SICOMP 35: (5) 1148--1184, 2006.
Also in SoCG 05.
Guarding galleries and
terrains , with A. Efrat. In IPL 100: (6) 238--245,
2006.
On the Fermat-Weber center of a convex object ,
with P. Carmi, and M. J. Katz.
In CGTA 32: (3) 188-195, 2005.
"On conflict-free coloring of
points and simple
regions in the plane , with S. Smorodinsky.
DCG 34 (1):40-70, 2005.
Also in SoCG 03.
Near-linear time approximation
algorithms for curve simplification in two and three
dimensions ,
with P.K. Agarwal, N. Mustafa, and Y. Wang,
Algorithmica, 42:203-219, 2005.
Also in ESA 02, 29-41.
Generalization bounds for the
area Under the ROC curve , with S. Agarwal, T. Graepel,
R. Herbrich, and Dan Roth.
J. Mach. Learn. Research,
6:393--425, Apr 2005.
Based partially on "A Uniform Convergence
Bound for the Area Under the ROC Curve , with S. Agarwal
and D. Roth. In AISTAT 05.
Geographic quorum systems
approximations ,
with P. Carmi, S. Dolev, M. J. Katz, and M. Segal. In
Algorithmica, 41 (4): 233--244, 2005.
How fast is the k -means method? ", with B. Sadri.
In Algorithmica, 41(3):185--202, 2005.
Also in SODA 05.
Approximating k-hop minimum-spanning trees , with
Ernst Althaus,
Stefan Funke,
Jochen Konemann,
Edgar A. Ramos,
and
Martin Skutella.
In Oper. Res. Lett., 33(2):115--120, March 2005.
Fast algorithms for computing the
smallest k-enclosing disc ,
with S. Mazumdar.
In Algorithmica, 41(3):147--157, 2005. Also in ESA 03.
Shape fitting with outliers ,
with Y. Wang.
In SICOMP 33(2):269-285, 2004. Also in SoCG 03.
High-dimensional shape fitting in
linear time ,
with K. R. Varadarajan.
DCG 32 (2): 269-288, 2004.
Also in SoCG 03.
Optimally cutting a surface into a disk , with
J. Erickson.
DCG 31 (1): 37-59, 2004.
Also in SoCG 2002.
The one-round Voronoi game , with
O. Cheong, N. Linial, and J. Matousek.
DCG 31 (1):125-138, 2004.
Also in SoCG 2002.
Reporting intersecting pairs
of polytopes in two and three dimensions , with
P.K. Agarwal, M. de Berg, M.H. Overmars, M. Sharir and
J. Vahrenhold.
CGTA 23:195--208 (2002).
Also in WADS 01.
Clustering motion .
DCG 31 (4): 545--565, 2004.
Also in FOCS 01.
Approximating extent measure of
points with P.K. Agarwal and
K. R. Varadarajan. In
J. ACM,
51 (4): 606-635, 2004.
Based on
"Approximate shape fitting via linearization
, and
"Maintaining the approximate extent measures of
moving points .
Computing the penetration depth of two
convex polytopes in 3D , with
P.K. Agarwal,
L.J. Guibas,
A. Rabinovitch, and
M. Sharir, in Nordic J. Comput. 3:(7), 227-240 (2000).
Also in SWAT 2000.
Computing approximate
shortest paths on convex polytopes ,
with P.K. Agarwal, and
M. Karia,
in Algorithmica 33 (2), 227-242, 2002. Also in
SoCG 2000.
Online point location in planar
arrangements and its applications , with M. Sharir.
DCG 26 (1): 19-40, 2001.
Also in SODA 01.
New similarity measures between polylines
with applications to morphing and polygon sweeping , with
A. Efrat, L.J. Guibas, J.S.B. Mitchell, and T.M. Murali.
DCG 28:535-569 (2002).
Based on
"Morphing between polylines and
"Sweeping simple polygons with a chain
of guards .
Routing with a clue , with
A. Bremler and Y. Afek, in Trans. on Networking,
9(6):693--705, 2001. Also in SIGCOMM '99.
An experimental study of on-line methods for zone
construction in arrangements of lines in the plane ,
in IJCGA, with D. Halperin, C, Linhart, and I. Hanniel.
Also appeared as
"On-line zone construction in arrangements of lines in the
plane", with
Y. Aharoni, D. Halperin, I. Hanniel, C. Linhart, in
WAE 99.
Taking a walk in a planar
arrangement , in
SICOMP 30 (4)
1341-1367, 2000. Also in
FOCS 99.
Approximation and exact algorithms for minimum-width
annuli and shells ,
with
P.K. Agarwal,
B. Aronov, and
M. Sharir.
DCG 24(4): 687--705, 2000.
Also in SoCG '99.
Efficiently approximating
the minimum-volume bounding box
of a point set in three dimensions , with G. Barequet,
in J. Algorithms 38 (1): 91-109, 2001. Also in SODA 99.
Some variants of polygon
containment and minimum Hausdorff distance under translation are
3sum -Hard , with G. Barequet, in IJCGA. Also
in SODA 99.
Constructing planar cuttings in theory and
practice . SICOMP 29 (6) 2016-2039, 2000.
Also in SoCG '98.
Constructing approximate shortest
path maps in three dimensions , in SICOMP, 28 (4), 1182-1197
(1999). Also in SoCG '98.
Approximate shortest-path and
geodesic diameter on convex polytopes in three dimensions .
DCG, 21: 217-231 (1999).
Also in SoCG '97.
An output sensitive algorithm
for discrete convex hulls , CGTA, 10 (1998) 125-138.
Also in SoCG '98.
Approximating
shortest paths on a convex polytope in three
dimensions , with
P.K. Agarwal,
M. Sharir, and
K.R. Varadarajan.
In J. ACM,
44 (1997), 567-584.
Also in SoCG '96.
Multicolor combination
lemma , in
CGTA, 12:155-176 (1999). (Master thesis.)
A List of my Survey:
Geometric approximation via coresets , with
P.K. Agarwal, and K.R. Varadarajan.