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
 97236408804 (voice)
 97236409373 (fax)
 michas at post.tau.ac.il
>
>
>
>
Biosketch:
See here
Current Interests:
Computational Geometry,
Combinatorical Geometry,
Geometric Optimization
Slides of the talk
From joints to distinct distances and beyond: The
dawn of an algebraic era in combinatorial geometry
And of the more recent talk
The Algebraic Revolution in Combinatorial and Computational Geometry:
State of the Art,
presented at SoCG'17
And of the even more recent version
Algebraic Techniques in Geometry: State of (Some of) the Art ,
presented at SoCG'19
Courses:
Computational Geometry
Advanced Topics in Computational Geometry
Algorithms
Geometric Optimization
B.Sc. Seminar on Computational Geometry
Research Seminar on Computational Geometry
Papers:
(Some links do not point to a file; please contact me by email if you
need a copy.)
The list includes papers from circa 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), 298351.

M. Sharir and P.K. Agarwal,
DavenportSchinzel Sequences and Their Geometric Applications,
Cambridge University Press, CambridgeNew YorkMelbourne, 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, 495511.

P. Agarwal and M. Sharir,
Algorithmic techniques for geometric optimization,
Lecture Notes in Computer Science, Vol. 1000 (J. van Leeuwen, Ed.),
SpringerVerlag, Berlin, 1995, 234253.

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 3space and its applications,
Discrete Comput. Geom. 15 (1996), 113.

A. Efrat and M. Sharir,
A nearlinear algorithm for the planar segment center problem,
Discrete Comput. Geom. 16 (1996), 239257.

M. Sharir,
Excess in arrangements of segments,
Information Processing Letters 58 (1996), 245247.

J. Matou\v{s}ek, M. Sharir and E. Welzl,
A subexponential bound for linear programming and related problems,
Algorithmica 16 (1996), 498516.

P.K. Agarwal and M. Sharir,
Efficient randomized algorithms for some geometric optimization problems,
Discrete Comput. Geom. 16 (1996), 317337.

D. Halperin and M. Sharir,
A nearquadratic algorithm for planning the motion of a polygon
in a polygonal environment,
Discrete Comput. Geom. 16 (1996), 121134.

G. Barequet and M. Sharir,
Piecewiselinear interpolation between polygonal slices,
Computer Vision and Image Understanding 63 (1996), 251272.

P. Agarwal, M. de Berg, D. Halperin and M. Sharir,
Efficient generation of kdirectional assembly sequences.
Proc. 7th ACMSIAM Symp. on Discrete Algorithms (1996), 122131.

M. Sharir and E. Welzl,
Rectilinear and polygonal ppiercing and pcenter problems,
Proc. 12th ACM Symp. on Computational Geometry (1996), 122132.

P.K. Agarwal, S. HarPeled, M. Sharir and K. Varadarajan,
Approximate shortest paths on a convex polytope in three dimensions,
J. Assoc. Comput. Mach. 44 (1997), 567584.

P. Agarwal, B. Aronov, J. Pach, R. Pollack and M. Sharir,
Quasiplanar graphs have a linear number of edges,
Combinatorica 17 (1997), 19.

O. Schwarzkopf and M. Sharir,
Vertical decomposition of a single cell in a 3dimensional arrangement
of surfaces,
Discrete Comput. Geom. 18 (1997), 269288.

M. Sharir,
A nearlinear algorithm for the planar 2center problem,
Discrete Comput. Geom. 18 (1997), 125134.

G. Barequet and M. Sharir,
Partial surface and volume matching in three dimensions,
IEEE Trans. on Pattern Analysis and Machine Intelligence
19 (9) (1997), 929948.

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, 733754.

B. Aronov and M. Sharir,
On translational motion planning of a convex polyhedron in 3space,
SIAM J. Computing 26 (1997), 17851803.

B. Aronov and M. Sharir,
The common exterior of convex polygons in the plane,
Computational Geometry, Theory and Appls. 8 (1997), 139149.

P.K. Agarwal, B. Aronov and M. Sharir,
Computing envelopes in four dimensions with applications,
SIAM J. Computing 26 (1997), 17141732.

M. Katz and M. Sharir,
An expanderbased approach to geometric optimization,
SIAM J. Computing. 26 (1997), 13841408.

S. Mohaban and M. Sharir,
Ray shooting amidst spheres in 3 dimensions and related problems,
SIAM J. Computing. 26 (1997), 654674.

