Micha Sharir

Alicia and Isaias Nizri Chair in Computational Geometry and Robotics

School of Computer Science

Tel Aviv University

Ramat Aviv, Tel Aviv 69978, Israel

972-3-6408804 (voice)

972-3-6409373 (fax)

michas at post.tau.ac.il

Biosketch:

Current Interests:

Courses:

Papers:

• M. Sharir and A. Pnueli,
  Two approaches to interprocedural data flow analysis,
  in Program Flow Analysis: Theory and Applications, (S. S. Muchnik and N. D. Jones, editors), Prentice-Hall, 1981, 189--233.
  
  
• J. T. Schwartz and M. Sharir,
  On the Piano Movers' problem: II. General techniques for computing topological properties of real algebraic manifolds,
  Advances in Appl. Math. 4 (1983), 298--351.
  
  
• M. Sharir and P.K. Agarwal,
  Davenport-Schinzel Sequences and Their Geometric Applications,
  Cambridge University Press, Cambridge-New York-Melbourne, 1995.
  
  
• D. Halperin and M. Sharir,
  Arrangements and their applications in robotics: Recent developments,
  in The Algorithmic Foundations of Robotics, K. Goldberg, D. Halperin, J.C. Latombe and R. Wilson, Eds., A.K. Peters, Boston, MA, 1995, 495--511.
  
  
• P. Agarwal and M. Sharir,
  Algorithmic techniques for geometric optimization,
  Lecture Notes in Computer Science, Vol. 1000 (J. van Leeuwen, Ed.), Springer-Verlag, Berlin, 1995, 234--253.
  
  
• M. Sharir,
  Arrangements in higher dimensions: Voronoi diagrams, motion planning, and other applications,
  Proc. Workshop on Algorithms and Data Structures, Ottawa, Canada, August 1995.
  
  
• P.K. Agarwal, O. Schwarzkopf and M. Sharir,
  The overlay of lower envelopes in 3-space and its applications,
  Discrete Comput. Geom. 15 (1996), 1--13.
  
  
• A. Efrat and M. Sharir,
  A near-linear algorithm for the planar segment center problem,
  Discrete Comput. Geom. 16 (1996), 239--257.
  
  
• M. Sharir,
  Excess in arrangements of segments,
  Information Processing Letters 58 (1996), 245--247.
  
  
• J. Matou\v{s}ek, M. Sharir and E. Welzl,
  A subexponential bound for linear programming and related problems,
  Algorithmica 16 (1996), 498--516.
  
  
• P.K. Agarwal and M. Sharir,
  Efficient randomized algorithms for some geometric optimization problems,
  Discrete Comput. Geom. 16 (1996), 317--337.
  
  
• D. Halperin and M. Sharir,
  A near-quadratic algorithm for planning the motion of a polygon in a polygonal environment,
  Discrete Comput. Geom. 16 (1996), 121--134.
  
  
• G. Barequet and M. Sharir,
  Piecewise-linear interpolation between polygonal slices,
  Computer Vision and Image Understanding 63 (1996), 251--272.
  
  
• P. Agarwal, M. de Berg, D. Halperin and M. Sharir,
  Efficient generation of k-directional assembly sequences.
  Proc. 7th ACM-SIAM Symp. on Discrete Algorithms (1996), 122--131.
  
  
• M. Sharir and E. Welzl,
  Rectilinear and polygonal p-piercing and p-center problems,
  Proc. 12th ACM Symp. on Computational Geometry (1996), 122--132.
  
  
• P.K. Agarwal, S. Har-Peled, M. Sharir and K. Varadarajan,
  Approximate shortest paths on a convex polytope in three dimensions,
  J. Assoc. Comput. Mach. 44 (1997), 567--584.
  
  
• P. Agarwal, B. Aronov, J. Pach, R. Pollack and M. Sharir,
  Quasi-planar graphs have a linear number of edges,
  Combinatorica 17 (1997), 1--9.
  
  
• O. Schwarzkopf and M. Sharir,
  Vertical decomposition of a single cell in a 3-dimensional arrangement of surfaces,
  Discrete Comput. Geom. 18 (1997), 269--288.
  
  
• M. Sharir,
  A near-linear algorithm for the planar 2-center problem,
  Discrete Comput. Geom. 18 (1997), 125--134.
  
  
• G. Barequet and M. Sharir,
  Partial surface and volume matching in three dimensions,
  IEEE Trans. on Pattern Analysis and Machine Intelligence 19 (9) (1997), 929--948.
  
  
