Home Bookmarks Papers Blog

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

  1. Revisiting random points: Combinatorial complexity and algorithms, with E. Harb.
  2. Computing optimal kernels in two dimensions, with P. K. Agarwal.
  3. Sparsifying disk intersection graphs for reliable connectivity, with E. Robson.
  4. Local spanners revisited, with S. Ashur.
  5. On clusters that are separated but large, with J. Rogge.
  6. On the various depths of lines and planes, with V. Leo.
  7. How packed is it, really?, with T. Zhou.

Papers in Conferences

  1. Halving by a thousand cuts or punctures, with D.W. Zheng. To appear in SODA 2023.
  2. On the number of incidences when avoiding a bipartite clique, with T. M. Chan. To appear in SODA 2023.
  3. Approximation algorithms for maximum matchings in geometric intersection graphs, with E. Yang. In SoCG 22.
  4. Improved approximation algorithms for Tverberg partitions, with T. Zhou. In ESA 2021.
  5. On Undecided LP, Clustering and Active Learning, with S. Ashur. In SoCG 21.
  6. Submodular clustering in low dimensions, with A. Backurs. In SWAT 20.
  7. Approximate sparse linear regression, with P. Indk and S. Mahabadi. In ICALP 2018 DBLP.
  8. Proximity in the age of distraction: Robust approximate nearest neighbor search, with S. Mahabadi. In SODA 17 DBLP.
  9. Towards tight bounds for the streaming set cover problem, with P. Indyk, S. Mahabadi, and A. Vakilian. In PODS 16 DBLP.

Papers in Journals

In submission

  1. A note on Stabbing Convex Bodies with Points, Lines and Flats, with M. Jones. In SoCG 21.
  2. Few cuts meet many point sets, with M. Jones.

Did not appear yet

  1. Reliable spanner for metric spaces, with M. Mendel and D. Oláh. To appear in TALG. In SoCG 21 DBLP.

