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
On Clusters that are Separated but large , with J. Rogge.
Shortest Secure Path
in a Voronoi Diagram , with R. Varadharajan
On the various depths of lines and planes, with V. Leo.
How Packed Is It, Really? with T. Zhou.
Papers in Conferences
Improved
approximation algorithms for Tverberg partitions , with
T. Zhou. To appear in ESA 2021.
Stabbing Convex Bodies with Lines and Flats , with
M. Jones.
In SoCG 2021.
On Undecided LP, Clustering and Active Learning , with
S. Ashur.
In SoCG 2021.
Reliable spanner for metric spaces ,
with M. Mendel and D. Oláh.
To appear in SoCG 2021.
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. Appeared 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
Optimal Algorithms for Geometric Centers and Depth ,
with T. M. Chan and M. Jones. In SoCG 20.
Active learning a convex body in low dimensions with
M. Jones and S. Rahul.
In ICALP 20 [talk ].
Few cuts meet many point sets ,
with M. Jones.
Approximate greedy clustering
and distance selection for graph metrics , with D. Eppstein and
A. Sidiropoulos.
Did not appear yet
The maximum-level vertex in an arrangement of lines ,
with S. Halperin, K. Mehlhorn, E. Oh, and M. Sharir. Accepted to DCG.
Smallest k -enclosing rectangle revisited ,
with T. M. Chan.
Accepted to DCG.
In SoCG 19
.
Published
Journey to the center of the point set ,
with M. Jones.
TALG
17(1): 9:1-9:21, 2021
.
Also
in SoCG 19
.
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
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: Thu 2021-06-24 16:28:58 UTC 2021 by Sariel Har-Peled