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:

Recent Papers:

• M. Sharir and P.K. Agarwal,
  Davenport-Schinzel Sequences and Their Geometric Applications,
  Cambridge University Press, Cambridge-New York-Melbourne, 1995.
  
  
• 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.
  
  
• 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.
  
  
• M. Sharir,
  A near-linear algorithm for the planar 2-center problem,
  Discrete Comput. Geom. 18 (1997), 125--134.
  
  
• G. Barequet and M. Sharir,
  Piecewise-linear interpolation between polygonal slices,
  Computer Vision and Image Understanding 63 (1996), 251--272.
  
  
• 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.
  
  
• 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.
  
  
• P. Agarwal and M. Sharir,
  Efficient algorithms for geometric optimization,
  ACM Computing Surveys 30 (1998), 412--458.
  
  
• 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.
  
  
• 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.
  
  
• 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.
  
  
• B. Aronov and M. Sharir,
  On translational motion planning of a convex polyhedron in 3-space,
  SIAM J. Computing 26 (1997), 1785--1803.
  
  
• 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.
  
  
• 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.
  
  
• A. Efrat and M. Sharir,
  A near-linear algorithm for the planar segment center problem,
  Discrete Comput. Geom. 16 (1996), 239--257.
  
  
• 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.
  
  
• B. Aronov, M. Sharir and B. Tagansky,
  The union of convex polyhedra in three dimensions,
  SIAM J. Computing. 26 (1997), 1670--1688.
  
  
• M. Sharir,
  Excess in arrangements of segments,
  Information Processing Letters 58 (1996), 245--247.
  
  
• P. Agarwal, N. Amenta and M. Sharir,
  Largest placement of one convex polygon inside another,
  Discrete Comput. Geom. 19 (1998), 95--104.
  
  
• 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.
  
  
• 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, 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.
  
  
• 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.
  
  
• 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.
  
  
• 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.
  
  
• K. Kedem, M. Sharir and S. Toledo,
  On critical orientations in the Kedem-Sharir motion planning algorithm,
  Discrete Comput. Geom. 17 (1997), 227--239.
  
  
• S. Smorodinski, J. Mitchell and M. Sharir,
  Geometric permutations of pairwise disjoint balls,
  Discrete Comput. Geom., 23 (2000), 247--259.
  
  
• 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. Agarwal, B. Aronov, J. Pach, R. Pollack and M. Sharir,
  Quasi-planar graphs have a linear number of edges,
  Combinatorica 17 (1997), 1--9.
  
  
• J. Pach and M. Sharir,
  On the number of incidences between points and curves.
  Combinat. Probab. Comput. 7 (1998), 121--127.
  
  
• 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.
  
  
• 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.
  
  
• 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.
  
  
• M. Sharir and E. Welzl,
  Rectilinear and polygonal p-piercing and p-center problems,
  Proc. 12th ACM Symp. on Computational Geometry (1996), to appear.
  
  
• 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 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.
  
  
• P. Agarwal, B. Aronov and M. Sharir,
  Exact and approximation algorithms for minimum-width cylindrical shells,
  Discrete Comput. Geom. 26 (2001), 307--320.
  
  
• 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.
  
  
• 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.
  
  
• D. Halperin, M. Sharir and K. Goldberg,
  The 2-center problem with obstacles,
  J. Algorithms 42 (2002), 109--134.
  
  
• 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.
  
  
• 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.
  
  
• P. Agarwal and M. Sharir,
  Pseudoline arrangements: Duality, algorithms and applications,
  SIAM J. Comput., 34 (2005), 526--552.
  
  
• 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.
  
  
• P. Agarwal and M. Sharir,
  On the number of congruent simplices in a point set,
  Discrete Comput. Geom. 28 (2002), 123--150.
  
  
• 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.
  
  
• M. Sharir,
  The Clarkson-Shor technique revisited and extended,
  Combinat. Probab. Comput. 12 (2003), 191--201.
  
  
• 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.
  
  
• G. Pustylnik and M. Sharir,
  The Minkowski sum of a simple polygon and a segment,
  Information Processing Letters 85 (2003), 179--184.
  
  
• 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.
  
  
• 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.
  
  
• 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.
  
  
• 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.
  
  
• M. Sharir and E. Welzl,
  Point-line incidences in space,
  Combinat. Probab. Comput. 13 (2004), 203--220.
  
  
• 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.
  
  
• 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.
  
  
• 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.
  
  
• 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.
  
  
• 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.
  
  
• V. Koltun and M. Sharir,
  Curve-sensitive cuttings,
  SIAM J. Comput. 34 (2005), 863--878.
  
  
• 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.
  
  
• M. Sharir and H. Shaul,
  Ray shooting and stone throwing with near-linear storage,
  Comput. Geom. Theory Appl., 30 (2005), 239--252.
  
  
• B. Aronov and M. Sharir,
  Cell complexities in hyperplane arrangements,
  Discrete Comput. Geom. 32 (2004), 107--115.
  
  
• 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.
  
  
• 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.
  
  
• 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.
  
  
• 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. 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. Oks and M. Sharir,
  Minkowski sums of monotone and general simple polygons,
  Discrete Comput. Geom. 35 (2006), 223--240.
  
  
• 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.
  
  
• 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, M. Sharir and E. Welzl,
  Algorithms for center and Tverberg points,
  ACM Trans. Algorithms 5 (2008), Article 5.
  
  