Published

  1. 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.
  2. Sometimes reliable spanners of almost linear size, with K. Buchin and D. Oláh. In ESA 20. JoCG 13(1): 178-196 (2022).
  3. 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).
  4. 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.
  5. 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.
  6. Active learning a convex body in low dimensions with M. Jones and S. Rahul. In Algorithmica 83(6): 1885-1917, 2021 DBLP. Also in ICALP 20 [talk]. DBLP.
  7. Smallest k-enclosing rectangle revisited, with T. M. Chan. In DCG 66(2): 769-791, 2021. DBLP. Also in SoCG 19 DBLP.
  8. Journey to the center of the point set, with M. Jones. TALG 17(1): 9:1-9:21, 2021 DBLP. Also in SoCG 19 DBLP.
  9. Approximate greedy clustering and distance selection for graph metrics, with D. Eppstein and A. Sidiropoulos. In JoCG 11(1): 629-652 (2020).
  10. A spanner for the day after. with K. Buchin, and D. Olah. DCG, 64(4): 1167-1191, 2020 DBLP. Also in SoCG 19 DBLP.
  11. Grid peeling and the affine curve-shortening flow, with D. Eppstein, and G. Nivasch. Exper. Math. 29:3, 306-316, 2020 DBLP. Also in ALENEX 2018 DBLP.
  12. 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 DBLP. Also in ITCS 18 DBLP.
  13. On locality-sensitive orderings and their applications, with T.M. Chan and M. Jones. SICOMP 49(3), 583–600, 2020. Also in ITCS 19.
  14. Decomposing arrangements of hyperplanes: VC-dimension, combinatorial dimension, and point location, with E. Ezra, H. Kaplan, and M Sharir. DCG 64: 109–173, 2020.
  15. On separating points by lines, with M. Jones. DCG 63(3): 705–730, 2020 DBLP. Also in SODA 18 DBLP.
  16. Sparse approximation via generating point sets, with A. Blum and B. Raichel. In TALG 15(3): 32:1-32:16, 2019 DBLP. Also in SODA 16 DBLP.
  17. 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 DBLP link.
  18. Robust proximity search for balls using sublinear space, with N. Kumar. In Algorithmica 80(1): 279-299, 2018 DBLP. Also in FSTTCS 2014 DBLP.
  19. Approximation algorithms for polynomial-expansion and low-density graphs, with K. Quanrud. SICOMP, 46(6): 1712–1744, 2017 Also in ESA 15 DBLP.
  20. Geometric packing under non-uniform constraints, with A. Ene and B. Raichel. In SICOMP, 46(6): 1745–1784, 2017 Also in SoCG 12.
  21. 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 DBLP.
  22. Convex hulls under uncertainty, with P.K. Agarwal, S. Suri, H. Yildiz, and W. Zhang. In Algorithmica 79(2): 340-367, 2017 DBLP link. Also in ESA 14 DBLP.
  23. Approximating the maximum overlap of polygons under translation, with S. Roy. In Algorithmica 78(1): 147-165,2017 DBLP link. Also in ESA 14 DBLP link.
  24. 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 DBLP. Also in PODS 13 DBLP.
  25. From proximity to utility: A Voronoi partition of Pareto optima, with H.-C. Chang and B. Raichel. In DCG 56(3): 631-656, 2016 DBLP link. Also in SoCG 15 DBLP.
  26. Space exploration via proximity search, with N. Kumar, D. Mount, and B. Raichel. In DCG 56(2): 357-376, 2016 DBLP. Also in SoCG 15 DBLP.
  27. On the expected complexity of Voronoi diagrams on terrains, with A. Driemel and B. Raichel. In TALG 12(3): 37, 2016 DBLP link. Also in SoCG 12.
  28. 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 DBLP link. Also in SoCG 12.
  29. Shortest path in a polygon using sublinear space. JoCG 7(2):19–45, 2016 DBLP. Also in SoCG 15 DBLP.
  30. 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.
  31. Net and prune: A linear time algorithm for euclidean distance problems, with B. Raichel. JACM 62(6): 44:1–44:35, 2015 DBLP. Also in STOC 2013.
  32. Approximating minimization diagrams and generalized proximity search, with N. Kumar. SICOMP 44(4): 944-974, 2015. Also in FOCS 2013.
  33. On the complexity of randomly weighted Voronoi diagrams, with B. Raichel. DCG 53(3): 547-568, 2015 DBLP. Also in SoCG 14.
  34. Down the rabbit hole: Robust proximity search in sublinear space, with N. Kumar. SICOMP 43(4): 1486-1511, 2014 DBLP. Also in FOCS 2012.
  35. Union of random Minkowski sums and network vulnerability analysis, with P. K. Agarwal, H. Kaplan, and M. Sharir. DCG 52(3): 551-582, 2014 DBLP.
  36. 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.
  37. The Fréchet distance revisited and extended, with B. Raichel. TALG 10 (1):3:1-3:22, 2014. Also in SoCG 11.
  38. 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.
  39. 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.
  40. Peeling the grid, with B. Lidicky. SIDMA 27 (2): 650-655, 2013. [BIB]
  41. Approximate nearest neighbor search for low dimensional queries, with N. Kumar. SICOMP 42 (1), 138-159, 2013. Also in SODA 2011.
  42. On the multi-cover problem in geometric settings, with K. Clarkson and C. Chekuri. TALG 9 (1), 2012. Also in SoCG 09.
  43. 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.
  44. Approximation algorithms for maximum independent set of pseudo-disks, with T. M. Chan. DCG 48 (2): 373-392, 2012. Also in SoCG 09.
  45. Weighted geometric set cover problems revisited, with M. Lee. JoCG 3 (1): 65--85, 2012.
  46. 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.
  47. New constructions of SSPDs and their applications, with M. A. Abam. CGTA 45 (5–6):200--214, 2012. Also in SoCG 10.
  48. Relative (p,eps)-approximations in geometry, with M. Sharir. DCG 45 (3): 462-496, 2011. Also in SoCG 07 (as a merged paper).
  49. 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.
  50. On approximating the depth and related problems, with B. Aronov. SICOMP 38(3): 899-921 (2008). Also in SODA 05.
  51. 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.
  52. The orienteering Problem in the plane revisited, with Ke Chen. SICOMP 38: (1) 385--397, 2008. Also in SoCG 06.
  53. 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.
  54. Smaller coresets for k-median and k-means clustering, with A. Kushal. DCG 37 (1): 3-19, 2007. Also on SoCG 05.
  55. How to get close to the median shape. In CGTA 36 (1): 39-51, 2007. Also in SoCG 06.
  56. On the least median square problem, with J. Erickson and D. Mount. DCG 36 (4): 593-607, 2006. Also in SoCG 04.
  57. 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.
  58. Guarding galleries and terrains, with A. Efrat. In IPL 100: (6) 238--245, 2006.
  59. On the Fermat-Weber center of a convex object, with P. Carmi, and M. J. Katz. In CGTA 32: (3) 188-195, 2005.
  60. "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.
  61. 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.
  62. 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.
  63. Geographic quorum systems approximations, with P. Carmi, S. Dolev, M. J. Katz, and M. Segal. In Algorithmica, 41 (4): 233--244, 2005.
  64. How fast is the k-means method?", with B. Sadri. In Algorithmica, 41(3):185--202, 2005. Also in SODA 05.
  65. 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.
  66. Fast algorithms for computing the smallest k-enclosing disc, with S. Mazumdar. In Algorithmica, 41(3):147--157, 2005. Also in ESA 03.
  67. Shape fitting with outliers, with Y. Wang. In SICOMP 33(2):269-285, 2004. Also in SoCG 03.
  68. High-dimensional shape fitting in linear time, with K. R. Varadarajan. DCG 32 (2): 269-288, 2004. Also in SoCG 03.
  69. Optimally cutting a surface into a disk, with J. Erickson. DCG 31 (1): 37-59, 2004. Also in SoCG 2002.
  70. The one-round Voronoi game, with O. Cheong, N. Linial, and J. Matousek. DCG 31 (1):125-138, 2004. Also in SoCG 2002.
  71. 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.
  72. Clustering motion. DCG 31 (4): 545--565, 2004. Also in FOCS 01.
  73. 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.
  74. 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.
  75. 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.
  76. Online point location in planar arrangements and its applications, with M. Sharir. DCG 26 (1): 19-40, 2001. Also in SODA 01.
  77. 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.
  78. Routing with a clue, with A. Bremler and Y. Afek, in Trans. on Networking, 9(6):693--705, 2001. Also in SIGCOMM '99.
  79. 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.
  80. Taking a walk in a planar arrangement, in SICOMP 30 (4) 1341-1367, 2000. Also in FOCS 99.
  81. 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.
  82. 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.
  83. Some variants of polygon containment and minimum Hausdorff distance under translation are 3sum-Hard, with G. Barequet, in IJCGA. Also in SODA 99.
  84. Constructing planar cuttings in theory and practice. SICOMP 29 (6) 2016-2039, 2000. Also in SoCG '98.
  85. Constructing approximate shortest path maps in three dimensions, in SICOMP, 28 (4), 1182-1197 (1999). Also in SoCG '98.
  86. Approximate shortest-path and geodesic diameter on convex polytopes in three dimensions. DCG, 21: 217-231 (1999). Also in SoCG '97.
  87. An output sensitive algorithm for discrete convex hulls, CGTA, 10 (1998) 125-138. Also in SoCG '98.
  88. 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.
  89. 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.