• M. Sharir,
  Motion planning,
  in Handbook of Discrete and Computational Geometry, (J. E. Goodman and J. O'Rourke, Eds.), CRC Press, Boca Raton, Florida, 1997, 733--754.
  
  
• B. Aronov and M. Sharir,
  On translational motion planning of a convex polyhedron in 3-space,
  SIAM J. Computing 26 (1997), 1785--1803.
  
  
• B. Aronov and M. Sharir,
  The common exterior of convex polygons in the plane,
  Computational Geometry, Theory and Appls. 8 (1997), 139--149.
  
  
• P.K. Agarwal, B. Aronov and M. Sharir,
  Computing envelopes in four dimensions with applications,
  SIAM J. Computing 26 (1997), 1714--1732.
  
  
• M. Katz and M. Sharir,
  An expander-based approach to geometric optimization,
  SIAM J. Computing. 26 (1997), 1384--1408.
  
  
• S. Mohaban and M. Sharir,
  Ray shooting amidst spheres in 3 dimensions and related problems,
  SIAM J. Computing. 26 (1997), 654--674.
  
  
• B. Aronov, M. Sharir and B. Tagansky,
  The union of convex polyhedra in three dimensions,
  SIAM J. Computing. 26 (1997), 1670--1688.
  
  
• G. Barequet and M. Sharir,
  Partial surface and volume matching in three dimensions,
  IEEE Trans. on Pattern Recognition and Machine Intelligence 19 (9) (1997), 929--948.
  
  
• K. Kedem, M. Sharir and S. Toledo,
  On critical orientations in the Kedem-Sharir motion planning algorithm,
  Discrete Comput. Geom. 17 (1997), 227--239.
  
  
• J. Pach and M. Sharir,
  On the number of incidences between points and curves.
  Combinat. Probab. Comput. 7 (1998), 121--127.
  
  
• J.D. Boissonnat, M. Sharir, B. Tagansky and M. Yvinec,
  Voronoi diagrams in higher dimensions under certain polyhedral distance functions,
  Discrete Comput. Geom. 19 (1998), 485--519.
  
  
• P. Agarwal, B. Aronov, T. Chan and M. Sharir,
  On levels in arrangements of lines, segments, planes, and triangles,
  Discrete Comput. Geom. 19 (1998), 315--331.
  
  
• P. Agarwal and M. Sharir,
  Efficient algorithms for geometric optimization,
  ACM Computing Surveys 30 (1998), 412--458.
  
  
• P. Agarwal, N. Amenta and M. Sharir,
  Largest placement of one convex polygon inside another,
  Discrete Comput. Geom. 19 (1998), 95--104.
  
  
• P. Agarwal, M. Sharir and E. Welzl,
  The discrete 2-center problem,
  P. Agarwal, M. Sharir and E. Welzl, The discrete 2-center problem. Discrete Comput. Geom. 20 (1998), 287--305.
  
  
• L.P. Chew, K. Kedem, M. Sharir, B. Tagansky and E. Welzl,
  Voronoi diagrams of lines in three dimensions under polyhedral convex distance functions,
  J. Algorithms 29 (1998), 238--255.
  
  
• J. Pach and M. Sharir,
  On the boundary of the union of planar convex sets,
  Discrete Comput. Geom. 21 (1999), 321--328.
  
  
• P. Agarwal, B. Aronov and M. Sharir,
  Line transversals of balls and smallest enclosing cylinders in three dimensions,
  Discrete Comput. Geom. 21 (1999), 373--388.
  
  
• P. Agarwal, B. Aronov and M. Sharir,
  Motion planning for a convex polygon in a polygonal environment,
  Discrete Comput. Geom. 22 (1999), 201--221.
  
  
• G. Barequet and M. Sharir,
  Partial surface matching by using directed footprints,
  Comput. Geom. Theory Appls. 12 (1999), 45--62.
  
  
• M. van Kreveld, J. Mitchell, P. Rousseeuw, M. Sharir, J. Snoeyink and B. Speckmann,
  Efficient algorithms for maximum regression depth,
  Proc. 15th ACM Symp. on Computational Geometry (1999), 31--40.
  Also Discrete Comput. Geom. 39 (2008), 656--677.
  
  
• M. Sharir,
  Arrangements of surfaces in higher dimensions,
  in Advances in Discrete and Computational Geometry (Proc. 1996 AMS Mt. Holyoke Summer Research Conference, B. Chazelle, J.E. Goodman and R. Pollack, Eds.) Contemporary Mathematics No. 223, American Mathematical Society, 1999, 335--353.
  
  
• P. Agarwal and M. Sharir,
  Davenport-Schinzel sequences and their geometric applications,
  in Handbook of Computational Geometry, J.R. Sack and J. Urrutia (Eds.), North-Holland, 2000, pp. 1--47.
  
  
• P. Agarwal and M. Sharir,
  Arrangements of surfaces in higher dimensions,
  in Handbook of Computational Geometry, J.R. Sack and J. Urrutia (Eds.), North-Holland, 2000, pp. 49--119.
  
  
• P. Agarwal, A. Efrat and M. Sharir,
  Vertical decomposition of shallow levels in 3-dimensional arrangements and its applications,
  SIAM J. Computing 29 (2000), 912--953.
  
  
• A. Efrat and M. Sharir,
  The complexity of the union of fat objects in the plane,
  Discrete Comput. Geom. 23 (2000), 171--189.
  
  
• P. Agarwal, B. Aronov, S. Har-Peled and M. Sharir,
  Approximation and exact algorithms for minimum-width annuli and shells.
  Discrete Comput. Geom. 24 (2000), 687--705.
  
  
• P. Agarwal and M. Sharir,
  Pipes, cigars, and kreplach: The union of Minkowski sums in three dimensions.
  Discrete Comput. Geom. 24 (2000), 645--685.
  
  
• S. Smorodinski, J. Mitchell and M. Sharir,
  Geometric permutations of pairwise disjoint balls,
  Discrete Comput. Geom., 23 (2000), 247--259.
  
  
• P.K. Agarwal, L. Guibas, S. Har-Peled, A. Rabinovitch and M. Sharir,
  Computing the penetration depth of two convex polytopes in three dimensions,
  Nordic Journal of Computing 7 (2000), 227--240.
  
  
• A. Efrat, M. Katz, F. Nielsen and M. Sharir,
  Data structures for fat objects and their applications,
  Comput. Geom. Theory Appls. 15 (2000), 215--227.
  
  
• B. Aronov, A. Efrat, D. Halperin and M. Sharir,
  On the number of regular vertices of the union of Jordan regions,
  Discrete Comput. Geom. 25 (2001), 203--220.
  
  
• S. Har-Peled and M. Sharir,
  On-line point location in planar arrangements and its applications,
  Discrete Comput. Geom. 26 (2001), 19--40.
  
  
• M. Sharir, S. Smorodinsky and G. Tardos,
  An improved bound for k-sets in three dimensions,
  Discrete Comput. Geom. 26 (2001), 195--204.
  
  
• J. Pach and M. Sharir,
  Radial points in the plane,
  European J. Combinatorics 22 (2001), 855--863.
  
  
• P. Agarwal, B. Aronov and M. Sharir,
  Exact and approximation algorithms for minimum-width cylindrical shells,
  Discrete Comput. Geom. 26 (2001), 307--320.
  
  
• N. Alon, H. Last, R. Pinchasi and M. Sharir,
  On the complexity of arrangements of circles in the plane,
  Discrete Comput. Geom. 26 (2001), 465--492.
  
  
• B. Aronov and M. Sharir,
  Cutting circles into pseudo-segments and improved bounds for incidences,
  Discrete Comput. Geom. 28 (2002), 475--490.
  
  
• P. Agarwal and M. Sharir,
  On the number of congruent simplices in a point set,
  Discrete Comput. Geom. 28 (2002), 123--150.
  
  
• P. Agarwal, T. Hagerup, R. Ray, M. Sharir, M. Smid and E. Welzl,
  Translating a planar object to maximize point containment,
  Proc. European Symposium on Algorithms (2002), 42--53.
  
  
• D. Halperin, M. Sharir and K. Goldberg,
  The 2-center problem with obstacles,
  J. Algorithms 42 (2002), 109--134.
  
  
• P.K. Agarwal, M. de Berg, S. Har-Peled, M. Overmars, M. Sharir and J. Vahrenhold,
  Reporting intersecting pairs of polytopes in two and three dimensions,
  Comput. Geom. Theory Appls., 23 (2002), 195--207.
  
  
• P. Agarwal, B. Aronov and M. Sharir,
  On the complexity of many faces in arrangements of pseudo-segments and of circles,
  Discrete and Computational Geometry --- The Goodman-Pollack Festschrift, B. Aronov, S. Basu, J. Pach and M. Sharir (Eds.), Springer-Verlag, Heidelberg, 2003, pp. 1--23.
  Also in Proc. 42nd IEEE Symp. on Foundations of Computer Science (2001), 74--83.
  
  
• M. Sharir and S. Smorodinsky,
  Extremal configurations and levels in pseudoline arrangements,
  Proc. 8th Workshop on Algorithms and Data Structures (2003), in Lecture Notes in Computer Science, Vol. 2748, Springer Verlag, pages 127--139.
  
  
• B. Aronov, J. Pach, M. Sharir and G. Tardos,
  Distinct distances in higher dimensions,
  Combinat. Probab. Comput. 13 (2004), 283--293.
  
  
• M. Sharir and E. Welzl,
  Balanced lines, halving triangles, and the generalized lower bound theorem,
  Discrete and Computational Geometry --- The Goodman-Pollack Festschrift, B. Aronov, S. Basu, J. Pach and M. Sharir (Eds.), Springer-Verlag, Heidelberg, 2003, pp. 789--798.
  Also in Proc. 17th ACM Symp. on Computational Geometry, June 2001, pp. 315--318.
  
  
• J. Pach, I. Safruti and M. Sharir,
  The union of congruent cubes in three dimensions,
  Discrete Comput. Geom., 30 (2003), 133--160.
  
  
• V. Koltun and M. Sharir,
  Three-dimensional Euclidean Voronoi diagrams of lines with a fixed number of orientations,
  SIAM J. Comput., 32 (2003), 616--642.
  
  
• M. Sharir,
  The Clarkson-Shor technique revisited and extended,
  Combinat. Probab. Comput. 12 (2003), 191--201.
  
  
• P. Agarwal, S. Har-Peled, M. Sharir and Y. Wang,
  Hausdorff distance under translation for points, disks and balls,
  Proc. 19th ACM Symp. on Computational Geometry (2003), 282-291.
  Also in ACM Trans. Algorithms 6(4) (2010), Article 71.
  
  
• G. Pustylnik and M. Sharir,
  The Minkowski sum of a simple polygon and a segment,
  Information Processing Letters 85 (2003), 179--184.
  
  
• M. Sharir and S. Smorodinsky,
  Neighbors in geometric permutations,
  Discrete Math. 268 (2003), 327--335.
  
  
• V. Koltun and M. Sharir,
  The partition technique for the overlay of envelopes,
  SIAM J. Comput. 32 (2003), 841--863.
  
  
• B. Aronov, S. Basu, J. Pach and M. Sharir (Editors),
  Discrete and Computational Geometry---The Goodman--Pollack Festschrift ,
  Algorithms and Combinatorics Series, Vol. 25, Springer Verlag, Heidelberg, 2003.
  
  
• P. Agarwal, E. Nevo, J. Pach, R. Pinchasi, M. Sharir and S. Smorodinsky,
  Lenses in arrangements of pseudocircles and their applications,
  J. ACM, 51 (2004), 139--186.
  
  
• A. Dumitrescu, J.S.B. Mitchell and M. Sharir,
  Binary space partitions for axis-parallel segments, rectangles, and hyperrectangles,
  Discrete Comput. Geom. 31 (2004), 207--227.
  
  
• S. Smorodinsky and M. Sharir,
  Selecting points that are heavily covered by pseudo-circles, spheres, or boxes.
  Combin. Probab. Comput. 13 (2004), 389--411.
  
  
• E. Ezra, D. Halperin and M. Sharir,
  Speeding up the incremental construction of the union of geometric objects in practice,
  Comput. Geom. Theory Appl. 27 (2004), 63--85.
  
  
• S. Dekel, D. Leviatan and M. Sharir,
  On bivariate smoothness spaces associated with nonlinear approximation,
  Constructive Approximation, 20 (2004), 625--646.
  
  
• V. Koltun and M. Sharir,
  Polyhedral Voronoi diagrams of polyhedra in three dimensions,
  Discrete Comput. Geom. 31 (2004), 83--124.
  
  
• M. Sharir and E. Welzl,
  Point-line incidences in space,
  Combinat. Probab. Comput. 13 (2004), 203--220.
  
  
• B. Aronov and M. Sharir,
  Cell complexities in hyperplane arrangements,
  Discrete Comput. Geom. 32 (2004), 107--115.
  
  
• J.S.B. Mitchell and M. Sharir,
  New results on shortest paths in three dimensions,
  Proc. 20th ACM Symp. on Computational Geometry (2004), 124--133.
  
  
• G. Kozma, Z. Lotker, M. Sharir and G. Stupp,
  Geometrically aware communication in random wireless networks reconsidered,
  Proc. 23rd ACM Symp. on Principles of Distributed Computing (2004), 310--319.
  
  
• J. Pach and M. Sharir,
  Geometric incidences,
  in Towards a Theory of Geometric Graphs (J. Pach, ed.), Contemporary Mathematics, Vol. 342, Amer. Math. Soc., Providence, RI, 2004, pp. 185--223.
  
  
• J. Pach, R. Pinchasi and M. Sharir,
  On the number of directions determined by a three-dimensional point set,
  J. Combinat. Theory, Ser. A 108 (2004), 1--16.
  
  
• B. Aronov, R. Schiffenbauer and M. Sharir,
  On the number of views of translates of a cube and related problems,
  Comput. Geom. Theory Appl. 27 (2004), 179--192.
  
  
• P. Agarwal and M. Sharir,
  Pseudoline arrangements: Duality, algorithms and applications,
  SIAM J. Comput., 34 (2005), 526--552.
  
  
• B. Aronov, V. Koltun and M. Sharir,
  Cutting triangular cycles of lines in space.
  Discrete Comput. Geom., 33 (2005), 231--247.
  
  
• R. Pinchasi and M. Sharir,
  On graphs that do not contain the cube and related problems,
  Combinatorica 25 (2005), 615--624.
  
  
• B. Aronov, V. Koltun and M. Sharir,
  Incidences between points and circles in three and higher dimensions,
  Discrete Comput. Geom., 33 (2005), 185--206.
  Also in Proc. 18th ACM Symp. on Computational Geometry (2002), 116--122.
  
  
• S. Feldman and M. Sharir,
  An improved bound for joints in arrangements of lines in space,
  Discrete Comput. Geom. 33 (2005), 307--320.
  
  
• R. Seidel and M. Sharir,
  Top-down analysis of path compression,
  SIAM J. Comput., 34 (2005), 515--525.
  
  
• J. Pach, R. Pinchasi, M. Sharir and G. T\'oth,
  Topological graphs with no large grids,
  Graphs and Combinatorics, 21 (2005), 355--364.
  
  
• V. Koltun and M. Sharir,
  Curve-sensitive cuttings,
  SIAM J. Comput. 34 (2005), 863--878.
  
  
• M. Sharir and H. Shaul,
  Ray shooting and stone throwing with near-linear storage,
  Comput. Geom. Theory Appl., 30 (2005), 239--252.
  
  
• P. Agarwal, B. Aronov, V. Koltun and M. Sharir,
  On lines avoiding unit balls in three dimensions,
  Discrete Comput. Geom., 34 (2005), 231--250.
  
  
• V. Kaibel, R. Mechtel, M. Sharir and G. Ziegler,
  The simplex algorithm in dimension three,
  SIAM J. Comput. 34 (2005), 475--497.
  
  
• E. Ezra and M. Sharir,
  Counting and representing intersections among triangles in three dimensions,
  Comput. Geom. Theory Appls. 32 (2005), 196--215.
  
  
• N. Alon, J. Pach, R. Pinchasi, R. Radoi\v{c}i\'c and M. Sharir,
  Crossing patterns of semialgebraic sets,
  J. Combinat. Theory, Ser. A 111 (2005), 310--326.
  
  
• E. Ezra and M. Sharir,
  Output sensitive construction of the union of triangles,
  SIAM J. Comput. 34 (2005), 1331--1351.
  
  
• R. Apfelbaum and M. Sharir,
  Repeated angles in three and four dimensions,
  SIAM J. Discrete Math. 19 (2005), 294--300.
  
  
• J. Matou\v{s}ek, M. Sharir, S. Smorodinsky and U. Wagner,
  On k-sets in four dimensions,
  Discrete Comput. Geom. 35 (2006), 177--191.
  
  
• H. Kaplan and M. Sharir,
  Randomized incremental construction of three-dimensional convex hulls and planar Voronoi diagrams, and approximate range counting,
  Proc. 17th ACM-SIAM Symp. on Discrete Algorithms (2006), 484--493.
  
  
• E. Welzl and M. Sharir,
  On the number of crossing-free matchings, cycles and partitions,
  SIAM J. Comput., 36 (2006), 695--720.
  
  
• R. Pinchasi, R. Radoi\v{c}i\'c and M. Sharir,
  On empty convex polygons in a planar point set,
  J. Combinat. Theory, Ser. A 113 (2006), 385--419.
  
  
• E. Oks and M. Sharir,
  Minkowski sums of monotone and general simple polygons,
  Discrete Comput. Geom. 35 (2006), 223--240.
  
  
• B. Aronov, A. Efrat, V. Koltun and M. Sharir,
  On the union of kappa-curved objects in three and four dimensions,
  Discrete Comput. Geom., 36 (2006), 511--526.
  
  
• P. Agarwal, M. Overmars and M. Sharir,
  Computing maximally separated sets in the plane and independent sets in the intersection graph of unit disks.
  SIAM J. Comput., 36 (2006), 815--834.
  
  
• P.K. Agarwal, S. Cabello, J.A. Sellar\`es and M. Sharir,
  Computing a center-transversal line,
  Proc. FSTTCS (2006), Lecture Notes Comput. Sci., Vol 4337, Springer Verlag, 2006, 93--104.
  
  
• M. Sharir and E. Welzl,
  Random triangulations of planar point sets,
  Proc. 22nd ACM Symp. on Computational Geometry (2006), 273--281.
  
  
• K. Chen, A. Fiat, H. Kaplan, M. Levy, J. Matou\v{s}ek, E. Mossel, J. Pach, M. Sharir, S. Smorodinsky, U. Wagner and E. Welzl,
  Online conflict-free coloring for intervals,
  SIAM J. Comput., 36 (2006), 1342--1359.
  
  
• H. Kaplan, M. Sharir and E. Verbin,
  Colored intersection searching via sparse rectangular matrix multiplication,
  Proc. 22nd ACM Symp. on Computational Geometry (2006), 52--60.
  
  
• G. Alexandron, H. Kaplan and M. Sharir,
  Kinetic and dynamic data structures for convex hulls and upper envelopes,
  Comput. Geom. Theory Appls., 36 (2006), 144--158.
  
  
• D. Feldman, A. Fiat and M. Sharir,
  Coresets for weighted facilities and their applications,
  Proc. 47rd IEEE Symp. on Foundations of Computer Science (2006), 315--324.
  
  
• J. Pach, R. Pinchasi and M. Sharir,
  Solution of Scott's problem on the number of directions determined by a point set in 3-space,
  Discrete Comput. Geom., 38 (2007), 399--441.
  
  
• E. Ezra and M. Sharir,
  A single cell in an arrangement of convex polyhedra in R^3,
  Discrete Comput. Geom., 37 (2007), 21--41.
  
  
• R. Apfelbaum and M. Sharir,
  Large bipartite graphs in incidence graphs of points and hyperplanes,
  SIAM J. Discrete Math. 21 (2007), 707--725.
  
  
• B. Aronov, S. Har-Peled and M. Sharir,
  On approximate halfspace range counting and relative epsilon approximations.
  Proc. 23rd ACM Symp. on Computational Geometry (2007), 327--336.
  
  
• P.K. Agarwal, H. Kaplan and M. Sharir,
  Computing the volume of the union of cubes in three dimensions,
  Proc. 23rd ACM Symp. on Computational Geometry (2007), 294--301.
  
  
• P.K. Agarwal, R. Apfelbaum, G. Purdy and M. Sharir,
  Similar simplices in a d-dimensional point set,
  Proc. 23rd ACM Symp. on Computational Geometry (2007), 232--238.
  
  
• D. Feldman, A. Fiat, M. Sharir and D. Segev,
  Constant-factor bi-criteria linear-time approximations for generalized k-mean/median/center,
  Proc. 23rd ACM Symp. on Computational Geometry (2007), 19--26.
  
  
• Y. Schreiber and M. Sharir,
  An optimal algorithm for shortest paths on a convex polytope in three dimensions,
  Discrete Comput. Geom., 39 (2008), 500--579.
  
  
• P.K. Agarwal, M. Sharir and E. Welzl,
  Algorithms for center and Tverberg points,
  ACM Trans. Algorithms 5 (2008), Article 5.
  
  
• P.K. Agarwal, R. Klein, C. Knauer, S. Langerman, P. Morin, M. Sharir and M. Soss,
  Computing the maximum detour and spanning ratio of 2- and 3-dimensional paths, trees, and cycles,
  Discrete Comput. Geom., 39 (2008), 17--37.
  
  
• E. Ezra, M. Sharir and A. Efrat,
  On the ICP algorithm,
  Comput. Geom. Theory Appls., 41 (2008), 77--93.
  
  
• H. Kaplan, N. Rubin, M. Sharir and E. Verbin,
  Efficient colored orthogonal range counting,
  SIAM J. Comput. 38 (2008), 982--1011.
  
  
• J. Pach and M. Sharir,
  On planar intersection graphs with forbidden subgraphs,
  J. Graph Theory 59 (2008), 205--214.
  
  
• P. K. Agarwal, H. Kaplan and M. Sharir,
  Kinetic and dynamic data structures for closest pairs and nearest neighbors,
  ACM Trans. Algorithms 5 (2008), Article 4.
  
  
• P. K. Agarwal, J. Pach and M. Sharir,
  State of the union, of geometric objects: A review,
  in Proc. Joint Summer Research Conf. on Discrete and Computational Geometry: 20 Years Later, Contemp. Math. 452, AMS, 2008, pp. 9--48.
  
  
• N. Alon, H. Kaplan, G. Nivasch, M. Sharir and S. Smorodinsky,
  Weak epsilon-nets and interval chains,
  J. ACM 55 (2008), Article 28.
  
  
• N. Alon, D. Halperin, O. Nechushtan and M. Sharir,
  The complexity of the outer face in random arrangements of segments,
  Proc. 24th ACM Symp. on Computational Geometry (2008), 69--78.
  
  
• P.K. Agarwal, D.Z. Chen, S.K. Ganjugunte, E. Misiolek, M. Sharir and K. Tang,
  Stabbing convex polygons with a segment or a polygon,
  Proc. European Symposium on Algorithms, (2008), 52--63.
  
  
• V. Koltun and M. Sharir,
  A note on overlays of minimization diagrams,
  Discrete Comput. Geom. 41 (2009), 385--397.
  
  
• K. Chen, H. Kaplan and M. Sharir,
  Online conflict-free coloring for halfplanes, congruent disks, and axis-parallel rectangles,
  ACM Trans. Algorithms 5 (2009), Article 16.
  
  
• J. Pach and M. Sharir,
  Combinatorial Geometry and its Algorithmic Applications: The Alcala Lectures,
  Lecture notes, Alcala, Spain, August--September, 2006.
  Revised version in Amer. Math. Soc. Press., Providence, RI, 2009.
  
  
• E. Ezra, J. Pach and M. Sharir,
  On regular vertices on the union of planar objects,
  Discrete Comput. Geom. 41 (2009), 216--231.
  
  
• H. Kaplan, N. Rubin and M. Sharir,
  Linear data structures for fast ray shooting amid convex polytopes,
  Algorithmica 55 (2009), 283--310.
  
  
• E. Ezra and M. Sharir,
  Almost tight bound for the union of fat tetrahedra in three dimensions,
  J. ACM 57 (2009), Article 2 (23 pages).
  
  
• G. Nivasch and M. Sharir,
  Eppstein's bound on intersecting triangles revisited,
  J. Combinat. Theory, Ser. A 116 (2009), 494--497.
  
  
• A. Dumitrescu, M. Sharir and Cs.D. Toth,
  Extremal problems on triangle areas in two and three dimensions,
  J. Combinat. Theory, Ser. A 116 (2009), 1177--1198.
  
  
• M. Sharir,
  On distinct distances and incidences: Elekes's transformation and the new algebraic developments,
  Annales Univ. Sci. Budapest. 52 (2009), 75--102.
  
  
• P. K. Agarwal, J. Gao. L. Guibas, H. Kaplan, V. Koltun, N. Rubin and M. Sharir,
  Kinetic stable Delaunay graphs,
  Proc. 26th ACM Symp. on Computational Geometry (2010), 127--136.
  Also in arXiv:1104.0622.
  
  
• P.K. Agarwal, S. Bereg, O. Daescu, H. Kaplan, S. Ntafos, M. Sharir and B. Zhu,
  Guarding a terrain by two watchtowers,
  Algorithmica 58 (2010), 352--390.
  
  
• H. Kaplan, N. Rubin and M. Sharir,
  Line transversals of convex polyhedra in R^3,
  SIAM J. Comput. 39 (2010), 3283--3310.
  
  
• B. Aronov and M. Sharir,
  Approximate halfspace range counting,
  SIAM J. Comput. 39 (2010), 2704--2725.
  
  
• J.S.B. Mitchell, Y. Schreiber and M. Sharir,
  New results on shortest paths in three dimensions,
  Manuscript, 2010.
  
  
• B. Aronov, E. Ezra and M. Sharir,
  Small-size epsilon nets for axis-parallel rectangles and boxes,
  SIAM J. Comput. 39 (2010), 3248--3282.
  
  
• R. Apfelbaum and M. Sharir,
  An improved bound on the number of unit-area triangles,
  Discrete Comput. Geom. 44 (2010), 753--761.
  
  
• H. Kaplan, M. Sharir, and E. Shustin,
  On lines and joints,
  Discrete Comput. Geom. 44 (2010), 838--843.
  Also in arXiv:0906.0558.
  
  
• D. Halperin, O. Setter and M. Sharir,
  Constructing two-dimensional Voronoi diagrams via divide-and-conquer of envelopes in space,
  Transactions on Computational Science 9 (2010), 1--27.
  Also in Proc. 6th Annu. Internat. Sympos. Voronoi Diagrams in Science and Engineering (ISVD) (2009), 43--52.
  
  
• H. Kaplan, E. Ramos and M. Sharir,
  Range minima queries with respect to a random permutation, and approximate range counting,
  Discrete Comput. Geom. 45 (2011), 3--33. Published online Nov. 11, 2010.
  
  
• H. Kaplan, E. Ramos and M. Sharir,
  The overlay of minimization diagrams in a randomized incremental construction,
  Discrete Comput. Geom. 45 (2011), 371--382. Published online January 6, 2011.
  
  
• M. Sharir and H. Shaul,
  Semi-algebraic range reporting and emptiness searching with applications,
  SIAM J. Comput., 40 (2011), 1045--1074.
  
  
• Gy. Elekes, H. Kaplan and M. Sharir,
  On lines, joints, and incidences in three dimensions,
  J. Combinat. Theory, Ser. A 118 (2011), 962--977. published online Nov. 17, 2010. Also in arXiv:0905.1583.
  
  
• M. Sharir,
  An improved bound for k-sets in four dimensions,
  Combinat. Probab. Comput. 20 (2011), 119--129.
  
  
• M. Sharir and A. Sheffer,
  Counting triangulations of planar point sets,
  Electronic J. Combinat. 18 (2011), P70. Also in arXiv:0911.3352.
  
  
• S. Har-Peled and M. Sharir,
  Relative (p,epsilon)-approximations in geometry,
  Discrete Comput. Geom. 45 (2011), 462--496. Also in arXiv:0909.0717.
  
  
• H. Kaplan, N. Rubin and M. Sharir,
  A kinetic triangulation scheme for moving points in the plane,
  Comput. Geom. Theory Appl. 44 (2011), 191--205. Published online Nov. 5, 2010.
  
  
• M. Sharir, A. Sheffer and E. Welzl,
  On degrees in random triangulations,
  J. Combinat. Theory, Ser. A, 118 (2011), 1979--1999.
  
  
• Gy. Elekes and M. Sharir,
  Incidences in three dimensions and distinct distances in the plane,
  Combinat. Probab. Comput., 20 (2011), 571--608. Also in arXiv:1005.0982.
  
  
• H. Kaplan, M. Katz, G. Morgenstern and M. Sharir,
  Optimal cover of points by disks in a simple polygon,
  SIAM J. Comput. 40 (2011), 1647--1661.
  Also in Proc. European Symposium on Algorithms (2010), 475--486.
  
  
• R. Apfelbaum and M. Sharir,
  Non-degenerate spheres in three dimensions,
  Combinat. Probab. Comput., 20 (2011), 503--512. Published online January 28, 2011.
  
  
• E. Ezra, B. Aronov, and M. Sharir,
  Improved bound for the union of fat triangles,
  Proc. 22nd ACM-SIAM Symp. on Discrete Algorithms (2011), 1778--1785.
  
  
• H. Kaplan and M. Sharir,
  Finding the maximal empty rectangle containing a query point,
  In arXiv:1106.3628.
  
  
• N. Rubin, H. Kaplan and M. Sharir,
  Improved bounds for geometric permutations,
  SIAM J. Comput. 41 (2012), 367--390.
  Also in arXiv:1007.3244.
  Also in Proc. 51st IEEE Symp. on Foundations of Computer Science (2010), 355--364.
  
  
• H. Kaplan, J. Matou\v{s}ek, M. Sharir, and Z. Safernov\'a,
  Unit distances in three dimensions,
  Combinat. Probab. Comput. 21 (2012), 597--610.
  Also in arXiv:1107.1077.
  
  
• H. Kaplan, J. Matou\v{s}ek and M. Sharir,
  Simple proofs of classical theorems in discrete geometry via the Guth-Katz polynomial partitioning technique,
  Discrete Comput. Geom. 48 (2012), 499--517.
  Also in arXiv:1102.5391.
  
  
• P. K. Agarwal, E. Ezra and M. Sharir,
  Near-linear approximation algorithms for geometric hitting sets,
  Algorithmica 63 (2012), 1--25.
  Also in Proc. 25th ACM Sympos. Comput. Geom., 2009, 23--32.
  
  
• M. Hoffmann, A. Schulz, M. Sharir, A. Sheffer, Cs. D. T\'oth and E. Welzl,
  Counting plane graphs: Flippability in triangulations and its applications,
  in Thirty Essays on Geometric Graph Theory (J. Pach, ed.), Springer Verlag, Heidelberg, 2013, pp. 303--326.
  Also in arXiv:1012.0591.
  See also Proc. 12th Workshop on Algorithms and Data Structures (2011), 524--535.
  
  
• P. K. Agarwal, R. Ben-Avraham and M. Sharir,
  The 2-center problem in three dimensions,
  Comput. Geom. Theory Appl. 46 (2013), 734--746.
  Also in Proc. 26th ACM Symp. on Computational Geometry (2010), 87--96.
  Also in arXiv:1012.2694.
  
  
• H. Kaplan and M. Sharir,
  Finding the maximal empty disk containing a query point,
  Internat. J. Comput. Geom. Appl. 23 (2013), 335--355.
  Also in Proc. 28th ACM Symp. on Computational Geometry (2012), 287--292.
  
  
• A. Sheffer, M. Sharir, and E. Welzl,
  Counting plane graphs: Perfect matchings, spanning cycles, and Kasteleyn's technique,
  J. Combinat. Theory Ser. A, 120 (2013), 777--794.
  Also, Proc. 28th ACM Symp. on Computational Geometry (2012), 189--198.
  Also in arXiv:1109.5596.
  
  
• P. K. Agarwal, J. Matou\v{s}ek, and M. Sharir,
  On range searching with semialgebraic sets II,
  SIAM J. Comput. 42 (2013), 2039--2062.
  Also in Proc. 53rd IEEE Symp. on Foundations of Computer Science (2012), 420--429.
  Also in arXiv 1208.3384.
  
  
• B. Aronov, M. Dulieu, R. Pinchasi, and M. Sharir,
  On the union complexity of diametral disks,
  Electronic J. Combinat. 20(2) (2013), P53.
  
  
• A. Sheffer and M. Sharir,
  Counting plane graphs: Cross-graph charging schemes,
  Combinat. Probab. Comput. 22 (2013), 935--954.
  Also in Proc. Symp. on Graph Drawing (2012), 19--30.
  Also in arXiv:1209.0194.
  
  
• A. Sheffer, M. Sharir, and J. Solymosi,
  Distinct distances on two lines,
  J. Combinat. Theory Ser. A 20 (2013), 1732--1736.
  Also in arXiv:1302.3081.
  
  
• P. K. Agarwal, R. Ben Avraham, H. Kaplan and M. Sharir,
  Computing the discrete Fr\'echet distance in subquadratic time,
  SIAM J. Comput. 43 (2014), 429--449.
  Also in Proc. 24th ACM-SIAM Symp. on Discrete Algorithms (2013), 156--167.
  Also in arXiv:1204.5333.
  
  
• D. Aiger, H. Kaplan and M. Sharir,
  Reporting neighbors in high-dimensional Euclidean spaces,
  SIAM J. Comput. 43 (2014), 1363--1395.
  Also in Proc. 24th ACM-SIAM Symp. on Discrete Algorithms (2013), 784--803.
  
  
• B. Aronov, M. de Berg, E. Ezra, and M. Sharir,
  Improved bound for the union of locally $\gamma$-fat objects,
  SIAM J. Comput. 43 (2014), 543--572.
  
  
• P. K. Agarwal, S. Har-Peled, H. Kaplan and M. Sharir,
  Union of random Minkowski sums and network vulnerability analysis,
  Discrete Comput. Geom. 52 (2014), 551--582.
  Also in Proc. 29th ACM Symp. on Computational Geometry (2013), 177--186.
  Also in arXiv:1310.5647.
  
  
• J. Cilleruelo, A. Sheffer, and M. Sharir,
  On lattices, distinct distances, and the Elekes-Sharir framework,
  Discrete Math. 336 (2014), 37--40.
  Also in arXiv:1306.0242.
  
  
• A. Sheffer, M. Sharir, and J. Zahl,
  Improved bounds for incidences between points and circles,
  Combinat. Probab. Comput. 24 (2015), 490--520.
  Also in Proc. 29th ACM Symp. on Computational Geometry (2013), 97--106.
  Also in arXiv:1208.0053.
  
  
• O. E. Raz, O. Roche-Newton and M. Sharir,
  Sets with few distinct distances do not have heavy lines,
  Discrete Math. 338 (2015), 1484--1492.
  Also in arXiv:1410.1654.
  
  
• T. Kaminker and M. Sharir,
  Finding the largest disk containing a query point in logarithmic time with linear storage.
  J. Comput. Geom. 6(2) (2015), 3--18.
  Also in Proc. 30th ACM Symp. on Computational Geometry (2014), 206--213.
  Also in arXiv:1310.3388.
  
  
• H. Kaplan, S. Mozes, Y. Nussbaum and M. Sharir,
  Submatrix maximum queries in Monge matrices and Monge partial matrices, and their applications,
  ACM Trans. Algorithms 3(2) (2017), Article 26.
  Also in Proc. 23rd ACM-SIAM Symp. on Discrete Algorithms (2012), 338--355.
  
  
• M. Sharir and J. Solymosi,
  Distinct distances from three points,
  Combinat. Probab. Comput. 25 (2016), 623--632.
  Also in arXiv:1308.0814.
  
  
• M. Sharir and S. Zaban,
  Output-sensitive tools for range searching in higher dimensions,
  
  
• O. E. Raz, M. Sharir and J. Solymosi,
  Polynomials vanishing on grids: The Elekes-R\'onyai problem revisited,
  Amer. J. Math. 138 (2016), 1029--1065.
  Also in Proc. 30th ACM Symp. on Computational Geometry (2014), 251--260.
  Also in arXiv:1401.7419.
  
  
• O. E. Raz, M. Sharir and J. Solymosi,
  On triple intersections of three families of unit circles,
  Discrete Comput. Geom. 54 (2015), 930-- 953.
  Also in Proc. 30th ACM Symp. on Computational Geometry (2014), 198--205.
  Also in arXiv:1407.6625.
  
  
• R. Ben Avraham, O. Filtser, H. Kaplan, M. Katz, and M. Sharir,
  The discrete and semicontinuous Fr\'echet distance with shortcuts via approximate distance counting and selection,
  in arXiv:1310.5245. This is a revision of the versions in
  ACM Trans. Algorithms 11 (2015), Article 29, and in
  Proc. 30th ACM Symp. on Computational Geometry (2014), 377--386.
  
  
• M. Sharir and N. Solomon,
  Incidences between points and lines in four dimensions,
  Proc. 30th ACM Symp. on Computational Geometry (2014), 189--197.
  
  
• P. K. Agarwal, H. Kaplan, N. Rubin, and M. Sharir,
  Kinetic Voronoi diagrams and Delaunay triangulations under polygonal distance functions,
  Discrete Comput. Geom. 54 (2015), 871--904.
  Also in arXiv:1404.4851.
  
  
• P. K. Agarwal, J. Gao. L. Guibas, H. Kaplan, N. Rubin and M. Sharir,
  Stable Delaunay graphs,
  Discrete Comput. Geom. 54 (2015), 905--929.
  New version in arXiv:1504.06851.
  
  
• M. Sharir, A. Sheffer, and N. Solomon,
  Incidences with curves in $R^d$.
  Electronic J. Combinat.} 23(4) (2016), P4.16.
  Also in Proc. European Sympos. Algorithms, (2015), 977--988.
  Also in arXiv:1512.08267.
  
  
• S. Kalia, M. Sharir, N. Solomon, and B. Yang,
  Generalizations of the Szemer\'edi-Trotter theorem,
  Discrete Comput. Geom., 55 (2016), 571--593.
  Also in arXiv:1408.5915v2.
  
  
• S. Har-Peled, H. Kaplan, M. Sharir, and S. Smorodinsky,
  Epsilon-nets for halfspaces revisited,
  In arXiv:1410.3154.
  
  
• M. Sharir and N. Solomon,
  Incidences between points and lines in $\reals^4$,
  Discrete Comput. Geom. 57 (2017), 702--756.
  Also in Proc. 56th IEEE Symp. Foundations of Computer Science, (2015), 1378--1394.
  Also in arXiv:1411.0777.
  
  
• O. E. Raz and M. Sharir,
  Unit-area triangles in the plane: Theme and variation,
  Combinatorica 37 (2017), 1221--1240.
  Also in Proc. 31st Symp. on Computational Geometry (2015), 569--583.
  Also in arXiv:1501.00379.
  
  
• M. Sharir and N. Solomon,
  Incidences between points and lines in three dimensions,
  in it New Trends in Intuitive Geometry (G. Ambrus, I. B\'ar\'any, K. B\"or\"oczky, G. Fejes-T\'oth, J. Pach, Eds.),
  Bolyai Soc. Math. Studies (BSMS, Vol. 27), Springer, 2018, pages 359--383.
  Also in arXiv:1501.02544.
  Also in Proc. 31st Symp. on Computational Geometry (2015), 553--568.
  
  
• O. E. Raz, M. Sharir and F. de Zeeuw,
  Polynomials vanishing on Cartesian products: The Elekes--Szab\'o theorem revisited,
  Duke Math. J. 165(18) (2016), 3517--3566.
  Also in Proc. 31st Symp. on Computational Geometry (2015), 522--536.
  Also in arXiv:1504.05012
  
  
• M. Sharir and N. Solomon,
  Incidences between points and lines on a two-dimensional variety,
  in arXiv:1501.01670.
  
  
• R. Ben Avraham, H. Kaplan, and M. Sharir,
  A faster algorithm for the discrete Fr\'echet distance under translation,
  in arXiv:1501.03724.
  
  
• O. E. Raz, M. Sharir and I. D. Shkredov
  On the number of unit-area triangles spanned by convex grids in the plane,
  Comput. Geom. Theory Appls. 62 (2017), 25--33.
  Also in arXiv:1504.06989.
  
  
• S. Har-Peled, H. Kaplan, and M. Sharir,
  Approximating the k-level in three-dimensional plane arrangements,
  in Journey through Discrete Mathematics: A Tribute to Ji\v{r}\'{\i} Matou\v{s}ek,
  M. Loebl, J. Ne\v{s}et\v{r}il, and R. Thomas (editors), Springer Verlag, Berlin-Heidelberg, 2017, pp.~467--504.
  Also in Proc. 27th ACM-SIAM Sympos. Discrete Algorithms, (2016), 1193--1212.
  Also in arXiv:1601.04755.
  
  
• O. Gold and M. Sharir,
  Improved bounds for 3SUM, $k$-SUM, and linear degeneracy,
  Proc. 25th European Sympos. Algorithms, (2017), 42:1--42:13.
  Also in arXiv:1512.05279v2.
  
  
• M. Sharir and J. Zahl,
  Cutting algebraic curves into pseudo-segments and applications,
  J. Combinat. Theory Ser. A 150 (2017), 1--35.
  Also in arXiv:1604.07877.
  
  
• D. Halperin and M. Sharir,
  Arrangements,
  Chapter 28, Handbook of Discrete and Computational Geometry,
  (J. E. Goodman, J. O'Rourke, and C. D. T\'oth, Eds.),
  CRC Press, Boca Raton, Florida, Third Edition, 2018.
  
  
• D. Halperin, O. Salzman and M. Sharir,
  Algorithmic motion planning,
  Chapter 50, Handbook of Discrete and Computational Geometry,
  (J. E. Goodman, J. O'Rourke, and C. D. T\'oth, Eds.),
  CRC Press, Boca Raton, Florida, Third Edition, 2018.
  
  
• O. Gold and M. Sharir,
  Dominance products and faster algorithms for high-dimensional closest pair under $L_\infty$,
  Proc. 28th Internat. Sympos. Algorithms and Computation, (2017), 39:1--39:12.
  Also in arXiv:1605.08107.
  
  
• P. K. Agarwal, N. Rubin, and M. Sharir,
  Approximate nearest neighbor search amid higher-dimensional flats,
  Proc. 25th European Sympos. Algorithms, (2017), 4:1--4:13.
  
  
• O. Gold and M. Sharir,
  Dynamic time warping: Breaking the quadratic barrier,
  ACM Trans. Algo., Art. 50.
  Also in Proc. Int. Colloq. Automata, Languages, Programming (2017), 25:1--25:14.
  Also in arXiv:1607.05994.
  
  
• M. Sharir and N. Solomon,
  Incidences between points and surfaces and points and curves, and distinct and repeated distances in three dimensions,
  Proc. 28th ACM-SIAM Symp. on Discrete Algorithms (2017), 2456--2475.
  Also in arXiv:1610.01560.
  
  
• M. Sharir and N. Solomon,
  Incidences between points and lines on two- and three-dimensional varieties,
  Discrete Comput. Geom., 59 (2018), 88--130.
  Also in arXiv:1609.09026.
  
  
• R. Ben Avraham, M. Henze, R. Jaume, B. Keszegh, O. E. Raz, M. Sharir, and I. Tubis,
  The minimum Hausdorff and partial matching RMS-distance under translation: Combinatorics and algorithms,
  Algorithmica, 80 (2018), 2400--2421.
  Also in Proc. European Sympos. Algorithms, (2014), 100--111.
  Also in arXiv:1411.7273.
  
  
• M. Sharir, S. Smorodinsky, C. Valculescu, and F. de Zeeuw,
  Distinct distances between points and lines,
  Comput. Geom. Theory Appls., 69 (2018), 2--15.
  Also in arXiv:1512.09006.
  
  
• O. E. Raz, M. Sharir, and F. de Zeeuw,
  The Elekes--Szab\'o theorem in four dimensions,
  Israel J. Math. 227 (2018) 663--690.
  Also in arXiv:1607.03600.
  
  
• A. Bruner and M. Sharir,
  Distinct distances between a collinear set and an arbitrary set of points,
  Discrete Math., 341 (2018), 261--265.
  Also in arXiv:1612.04940.
  
  
• D. Aiger and M. Sharir,
  Homotheties and incidences.
  Discrete Math., 341 (2018), 2011--2017.
  Also in arXiv:1709.02933.
  
  
• B. Aronov and M. Sharir,
  Almost tight bounds for eliminating depth cycles in three dimensions,
  Discrete Comput. Geom., 59 (2018), 725--741.
  Also in Proc. 48th ACM Sympos. Theory of Computing, (2016), 1--8.
  Also in arXiv:1512.00358.
  
  
• P. K. Agarwal, H. Kaplan, G. Kipper, W. Mulzer, G. Rote, M. Sharir, and A. Xiao,
  Approximate minimum-weight matching with outliers under translation,
  Proc. 29th Internat. Sympos. Algorithms and Computation (2018), 26:1--26:13.
  Also in arXiv:1810.10466.
  
  
• E. Ezra and M. Sharir,
  A nearly quadratic bound for point location in hyperplane arrangements, in the linear decision tree model,
  Discrete Comput. Geom. 61 (2019), 735--755.
  A preliminary version in Proc. 33rd Symp. on Computational Geometry (2017), 41:1--41:15.
  Also in arXiv:1607.04336.
  
  
• M. Sharir and C. Ziv,
  On levels in arrangements of pseudo-planes in three dimensions,
  Discrete Math. 344 (2021), Article 112354.
  Also in Proc. 35th Sympos. Comput. Geom. (2019), 62:1--62:15.
  Also in arXiv:1903.07196.
  
  
• D. Aiger, H. Kaplan, E. Kokiopoulou, M. Sharir and B. Zeisl,
  General techniques for approximate incidences and their application to the camera posing problem,
  Proc. 35th Sympos. Comput. Geom. (2019), 8:1--8:14.
  Also in arXiv:1903.07047.
  
  
• H. Kaplan, K. Klost, W. Mulzer, L. Roditty and M. Sharir,
  Triangles and girth in disk graphs and transmission graphs,
  Proc. European Sympos. Algorithms (2019), 64:1--64:14.
  Also in arXiv:1907.01980.
  
  
• H. Kaplan, S. Roy and M. Sharir,
  Finding axis-parallel rectangles of fixed perimeter or area containing the largest number of points,
  Comput. Geom. Theory Appls. 81 (2019), 1--11.
  Also in Proc. 25th European Sympos. Algorithms, (2017), 52:1--52:13.
  
  
• D. Aiger, H. Kaplan, and M. Sharir,
  Output sensitive algorithms for approximate incidences and their applications,
  Comput. Geom. Theory Appls. 91 (2020), Art.~101666.
  Also in Proc. 25th European Sympos. Algorithms, (2017), 5:1--5:13.
  
  
• M. Sharir and O. Zlydenko,
  Incidences with curves with almost two degrees of freedom,
  Proc. 36th Sympos. on Computational Geometry (2020), 66:1--66:14.
  A revised version is:
  M. Sharir, N. Solomon and O. Zlydenko,
  Incidences with curves with almost two degrees of freedom,
  J. Combinat. Theory Ser. A 188 (2022), Art.~105582.
  Also in arXiv:2003.02190.
  
  
• M. Sharir and J. Zahl,
  Erratum: ``Breaking the 3/2-barrier for unit distances in three dimensions,''
  Internat. Math. Res. Notices, in press.
  Published online 24 August 2021.
  
  
• H. Kaplan, M. Sharir and U. Stemmer,
  How to find a point in the convex hull privately,
  Proc. 36th Sympos. on Computational Geometry (2020), 52:1--52.15.
  Also in arXiv:2003.13192.
  
  
• D. Halperin, S. Har-Peled, K. Mehlhorn, E. Oh and M. Sharir,
  The maximum-level vertex in an arrangement of lines.
  Discrete Comput. Geom. 67 (2022), 439--461.
  Also in arXiv:2003.00518.
  
  
• E. Ezra, S. Har-Peled, H. Kaplan and M. Sharir,
  Decomposing arrangements of hyperplanes: VC-dimension, combinatorial dimension, and point location.
  Discrete Comput. Geom. 64 (2020), 109--173.
  Also in arXiv:1712.02913.
  
  
• B. Aronov, E. Miller and M. Sharir,
  Eliminating depth cycles among triangles in three dimensions,
  Discrete Comput. Geom. 64 (2020), 627--653.
  (Ricky Pollack's memorial issue.)
  Also in Proc. 28th ACM-SIAM Symp. on Discrete Algorithms (2017), 2476--2494.
  Also in arXiv:1607.06136.
  
  
• H. Kaplan, W. Mulzer, L. Roditty, P. Seiferth, and M. Sharir,
  Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications,
  Discrete Comput. Geom. 64 (2020), 838--904.
  (Ricky Pollack's memorial issue.)
  Also in Proc. 28th ACM-SIAM Symp. on Discrete Algorithms (2017), 2495--2504.
  Also in arXiv:1604.03654.
  
  
• D. Halperin, M. van Kreveld, G. Miglioli-Levy and M. Sharir,
  Space-aware reconfiguration,
  Discrete Comput. Geom. 69 (2023), 1157--1194.
  Also in Proc. Workshop on Algorithmic Foundations of Robotics (WAFR 2020), 37--53.
  Also in arXiv:2006.04402.
  
  
• S. Artstein-Avidan, H. Kaplan and M. Sharir,
  On radial isotropic position: Theory and algorithms,
  in arXiv:2005.04918.
  
  
• D. Aiger, H. Kaplan, and M. Sharir,
  Duality-based approximation algorithms for depth queries and maximum depth,
  in arXiv:2006.12318.
  
  
• M. Sharir and N. Solomon,
  Incidences with curves in three dimensions,
  in arXiv:2007.04081.
  
  
• P. K. Agarwal, M. Sharir and A. Steiger,
  Decomposing the complement of the union of cubes and boxes in three dimensions,
  Discrete Comput. Geom., 72 (2024), 407--450.
  Also in Proc. 32nd ACM-SIAM Sympos. on Discrete Algorithms (2021), 1425--1444.
  
  
• S. Har-Peled, H. Kaplan, W. Mulzer, L. Roditty, P. Seiferth, M. Sharir, and M. Willert,
  Stabbing pairwise intersecting disks by five points,
  Discrete Math. 344(7) (2021), Art.~112403.
  Also in Proc. 29th Internat. Sympos. Algorithms and Computation (2018), 50:1--50:12.
  Also in Proc. 18th Euro-CG (2018), 29:1--29:6.
  Also in arXiv:1801.03158.
  
  
• E. Ezra, O. Raz, M. Sharir and J. Zahl,
  Counting and cutting rich lenses in arrangements of circles,
  SIAM J. Discrete Math. 36 (2022), 958--974.
  Also in Proc. 37th Sympos. on Computational Geometry (2021), 35:1--35:15.
  Also in arXiv:2012.04204.
  
  
• M. Sharir and N. Solomon,
  On rich points and incidences with restricted sets of lines in 3-space,
  J. Comput. Geom. 13 (2022), 51--72.
  Also in Proc. 37th Sympos. on Computational Geometry (2021), 56:1--56:14.
  Also in arXiv:2012.11913.
  
  
• D. Halperin, M. Sharir and I. Yehuda,
  Throwing a sofa through the window,
  Discrete Comput. Geom., in press.
  Pubished online, October 6, 2023.
  Also in Proc. 37th Sympos. on Computational Geometry (2021), 41:1--41:16.
  Also in arXiv:2102.04262.
  
  
• E. Ezra and M. Sharir,
  On ray shooting for triangles in 3-space and related problems,
  SIAM J. Comput. 51 (2022), 1065--1095.
  Also in Proc. 37th Sympos. on Computational Geometry (2021), 34:1--34:15.
  Also in arXiv:2102.07310.
  
  
• P. K. Agarwal, H. Kaplan and M. Sharir,
  Union of hypercubes and 3d Minkowski sums with random sizes,
  Discrete Comput. Geom., 65 (2021), 1136--1165.
  Also in Proc. 45th Int. Colloq. Automata, Languages, Programming (2018), 10:1--10:15.
  
  
• P. Gawrychowski, H. Kaplan, S. Mozes, M. Sharir and O. Weimann,
  Voronoi diagrams on planar graphs, and computing the diameter in deterministic $\tilde{O}(n^{5/3})$ time,
  SIAM J. Comput. 50 (2021), 509--554.
  Also in Proc. 29th ACM-SIAM Sympos. on Discrete Algorithms (2018), 495--514.
  Also in arXiv:1704.02793.
  
  
• B. Aronov, M. de Berg, J. Cardinal, E. Ezra, J. Iacono and M. Sharir,
  Subquadratic algorithms for some 3SUM-hard geometric problems in the algebraic decision-tree model,
  Comput. Geom. Theory Appls. 109 (2023), Art.~101945.
  Also in Proc. 32nd Internat. Sympos. Algorithms and Computation (2021), 3:1--3:15.
  Also in arXiv:2109.07587.
  
  
• P. K. Agarwal, B. Aronov, E. Ezra, M. Katz and M. Sharir,
  Intersection queries for flat semi-algebraic objects in three dimensions and related problems,
  Proc. 38th Sympos. on Computational Geometry (2022), 4:1--4:14.
  Also in arXiv:2203.10241.
  
  
• Z. Pat\'akov\'a and M. Sharir,
  Covering points by hyperplanes and related problems,
  Proc. 38th Sympos. on Computational Geometry (2022), 57:1--57:7.
  
  
• E. Ezra, M. Sharir, and T. Tsabari,
  Ray shooting amid tetrahedra in four dimensions,
  Proc. 38th EuroCG (2022), 36:1--36:5.
  
  
• B. Aronov, E. Ezra, M. Sharir and G. Zigdon,
  Time and space efficient collinearity indexing,
  Comput. Geom. Theory Appls. 110 (2023), Art.~101963.
  Also in Proc. 38th EuroCG (2022), 52:1--52:6.
  
  
• M. J. Katz and M. Sharir,
  Bottleneck matching in the plane,
  Comput. Geom. Theory Appls., 112 (2023), Art.~101986.
  Also in arXiv:2205.05887.
  
  
• E. Ezra and M. Sharir,
  Intersection searching amid tetrahedra in four dimensions,
  Discrete Comput. Geom., available online, June 3, 2024.
  Also in Proc. 30th European Sympos. Algorithms (2022), 51:1--51:17.
  Also in arXiv:2208.06703.
  
  
• P. K. Agarwal, M. Katz and M. Sharir,
  On reverse shortes paths in geometric proximity graphs,
  Comput. Geom. Theory Appls., 117 (2024), Art.~102053.
  Also in Proc. 33rd Internat. Sympos. Algorithms and Computation (2022), 42:1--42:19.
  
  
• B. Aronov, E. Ezra and M. Sharir,
  Testing polynomials for vanishing on Cartesian products of planar point sets,
  Discrete Comput. Geom. 68 (2022), 997--1048.
  Also in Proc. 36th Sympos. on Computational Geometry (2020), 8:1--8:14.
  Also in arXiv:2003.09533.
  
  
• J. Cardinal and M. Sharir,
  Improved algebraic degeneracy testing,
  Discrete Comput. Geom., accepted.
  
  Also in Proc. 39th Sympos. on Computational Geometry (2023), 22:1--22:16.
  Also in arXiv:2212.03030.
  
  
• H. Kaplan, M. J. Katz, R. Saban and M. Sharir,
  The unweighted and weighted reverse shortest path problem for disk graphs,
  Proc. 31st European Sympos. Algorithms (2023), 67:1--67:14.
  Also in arXiv:2307.14663.
  
  
• P. K. Agarwal, D. Halperin, M. Sharir and A. Steiger,
  Near-optimal min-sum motion planning for two square robots in a polygonal environment,
  Proc. 35th ACM-SIAM Sympos. on Discrete Algorithms (2024), 4942--4962.
  Also in arXiv:2310.20615.
  
  
• P. K. Agarwal, E. Ezra and M. Sharir,
  Vertical decomposition in 3D and 4D with applications to line nearest-neighbor searching in 3D,
  Proc. 35th ACM-SIAM Sympos. on Discrete Algorithms (2024), 150--170.
  Also in arXiv:2311.01597.
  
  
• P. K. Agarwal, E. Ezra and M. Sharir,
  Semi-algebraic off-line range searching and biclique partitions in the plane,
  Proc. 40th Sympos. on Computational Geometry (2024), 4:1--4:15.
  Also in arXiv:2403.12276.
  
  
• N. Alon, A. Holmsen, J. Pach and M. Sharir,
  Eli Goodman (1933--2021) and Ricky Pollack (1935--2018),
  Notices AMS, in press.
  
  
• P. K. Agarwal, E. Ezra and M. Sharir,
  Lower envelopes of surface patches in 3-space,
  Proc. 32nd European Sympos. Algorithms (2024), 6:1--6:17.
  
  
• M. J. Katz, R. Saban and M. Sharir,
  Near-linear algorithms for visibility graphs over a 1.5-dimensional terrain,
  Proc. 32nd European Sympos. Algorithms (2024), 77:1--77:17.
  
  
• P. K. Agarwal, H. Kaplan, M. J. Katz and M. Sharir,
  Segment proximity graphs and nearest neighbor queries amid disjoint segments,
  Proc. 32nd European Sympos. Algorithms (2024), 7:1--7:20.
  
  
• N. Alon, A. Holmsen, J. Pach and M. Sharir,
  Eli Goodman (1933--2021) and Ricky Pollack (1935--2018) (Goodman-Pollack memorial article),
  Notices AMS 71(8) (2024), 1044--1053.
  
  

Last update: June 12, 2024