• 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.
  
  
• 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.
  
  
• 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.
  
  
• 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.
  
  
• 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 and M. Sharir,
  A single cell in an arrangement of convex polyhedra in R^3,
  Discrete Comput. Geom., 37 (2007), 21--41.
  
  
• 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.
  
  
• 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.
  
  
• 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.
  
  
• V. Koltun and M. Sharir,
  A note on overlays of minimization diagrams,
  Discrete Comput. Geom. 41 (2009), 385--397.
  
  
• M. Sharir and E. Welzl,
  Random triangulations of planar point sets,
  Proc. 22nd ACM Symp. on Computational Geometry (2006), 273--281.
  
  
• E. Ezra, M. Sharir and A. Efrat,
  On the ICP algorithm,
  Comput. Geom. Theory Appls., 41 (2008), 77--93.
  
  
• 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.
  
  
• J. Pach and M. Sharir,
  On planar intersection graphs with forbidden subgraphs,
  J. Graph Theory 59 (2008), 205--214.
  
  
• R. Apfelbaum and M. Sharir,
  Large bipartite graphs in incidence graphs of points and hyperplanes,
  SIAM J. Discrete Math. 21 (2007), 707--725.
  
  
• 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.
  
  
• 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.
  
  
• 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.
  
  
• 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,
  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.
  
  
• 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.
  
  
• 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).
  
  
• 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.
  
  
• 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.
  
  
• 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.
  
  
• 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.
  
  
• 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,
  Discrete Comput. Geom., submitted.
  
  
• 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.
  
  
• M. Sharir and H. Shaul,
  Semi-algebraic range reporting and emptiness searching with applications,
  SIAM J. Comput., 40 (2011), 1045--1074.
  
  
• 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.
  
  
• 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.
  
  
• 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.
  
  
• P. K. Agarwal, R. Ben-Avraham and M. Sharir,
  The 2-center problem in three dimensions,
  Comput. Geom. Theory Appl., in press (published online November 16, 2012). Also in Proc. 26th ACM Symp. on Computational Geometry (2010), 87--96. Also in arXiv:1012.2694.
  
  
• H. Kaplan, M. Katz, G. Morgenstern and M. Sharir,
  Optimal cover of points by disks in a simple polygon,
  Proc. European Symposium on Algorithms (2010), 475--486. Also in SIAM J. Comput. 40 (2011), 1647--1661.
  
  
• 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.
  
  
• 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.
  
  
• 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.), in press. Also in arXiv:1012.0591.
  See also Proc. 12th Workshop on Algorithms and Data Structures (2011), 524--535.
  
  
• 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.
  
  
• H. Kaplan, S. Mozes, Y. Nussbaum and M. Sharir,
  Submatrix maximum queries in Monge matrices and Monge partial matrices, and their applications,
  SIAM J. Comput., submitted.
  Also in Proc. 23rd ACM-SIAM Symp. on Discrete Algorithms (2012), 338--355.
  
  
• H. Kaplan and M. Sharir,
  Finding the maximal empty rectangle containing a query point,
  In arXiv:1106.3628.
  
  
• H. Kaplan and M. Sharir,
  Finding the maximal empty disk containing a query point,
  Internat. J. Comput. Geom. Appl., accepted.
  Also in Proc. 28th ACM Symp. on Computational Geometry (2012), 287--292.
  
  
• 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.
  
  
• 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.
  
  
• A. Sheffer, M. Sharir, and E. Welzl,
  Counting plane graphs: Perfect matchings, spanning cycles, and Kasteleyn's technique,
  Proc. 28th ACM Symp. on Computational Geometry (2012), 189--198. Also, J. Combinat. Theory Ser. A, in press. 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., accepted.
  Also in Proc. 53rd IEEE Symp. on Foundations of Computer Science (2012), 420--429. Also in arXiv 1208.3384.
  
  
• A. Sheffer and M. Sharir,
  Counting plane graphs: Cross-graph charging schemes,
  Combinat. Probab. Comput., accepted.
  Also in Proc. Symp. on Graph Drawing (2012), 19--30. Also in arXiv:1209.0194.
  
  
• P. K. Agarwal, R. Ben Avraham, H. Kaplan and M. Sharir,
  Computing the discrete Fr\'echet distance in subquadratic time,
  SIAM J. Comput., submitted.
  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., submitted.
  Also in Proc. 24th ACM-SIAM Symp. on Discrete Algorithms (2013), 784--803.
  
  
• B. Aronov, M. Dulieu, R. Pinchasi, and M. Sharir,
  On the union complexity of diametral disks,
  Electronic J. Combinat., accepted.
  
  
• B. Aronov, M. de Berg, E. Ezra, and M. Sharir,
  Improved bound for the union of locally $\gamma$-fat objects,
  SIAM J. Comput., submitted.
  
  
• A. Sheffer and M. Sharir,
  Distinct distances on two lines,
  J. Combinat. Theory Ser. A, accepted. Also in arXiv:1302.3081.
  
  
• A. Sheffer, M. Sharir, and J. Zahl,
  Improved bounds for incidences between points and circles,
  Proc. 29th ACM Symp. on Computational Geometry (2013), to appear. Also in arXiv:1208.0053.
  
  
• P. K. Agarwal, H. Kaplan and M. Sharir,
  Union of random Minkowski sums and network vulnerability analysis,
  Proc. 29th ACM Symp. on Computational Geometry (2013), to appear.
  

Last update: May 3, 2013