No journal version is planned

  1. Shortest secure path in a Voronoi diagram, with R. Varadharajan.

Older papers in conferences

No journal version is planned

  1. Separating a Voronoi diagram via local search, with V. V. S. P. Bhattiprolu. In SoCG 16 DBLP.
  2. Euclidean spanners in high dimensions, with P. Indyk and A. Sidiropoulos. In SODA 2013.
  3. Approximate distance queries in sparse graphs, with R. Agarwal and P. B. Godfrey. In INFOCOM 2011.
  4. Fréchet distance for curves, revisited, with B. Aronov, C. Knauer, Y. Wang, and C. Wenk. In ESA 06 DBLP.
  5. Maximum margin coresets for active and noise tolerant learning, with D. Roth and D. Zimak. In IJCAI 07.
  6. Coresets for discrete integration and clustering. In FSTTCS 06.
  7. Range medians, with S. Muthukrishnan. In ESA 08.
  8. Approximation algorithms for two optimal location problems in sensor networks, with A. Efrat and J. S. B. Mitchell. In Broadnets 2005.
  9. A time-optimal Delaunay refinement algorithm in two dimensions, with A. Ungor. In SoCG 05.
  10. Coresets for k-means and k-median clustering and their applications, with S. Mazumdar. In STOC 04.
  11. Constraint classification: A new approach to multiclass classification and ranking , with D. Roth and D. Zimak, in NIPS 2002.
  12. Projective clustering in high dimensions using coresets, with K. Varadarajan, in SoCG 2002.
  13. Approximate clustering via coresets, with M. Badoiu and P. Indyk, in STOC 2002.
  14. No coreset, no cry. Appeared in FSTTCS 04.
  15. Efficient algorithms for shared camera control, with V. Koltun, D. Song and K. Goldberg, in SoCG 03.
  16. On generalization bounds, projection profile, and margin distribution, with A. Garg and D. Roth. In ICML 2002.
  17. STAR-Tree: An efficient self-adjusting index for moving objects, with P.K. Agarwal and C.M. Procopiuc. In ALENEX 02.
  18. A practical approach for computing the diameter of a point-set , in SoCG 01.
  19. Occlusion culling for fast walkthrough in urban areas. with Y. Wang and P.K. Agarwal. In Eurographics 01.
  20. When crossings count - approximating the minimum spanning tree, with P. Indyk, in SoCG 2000.