B. Aronov, M. Sharir and B. Tagansky,
The union of convex polyhedra in three dimensions,
SIAM J. Computing. 26 (1997), 16701688.

G. Barequet and M. Sharir,
Partial surface and volume matching in three dimensions,
IEEE Trans. on Pattern Recognition and Machine Intelligence
19 (9) (1997), 929948.

K. Kedem, M. Sharir and S. Toledo,
On critical orientations in the KedemSharir motion planning algorithm,
Discrete Comput. Geom. 17 (1997), 227239.

J. Pach and M. Sharir,
On the number of incidences between points and curves.
Combinat. Probab. Comput. 7 (1998), 121127.

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), 485519.

P. Agarwal, B. Aronov, T. Chan and M. Sharir,
On levels in arrangements of lines, segments, planes, and triangles,
Discrete Comput. Geom. 19 (1998), 315331.

P. Agarwal and M. Sharir,
Efficient algorithms for geometric optimization,
ACM Computing Surveys 30 (1998), 412458.

P. Agarwal, N. Amenta and M. Sharir,
Largest placement of one convex polygon inside another,
Discrete Comput. Geom. 19 (1998), 95104.

P. Agarwal, M. Sharir and E. Welzl,
The discrete 2center problem,
P. Agarwal, M. Sharir and E. Welzl,
The discrete 2center problem.
Discrete Comput. Geom. 20 (1998), 287305.

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), 238255.

J. Pach and M. Sharir,
On the boundary of the union of planar convex sets,
Discrete Comput. Geom. 21 (1999), 321328.

P. Agarwal, B. Aronov and M. Sharir,
Line transversals of balls and smallest enclosing cylinders
in three dimensions,
Discrete Comput. Geom. 21 (1999), 373388.

P. Agarwal, B. Aronov and M. Sharir,
Motion planning for a convex polygon in a polygonal environment,
Discrete Comput. Geom. 22 (1999), 201221.

G. Barequet and M. Sharir,
Partial surface matching by using directed footprints,
Comput. Geom. Theory Appls. 12 (1999), 4562.

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), 3140.
Also Discrete Comput. Geom. 39 (2008), 656677.

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,
335353.

P. Agarwal and M. Sharir,
DavenportSchinzel sequences and their geometric applications,
in Handbook of Computational Geometry,
J.R. Sack and J. Urrutia (Eds.),
NorthHolland, 2000, pp. 147.

P. Agarwal and M. Sharir,
Arrangements of surfaces in higher dimensions,
in Handbook of Computational Geometry,
J.R. Sack and J. Urrutia (Eds.),
NorthHolland, 2000, pp. 49119.

P. Agarwal, A. Efrat and M. Sharir,
Vertical decomposition of shallow levels in 3dimensional arrangements
and its applications,
SIAM J. Computing 29 (2000), 912953.

A. Efrat and M. Sharir,
The complexity of the union of fat objects in the plane,
Discrete Comput. Geom. 23 (2000), 171189.

P. Agarwal, B. Aronov, S. HarPeled and M. Sharir,
Approximation and exact algorithms for minimumwidth annuli and
shells.
Discrete Comput. Geom. 24 (2000), 687705.

P. Agarwal and M. Sharir,
Pipes, cigars, and kreplach: The union of Minkowski sums in three
dimensions.
Discrete Comput. Geom. 24 (2000), 645685.

S. Smorodinski, J. Mitchell and M. Sharir,
Geometric permutations of pairwise disjoint balls,
Discrete Comput. Geom., 23 (2000), 247259.

P.K. Agarwal, L. Guibas, S. HarPeled, A. Rabinovitch and M. Sharir,
Computing the penetration depth of two convex polytopes in three
dimensions,
Nordic Journal of Computing 7 (2000), 227240.

A. Efrat, M. Katz, F. Nielsen and M. Sharir,
Data structures for fat objects and their applications,
Comput. Geom. Theory Appls. 15 (2000), 215227.

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), 203220.

S. HarPeled and M. Sharir,
Online point location in planar arrangements and its applications,
Discrete Comput. Geom. 26 (2001), 1940.

M. Sharir, S. Smorodinsky and G. Tardos,
An improved bound for ksets in three dimensions,
Discrete Comput. Geom. 26 (2001), 195204.

J. Pach and M. Sharir,
Radial points in the plane,
European J. Combinatorics 22 (2001), 855863.

