Papers
Notes ,
Other publications ,
Talks ,
GScholar ,
DBLP ,
arXiv ,
Gallery .
"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
A simple algorithm for
computing a cycle separator , with A. Nayyeri.
Papers in Conferences
Sometimes reliable
spanners of almost linear size ,
with K. Buchin and D. Olah. Appeared in ESA 20.
Submodular clustering in low dimensions ,
with A. Backurs. To appear in SWAT 20.
Fast Algorithms for Geometric Consensuses
with M. Jones. In SoCG 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
Active learning a convex body in low dimensions with
M. Jones and S. Rahul.
In ICALP 20 [talk ].
The maximum-level vertex in an arrangement of lines ,
with S. Halperin, K. Mehlhorn, E. Oh, and M. Sharir.
Few cuts meet many point sets ,
with M. Jones.
Journey to the center of the point set ,
with M. Jones.
In SoCG 19
.
Approximate greedy clustering
and distance selection for graph metrics , with D. Eppstein and
A. Sidiropoulos.
Did not appear yet
Smallest k -enclosing rectangle revisited ,
with T. M. Chan.
Accepted to DCG.
In SoCG 19
.
Edge estimation with independent set oracles ,
with P. Beame,
S. N. Ramamoorthy, C. Rashtchian,
and
M. Sinha.
To appear in TALG.
In ITCS 18
.
A spanner for the day after . with K. Buchin,
and D. Olah.
In SoCG 19
.
Accepted to DCG.
Grid peeling and the affine
curve-shortening flow , with
D. Eppstein, and G. Nivasch.
In Exper. Math.
Also in ALENEX 2018
.
Published
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
doi .
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.
Older papers in conferences
No journal version is planned
Separating a Voronoi diagram via local
search ,
with V. V. S. P. Bhattiprolu.
In SoCG 16
.
Euclidean spanners in high
dimensions ,
with P. Indyk and A. Sidiropoulos.
In SODA 2013.
Approximate distance queries in
sparse graphs , with R. Agarwal and P. B. Godfrey.
In INFOCOM 2011.
Fréchet distance for curves,
revisited , with B. Aronov, C. Knauer, Y. Wang, and C. Wenk. In
ESA 06
.
Maximum margin coresets for active and
noise tolerant learning , with D. Roth and D. Zimak. In
IJCAI 07.
Coresets for discrete integration and
clustering . In FSTTCS 06.
Range medians , with S.
Muthukrishnan. In ESA 08.
Approximation algorithms for two optimal location problems in
sensor networks , with A. Efrat and J. S. B. Mitchell. In
Broadnets 2005.
A time-optimal Delaunay refinement
algorithm in two dimensions , with A. Ungor. In SoCG 05.
Coresets for k-means and k-median
clustering and their applications , with S. Mazumdar. In STOC
04.
Constraint classification: A new approach to
multiclass classification and ranking , with D. Roth and D.
Zimak, in NIPS 2002.
Projective clustering in high dimensions
using coresets , with K. Varadarajan, in SoCG 2002.
Approximate clustering via coresets ,
with M. Badoiu and P. Indyk, in STOC 2002.
No coreset, no cry . Appeared in FSTTCS
04.
Efficient algorithms for shared camera
control , with V. Koltun, D. Song and K. Goldberg, in SoCG
03.
On generalization bounds,
projection profile, and margin distribution , with A. Garg
and D. Roth. In ICML 2002.
STAR-Tree: An efficient self-adjusting
index for moving objects , with P.K. Agarwal and
C.M. Procopiuc. In ALENEX 02.
A practical approach for computing the
diameter of a point-set
, in SoCG 01.
Occlusion culling for fast
walkthrough in urban areas . with Y. Wang and
P.K. Agarwal. In Eurographics 01.
When crossings count - approximating the
minimum spanning tree , with P. Indyk, in SoCG 2000.
Journal version appeared without me being involved
Results on k-sets and j-facets
via continuous motion arguments , with A. Andrzejak,
B. Aronov, R. Seidel and E. Welzl, in SoCG '98.
Fly cheaply: On the minimum
fuel-consumption problem , with A. Efrat, in SoCG '98.
PhD Thesis
Geometric approximation algorithms
and
randomized algorithms for planar arrangements .
Some other publications
Staying in the middle: Exact and approximate medians in
R^{1} and R^{2} for moving
points , with P.K. Agarwal, M. de Berg, J. Gao,
and L. J. Guibas. CCCG 05.
The complexity of a single
face of a Minkowski sum
with T. M. Chan, B. Aronov, D. Halperin and
J. Snoeyink, in CCCG 95, 91--96 .
PS :
PDF .
Conferences
SoCG 15
- Eindhoven, Netherlands (3:59/151) [39%].
SoCG 14
- Kyoto, Japan (2:60/175) [34%].
SoCG 13 -
Rio, Brazil. On PC.
SoCG 12 - UNC, North
Carolina (3:44/126) [35%].
SoCG 11 - Paris, France
(1:55/145) [38%].
SoCG 10 - Snowbird,
Utah (2:47/145) [32.4%].
SoCG 09 -
Aarhus, Denmark. (2:44/170) [25.8%].
SoCG
08 - UMD, Washington DC, USA. On PC - no papers.
SoCG 07
- Gyeongju, South-Korea (2:45/139) [32.3%].
SoCG 06
- Sedona, Arizona (2:54/138) [39.1%].
SoCG 05 - Pisa, Italy
(3:41:140) [29.2%].
SoCG 04
- New York City, USA (1:49:147) [33.3%]
SoCG 03
- San Diego, USA (5:42:118) [35.5%]
SoCG
02 - Barcelona (3:35/104) [33.6%].
SoCG 01 - Boston.
(AT 1:14/35),
SoCG 2000
- Hong Kong, (AT 1:16/50, TT 1:25/73)
SoCG 1999 -
Miami, Florida. (TT 1:27/61)
SoCG 1998 -
Minneapolis, Minnesota.
(AT 2:19/53, TT 3:25/57)
SoCG 1997 - Nice, France. (TT 1: 27/92)
SoCG 1996
- Philadelphia, Pennsylvania.
(1: 39/93) [41.9%]
STOC 2013 - Palo
Alto (1: 100/360).
STOC 2004
- Chicago (1:71/273)
STOC
2002 (1:91/287)
FOCS 2013
- Berkeley. (1:??/???).
FOCS 2012
- New Jersey. (1:79/248).
FOCS 2001 - Las
Vegas.
(3:63/214),
FOCS 1999 - New
York City (1: 67/218)
SIGCOMM
'99 (1: 24/190)
WAE 99
(1: 24/46)
WADS
2001 (1:40/89)
SWAT 2000
SODA 2013 -
New Orleans. (1:135/454) [30%]
SODA 2012 - Kyoto,
Japan.
(1:138/513) [27%]
SODA 2011 - SF.
(1:136/452) [30%]
SODA 2006 - Miami
(1:135/432)
SODA 2005 - Vancouver
(2:135/487)
SODA 2004 - New
Orleans (1:135/454)
SODA 2001
(3:95/224).
SODA 2000
(1:123/335),
SODA 1999
(1 short, 1 long).
AISTAT
05 : (1:58/150)
PODS 2013: (1:24/97).
ALENEX 2002: (1:15/34)
WADS 01: 1
ESA 02:
ESA 03: (1:46/119)
ESA 06: (1:52/215)
ESA 15: (1:85/320: 26%)
FSTTCS 04: (1:38/176)
FSTTCS 06:
Broadnets 2005 : (1:49/100).
Journals
JACM: 2
SICOMP: 10
DCG: 15
TALG: 1
JCG : 1
CGTA: 4
Nordic J. Comput.: 1
Algorithmica: 4
Trans. on Networking: 1
J. Algorithms : 1
ORL -
Operation Research Letters
orcid.org/0000-0003-2638-9635
Last modified: Tue 2020-09-22 15:02:19 UTC 2020 by Sariel Har-Peled