Journal version appeared without me being involved

  1. Results on k-sets and j-facets via continuous motion arguments, with A. Andrzejak, B. Aronov, R. Seidel and E. Welzl, in SoCG '98.
  2. 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

  1. Staying in the middle: Exact and approximate medians in R1 and R2 for moving points, with P.K. Agarwal, M. de Berg, J. Gao, and L. J. Guibas. CCCG 05.
  2. 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

  1. 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%]
  2. STOC 2013 - Palo Alto (1: 100/360).
    STOC 2004 - Chicago (1:71/273)
    STOC 2002 (1:91/287)
  3. 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)
  4. SIGCOMM '99 (1: 24/190)
  5. WAE 99 (1: 24/46)
  6. WADS 2001 (1:40/89)
  7. SWAT 2000
  8. 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).
  9. AISTAT 05: (1:58/150)
  10. PODS 2013: (1:24/97).
  11. ALENEX 2002: (1:15/34)
  12. WADS 01: 1
  13. ESA 02:
    ESA 03: (1:46/119)
    ESA 06: (1:52/215)
    ESA 15: (1:85/320: 26%)
  14. FSTTCS 04: (1:38/176)
    FSTTCS 06:
  15. Broadnets 2005: (1:49/100).

Journals

  1. JACM: 2
  2. SICOMP: 10
  3. DCG: 15
  4. TALG: 1
  5. JCG: 1
  6. CGTA: 4
  7. Nordic J. Comput.: 1
  8. Algorithmica: 4
  9. Trans. on Networking: 1
  10. J. Algorithms : 1
  11. ORL - Operation Research Letters
ORCID iD iconorcid.org/0000-0003-2638-9635
Last modified: Tue 2022-10-11 17:54:02 UTC 2022 by Sariel Har-Peled