P. Agarwal, B. Aronov and M. Sharir,
Exact and approximation algorithms for minimumwidth cylindrical
shells,
Discrete Comput. Geom. 26 (2001), 307320.

N. Alon, H. Last, R. Pinchasi and M. Sharir,
On the complexity of arrangements of circles in the plane,
Discrete Comput. Geom. 26 (2001), 465492.

B. Aronov and M. Sharir,
Cutting circles into pseudosegments and improved bounds for incidences,
Discrete Comput. Geom. 28 (2002), 475490.

P. Agarwal and M. Sharir,
On the number of congruent simplices in a point set,
Discrete Comput. Geom. 28 (2002), 123150.

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), 4253.

D. Halperin, M. Sharir and K. Goldberg,
The 2center problem with obstacles,
J. Algorithms 42 (2002), 109134.

P.K. Agarwal, M. de Berg, S. HarPeled, M. Overmars, M. Sharir
and J. Vahrenhold,
Reporting intersecting pairs of polytopes in two and three dimensions,
Comput. Geom. Theory Appls., 23 (2002), 195207.

P. Agarwal, B. Aronov and M. Sharir,
On the complexity of many faces in arrangements of pseudosegments
and of circles,
Discrete and Computational Geometry  The GoodmanPollack
Festschrift,
B. Aronov, S. Basu, J. Pach and M. Sharir (Eds.),
SpringerVerlag, Heidelberg, 2003, pp. 123.
Also in
Proc. 42nd IEEE Symp. on Foundations of Computer Science (2001),
7483.

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
127139.

B. Aronov, J. Pach, M. Sharir and G. Tardos,
Distinct distances in higher dimensions,
Combinat. Probab. Comput. 13 (2004), 283293.

M. Sharir and E. Welzl,
Balanced lines, halving triangles, and the generalized lower bound theorem,
Discrete and Computational Geometry  The GoodmanPollack
Festschrift,
B. Aronov, S. Basu, J. Pach and M. Sharir (Eds.),
SpringerVerlag, Heidelberg, 2003, pp. 789798.
Also in
Proc. 17th ACM Symp. on Computational Geometry, June 2001,
pp. 315318.

J. Pach, I. Safruti and M. Sharir,
The union of congruent cubes in three dimensions,
Discrete Comput. Geom., 30 (2003), 133160.

V. Koltun and M. Sharir,
Threedimensional Euclidean Voronoi diagrams of lines
with a fixed number of orientations,
SIAM J. Comput., 32 (2003), 616642.

M. Sharir,
The ClarksonShor technique revisited and extended,
Combinat. Probab. Comput. 12 (2003), 191201.

P. Agarwal, S. HarPeled, M. Sharir and Y. Wang,
Hausdorff distance under translation for points, disks and balls,
Proc. 19th ACM Symp. on Computational Geometry (2003), 282291.
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), 179184.

M. Sharir and S. Smorodinsky,
Neighbors in geometric permutations,
Discrete Math. 268 (2003), 327335.

V. Koltun and M. Sharir,
The partition technique for the overlay of envelopes,
SIAM J. Comput. 32 (2003), 841863.

B. Aronov, S. Basu, J. Pach and M. Sharir (Editors),
Discrete and Computational GeometryThe GoodmanPollack
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), 139186.

A. Dumitrescu, J.S.B. Mitchell and M. Sharir,
Binary space partitions for axisparallel segments, rectangles,
and hyperrectangles,
Discrete Comput. Geom. 31 (2004), 207227.

S. Smorodinsky and M. Sharir,
Selecting points that are heavily covered by pseudocircles,
spheres, or boxes.
Combin. Probab. Comput. 13 (2004), 389411.

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), 6385.

S. Dekel, D. Leviatan and M. Sharir,
On bivariate smoothness spaces associated with nonlinear
approximation,
Constructive Approximation, 20 (2004), 625646.

V. Koltun and M. Sharir,
Polyhedral Voronoi diagrams of polyhedra in three dimensions,
Discrete Comput. Geom. 31 (2004), 83124.

M. Sharir and E. Welzl,
Pointline incidences in space,
Combinat. Probab. Comput. 13 (2004), 203220.

B. Aronov and M. Sharir,
Cell complexities in hyperplane arrangements,
Discrete Comput. Geom. 32 (2004), 107115.

J.S.B. Mitchell and M. Sharir,
New results on shortest paths in three dimensions,
Proc. 20th ACM Symp. on Computational Geometry (2004), 124133.

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),
310319.

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. 185223.

J. Pach, R. Pinchasi and M. Sharir,
On the number of directions determined by a threedimensional point
set,
J. Combinat. Theory, Ser. A 108 (2004), 116.

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), 179192.

P. Agarwal and M. Sharir,
Pseudoline arrangements: Duality, algorithms and applications,
SIAM J. Comput., 34 (2005), 526552.

B. Aronov, V. Koltun and M. Sharir,
Cutting triangular cycles of lines in space.
Discrete Comput. Geom., 33 (2005), 231247.

R. Pinchasi and M. Sharir,
On graphs that do not contain the cube and related problems,
Combinatorica 25 (2005), 615624.

B. Aronov, V. Koltun and M. Sharir,
Incidences between points and circles in three and higher dimensions,
Discrete Comput. Geom., 33 (2005), 185206.
Also in
Proc. 18th ACM Symp. on Computational Geometry (2002),
116122.

S. Feldman and M. Sharir,
An improved bound for joints in arrangements of lines in space,
Discrete Comput. Geom. 33 (2005), 307320.

R. Seidel and M. Sharir,
Topdown analysis of path compression,
SIAM J. Comput., 34 (2005), 515525.

J. Pach, R. Pinchasi, M. Sharir and G. T\'oth,
Topological graphs with no large grids,
Graphs and Combinatorics, 21 (2005), 355364.

V. Koltun and M. Sharir,
Curvesensitive cuttings,
SIAM J. Comput. 34 (2005), 863878.

M. Sharir and H. Shaul,
Ray shooting and stone throwing with nearlinear storage,
Comput. Geom. Theory Appl., 30 (2005), 239252.

P. Agarwal, B. Aronov, V. Koltun and M. Sharir,
On lines avoiding unit balls in three dimensions,
Discrete Comput. Geom., 34 (2005), 231250.

V. Kaibel, R. Mechtel, M. Sharir and G. Ziegler,
The simplex algorithm in dimension three,
SIAM J. Comput. 34 (2005), 475497.

E. Ezra and M. Sharir,
Counting and representing intersections among triangles in three dimensions,
Comput. Geom. Theory Appls. 32 (2005), 196215.

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), 310326.

E. Ezra and M. Sharir,
Output sensitive construction of the union of triangles,
SIAM J. Comput. 34 (2005), 13311351.

R. Apfelbaum and M. Sharir,
Repeated angles in three and four dimensions,
SIAM J. Discrete Math. 19 (2005), 294300.

J. Matou\v{s}ek, M. Sharir, S. Smorodinsky and U. Wagner,
On ksets in four dimensions,
Discrete Comput. Geom. 35 (2006), 177191.

H. Kaplan and M. Sharir,
Randomized incremental construction of threedimensional convex hulls
and planar Voronoi diagrams, and approximate range counting,
Proc. 17th ACMSIAM Symp. on Discrete Algorithms (2006), 484493.

E. Welzl and M. Sharir,
On the number of crossingfree matchings, cycles and partitions,
SIAM J. Comput., 36 (2006), 695720.

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), 385419.

E. Oks and M. Sharir,
Minkowski sums of monotone and general simple polygons,
Discrete Comput. Geom. 35 (2006), 223240.

B. Aronov, A. Efrat, V. Koltun and M. Sharir,
On the union of kappacurved objects in three and four dimensions,
Discrete Comput. Geom., 36 (2006), 511526.

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), 815834.

P.K. Agarwal, S. Cabello, J.A. Sellar\`es and M. Sharir,
Computing a centertransversal line,
Proc. FSTTCS (2006),
Lecture Notes Comput. Sci., Vol 4337, Springer Verlag, 2006, 93104.

M. Sharir and E. Welzl,
Random triangulations of planar point sets,
Proc. 22nd ACM Symp. on Computational Geometry (2006), 273281.

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 conflictfree coloring for intervals,
SIAM J. Comput., 36 (2006), 13421359.

H. Kaplan, M. Sharir and E. Verbin,
Colored intersection searching via sparse rectangular matrix
multiplication,
Proc. 22nd ACM Symp. on Computational Geometry (2006), 5260.

G. Alexandron, H. Kaplan and M. Sharir,
Kinetic and dynamic data structures for convex hulls and upper
envelopes,
Comput. Geom. Theory Appls., 36 (2006), 144158.

D. Feldman, A. Fiat and M. Sharir,
Coresets for weighted facilities and their applications,
Proc. 47rd IEEE Symp. on Foundations of Computer Science (2006),
315324.

J. Pach, R. Pinchasi and M. Sharir,
Solution of Scott's problem on the number of directions determined by a
point set in 3space,
Discrete Comput. Geom., 38 (2007), 399441.

E. Ezra and M. Sharir,
A single cell in an arrangement of convex polyhedra in R^3,
Discrete Comput. Geom., 37 (2007), 2141.

R. Apfelbaum and M. Sharir,
Large bipartite graphs in incidence graphs of points and hyperplanes,
SIAM J. Discrete Math. 21 (2007), 707725.

B. Aronov, S. HarPeled and M. Sharir,
On approximate halfspace range counting and relative epsilon approximations.
Proc. 23rd ACM Symp. on Computational Geometry (2007), 327336.

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), 294301.

P.K. Agarwal, R. Apfelbaum, G. Purdy and M. Sharir,
Similar simplices in a ddimensional point set,
Proc. 23rd ACM Symp. on Computational Geometry (2007), 232238.

D. Feldman, A. Fiat, M. Sharir and D. Segev,
Constantfactor bicriteria lineartime approximations for generalized
kmean/median/center,
Proc. 23rd ACM Symp. on Computational Geometry (2007), 1926.

Y. Schreiber and M. Sharir,
An optimal algorithm for shortest paths on a convex polytope in
three dimensions,
Discrete Comput. Geom., 39 (2008), 500579.

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
3dimensional paths, trees, and cycles,
Discrete Comput. Geom., 39 (2008), 1737.

E. Ezra, M. Sharir and A. Efrat,
On the ICP algorithm,
Comput. Geom. Theory Appls., 41 (2008), 7793.

H. Kaplan, N. Rubin, M. Sharir and E. Verbin,
Efficient colored orthogonal range counting,
SIAM J. Comput. 38 (2008), 9821011.

J. Pach and M. Sharir,
On planar intersection graphs with forbidden subgraphs,
J. Graph Theory 59 (2008), 205214.

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. 948.

N. Alon, H. Kaplan, G. Nivasch, M. Sharir and S. Smorodinsky,
Weak epsilonnets 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), 6978.

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), 5263.

V. Koltun and M. Sharir,
A note on overlays of minimization diagrams,
Discrete Comput. Geom. 41 (2009), 385397.

K. Chen, H. Kaplan and M. Sharir,
Online conflictfree coloring for halfplanes, congruent disks, and
axisparallel 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, AugustSeptember, 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), 216231.

H. Kaplan, N. Rubin and M. Sharir,
Linear data structures for fast ray shooting amid convex polytopes,
Algorithmica 55 (2009), 283310.

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), 494497.

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), 11771198.

M. Sharir,
On distinct distances and incidences: Elekes's transformation and
the new algebraic developments,
Annales Univ. Sci. Budapest. 52 (2009), 75102.

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), 127136.
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), 352390.

H. Kaplan, N. Rubin and M. Sharir,
Line transversals of convex polyhedra in R^3,
SIAM J. Comput. 39 (2010), 32833310.

B. Aronov and M. Sharir,
Approximate halfspace range counting,
SIAM J. Comput. 39 (2010), 27042725.

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,
Smallsize epsilon nets for axisparallel rectangles and boxes,
SIAM J. Comput. 39 (2010), 32483282.

R. Apfelbaum and M. Sharir,
An improved bound on the number of unitarea triangles,
Discrete Comput. Geom. 44 (2010), 753761.

H. Kaplan, M. Sharir, and E. Shustin,
On lines and joints,
Discrete Comput. Geom. 44 (2010), 838843.
Also in arXiv:0906.0558.

D. Halperin, O. Setter and M. Sharir,
Constructing twodimensional Voronoi diagrams
via divideandconquer of envelopes in space,
Transactions on Computational Science 9 (2010), 127.
Also in Proc. 6th Annu. Internat. Sympos. Voronoi Diagrams in Science and
Engineering (ISVD) (2009), 4352.

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), 333.
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), 371382.
Published online January 6, 2011.

M. Sharir and H. Shaul,
Semialgebraic range reporting and emptiness searching with applications,
SIAM J. Comput., 40 (2011), 10451074.

Gy. Elekes, H. Kaplan and M. Sharir,
On lines, joints, and incidences in three dimensions,
J. Combinat. Theory, Ser. A 118 (2011), 962977.
published online Nov. 17, 2010.
Also in arXiv:0905.1583.

M. Sharir,
An improved bound for ksets in four dimensions,
Combinat. Probab. Comput. 20 (2011), 119129.

M. Sharir and A. Sheffer,
Counting triangulations of planar point sets,
Electronic J. Combinat. 18 (2011), P70.
Also in arXiv:0911.3352.

S. HarPeled and M. Sharir,
Relative (p,epsilon)approximations in geometry,
Discrete Comput. Geom. 45 (2011), 462496.
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), 191205.
Published online Nov. 5, 2010.

M. Sharir, A. Sheffer and E. Welzl,
On degrees in random triangulations,
J. Combinat. Theory, Ser. A, 118 (2011), 19791999.

Gy. Elekes and M. Sharir,
Incidences in three dimensions and distinct distances in the plane,
Combinat. Probab. Comput., 20 (2011), 571608.
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), 16471661.
Also in Proc. European Symposium on Algorithms (2010), 475486.

R. Apfelbaum and M. Sharir,
Nondegenerate spheres in three dimensions,
Combinat. Probab. Comput., 20 (2011), 503512.
Published online January 28, 2011.

E. Ezra, B. Aronov, and M. Sharir,
Improved bound for the union of fat triangles,
Proc. 22nd ACMSIAM Symp. on Discrete Algorithms (2011),
17781785.

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), 367390.
Also in arXiv:1007.3244.
Also in Proc. 51st IEEE Symp. on Foundations of Computer Science (2010), 355364.

H. Kaplan, J. Matou\v{s}ek, M. Sharir, and Z. Safernov\'a,
Unit distances in three dimensions,
Combinat. Probab. Comput. 21 (2012), 597610.
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
GuthKatz polynomial partitioning technique,
Discrete Comput. Geom. 48 (2012), 499517.
Also in arXiv:1102.5391.

P. K. Agarwal, E. Ezra and M. Sharir,
Nearlinear approximation algorithms for geometric hitting sets,
Algorithmica 63 (2012), 125.
Also in Proc. 25th ACM Sympos. Comput. Geom., 2009, 2332.

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. 303326.
Also in arXiv:1012.0591.
See also Proc. 12th Workshop on Algorithms and Data Structures (2011), 524535.

P. K. Agarwal, R. BenAvraham and M. Sharir,
The 2center problem in three dimensions,
Comput. Geom. Theory Appl. 46 (2013), 734746.
Also in Proc. 26th ACM Symp. on Computational Geometry (2010), 8796.
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), 335355.
Also in Proc. 28th ACM Symp. on Computational Geometry (2012),
287292.

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), 777794.
Also, Proc. 28th ACM Symp. on Computational Geometry (2012), 189198.
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), 20392062.
Also in Proc. 53rd IEEE Symp. on Foundations of Computer Science (2012),
420429.
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: Crossgraph charging schemes,
Combinat. Probab. Comput. 22 (2013), 935954.
Also in Proc. Symp. on Graph Drawing (2012), 1930.
Also in arXiv:1209.0194.

A. Sheffer, M. Sharir, and J. Solymosi,
Distinct distances on two lines,
J. Combinat. Theory Ser. A 20 (2013), 17321736.
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), 429449.
Also in Proc. 24th ACMSIAM Symp. on Discrete Algorithms (2013),
156167.
Also in arXiv:1204.5333.

D. Aiger, H. Kaplan and M. Sharir,
Reporting neighbors in highdimensional Euclidean spaces,
SIAM J. Comput. 43 (2014), 13631395.
Also in Proc. 24th ACMSIAM Symp. on Discrete Algorithms (2013),
784803.

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), 543572.

P. K. Agarwal, S. HarPeled, H. Kaplan and M. Sharir,
Union of random Minkowski sums and network vulnerability analysis,
Discrete Comput. Geom. 52 (2014), 551582.
Also in Proc. 29th ACM Symp. on Computational Geometry (2013), 177186.
Also in arXiv:1310.5647.

J. Cilleruelo, A. Sheffer, and M. Sharir,
On lattices, distinct distances, and the ElekesSharir framework,
Discrete Math. 336 (2014), 3740.
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), 490520.
Also in Proc. 29th ACM Symp. on Computational Geometry (2013), 97106.
Also in arXiv:1208.0053.

O. E. Raz, O. RocheNewton and M. Sharir,
Sets with few distinct distances do not have heavy lines,
Discrete Math. 338 (2015), 14841492.
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), 318.
Also in Proc. 30th ACM Symp. on Computational Geometry (2014), 206213.
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 ACMSIAM Symp. on Discrete Algorithms (2012), 338355.

M. Sharir and J. Solymosi,
Distinct distances from three points,
Combinat. Probab. Comput. 25 (2016), 623632.
Also in arXiv:1308.0814.

M. Sharir and S. Zaban,
Outputsensitive tools for range searching in higher dimensions,

O. E. Raz, M. Sharir and J. Solymosi,
Polynomials vanishing on grids: The ElekesR\'onyai problem revisited,
Amer. J. Math. 138 (2016), 10291065.
Also in Proc. 30th ACM Symp. on Computational Geometry (2014), 251260.
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), 198205.
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), 377386.

M. Sharir and N. Solomon,
Incidences between points and lines in four dimensions,
Proc. 30th ACM Symp. on Computational Geometry (2014), 189197.

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), 871904.
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), 905929.
New version in arXiv:1504.06851.

R. Ben Avraham, M. Henze, R. Jaume, B. Keszegh, O. E. Raz, M. Sharir, and I. Tubis,
The minimum Hausdorff and partial matching RMSdistance under translation: Combinatorics and algorithms,
Algorithmica, 80 (2018), 24002421.
Also in Proc. European Sympos. Algorithms, (2014), 100111.
Also in arXiv:1411.7273.

S. HarPeled, H. Kaplan, M. Sharir, and S. Smorodinsky,
Epsilonnets 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), 702756.
Also in Proc. 56th IEEE Symp. Foundations of Computer Science, (2015), 13781394.
Also in arXiv:1411.0777.

O. E. Raz and M. Sharir,
Unitarea triangles in the plane: Theme and variation,
Combinatorica 37 (2017), 12211240.
Also in Proc. 31st Symp. on Computational Geometry (2015), 569583.
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. FejesT\'oth, J. Pach, Eds.),
Bolyai Soc. Math. Studies (BSMS, Vol. 27), Springer, 2018, pages 359383.
Also in arXiv:1501.02544.
Also in Proc. 31st Symp. on Computational Geometry (2015), 553568.

O. E. Raz, M. Sharir and F. de Zeeuw,
Polynomials vanishing on Cartesian products: The ElekesSzab\'o theorem revisited,
Duke Math. J. 165(18) (2016), 35173566.
Also in Proc. 31st Symp. on Computational Geometry (2015), 522536.
Also in arXiv:1504.05012

M. Sharir and N. Solomon,
Incidences between points and lines on a twodimensional 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 unitarea triangles spanned by convex grids in the plane,
Comput. Geom. Theory Appls. 62 (2017), 2533.
Also in arXiv:1504.06989.

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), 977988.
Also in arXiv:1512.08267.

S. Kalia, M. Sharir, N. Solomon, and B. Yang,
Generalizations of the Szemer\'ediTrotter theorem,
Discrete Comput. Geom., 55 (2016), 571593.
Also in arXiv:1408.5915v2.

M. Sharir, S. Smorodinsky, C. Valculescu, and F. de Zeeuw,
Distinct distances between points and lines,
Comput. Geom. Theory Appls., 69 (2018), 215.
Also in arXiv:1512.09006.

S. HarPeled, H. Kaplan, and M. Sharir,
Approximating the klevel in threedimensional 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, BerlinHeidelberg, 2017, pp.~467504.
Also in Proc. 27th ACMSIAM Sympos. Discrete Algorithms, (2016), 11931212.
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:142:13.
Also in arXiv:1512.05279v2.

M. Sharir and J. Zahl,
Cutting algebraic curves into pseudosegments and applications,
J. Combinat. Theory Ser. A 150 (2017), 135.
Also in arXiv:1604.07877.

D. Halperin and M. Sharir,
Arrangements,
Chapter 30, 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, 2017, in press.

D. Halperin, O. Salzman and M. Sharir,
Algorithmic motion planning,
Chapter 51, 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, 2017, in press.

O. Gold and M. Sharir,
Dominance products and faster algorithms for highdimensional closest pair under $L_\infty$,
Proc. 28th Internat. Sympos. Algorithms and Computation, (2017), 39:139:12.
Also in arXiv:1605.08107.

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:125:14.
Also in arXiv:1607.05994.

B. Aronov, E. Miller and M. Sharir,
Eliminating depth cycles among triangles in three dimensions,
Proc. 28th ACMSIAM Symp. on Discrete Algorithms (2017), 24762494.
Also in arXiv:1607.06136.

M. Sharir and N. Solomon,
Incidences between points and lines on two and threedimensional varieties,
Discrete Comput. Geom., 59 (2018), 88130.
Also in arXiv:1609.09026.

M. Sharir and N. Solomon,
Incidences between points and surfaces and points and curves, and distinct and repeated distances in three dimensions,
Proc. 28th ACMSIAM Symp. on Discrete Algorithms (2017), 24562475.
Also in arXiv:1610.01560.

H. Kaplan, W. Mulzer, L. Roditty, P. Seiferth, and M. Sharir,
Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications,
Proc. 28th ACMSIAM Symp. on Discrete Algorithms (2017), 24952504.
Also in arXiv:1604.03654.

O. E. Raz, M. Sharir, and F. de Zeeuw,
The ElekesSzab\'o theorem in four dimensions,
Israel J. Math. 227 (2018) 663690.
Also in arXiv:1607.03600.

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), 735755.
A preliminary version in Proc. 33rd Symp. on Computational Geometry (2017), 41:141:15.
Also in arXiv:1607.04336.

A. Bruner and M. Sharir,
Distinct distances between a collinear set and an arbitrary set of points,
Discrete Math., 341 (2018), 261265.
Also in arXiv:1612.04940.

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,
Proc. 29th ACMSIAM Sympos. on Discrete Algorithms (2018), 495514.
Also in arXiv:1704.02793.

H. Kaplan, R. Sasanka, and M. Sharir,
Finding axisparallel rectangles of fixed perimeter or area containing the largest number of points,
Comput. Geom. Theory Appls. 81 (2019), 111.
Also in Proc. 25th European Sympos. Algorithms, (2017), 52:152:13.

D. Aiger, H. Kaplan, and M. Sharir,
Output sensitive algorithms for approximate incidences and their applications,
Comput. Geom. Theory Appls., accepted.
Also in Proc. 25th European Sympos. Algorithms, (2017), 5:15:13.

P. K. Agarwal, N. Rubin, and M. Sharir,
Approximate nearest neighbor search amid higherdimensional flats,
Proc. 25th European Sympos. Algorithms, (2017), 4:14:13.

D. Aiger and M. Sharir,
Homotheties and incidences.
Discrete Math., 341 (2018), 20112017.
Also in arXiv:1709.02933.

E. Ezra, S. HarPeled, H. Kaplan and M. Sharir,
Decomposing arrangements of hyperplanes: VCdimension, combinatorial dimension, and point location.
Discrete Comput. Geom., accepted.
Also in arXiv:1712.02913.

S. HarPeled, H. Kaplan, W. Mulzer, L. Roditty, P. Seiferth, M. Sharir, and M. Willert,
Stabbing pairwise intersecting disks by five points,
Proc. 29th Internat. Sympos. Algorithms and Computation (2018), 50:150:12.
Also in Proc. 18th EuroCG (2018), 29:129:6.
Also in arXiv:1801.03158.

B. Aronov and M. Sharir,
Almost tight bounds for eliminating depth cycles in three dimensions,
Discrete Comput. Geom., 59 (2018), 725741.
Also in Proc. 48th ACM Sympos. Theory of Computing, (2016), 18.
Also in arXiv:1512.00358.

P. K. Agarwal, H. Kaplan and M. Sharir,
Union of hypercubes and 3d Minkowski sums with random sizes,
Proc. 45th Int. Colloq. Automata, Languages, Programming (2018), 10:110:15.

P. K. Agarwal, H. Kaplan, G. Kipper, W. Mulzer, G. Rote, M. Sharir, and A. Xiao,
Approximate minimumweight matching with outliers under translation,
Proc. 29th Internat. Sympos. Algorithms and Computation (2018), 26:126:13.
Also in arXiv:1810.10466.

M. Sharir and C. Ziv,
On levels in arrangements of pseudoplanes in three dimensions,
Proc. 35th Sympos. Comput. Geom. (2019), 62:162: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:18: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), to appear.
Also in arXiv:1907.01980.
Last update: September 16, 2018