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
Courses:
Computational Geometry
Advanced Topics in Computational Geometry
Algorithms
Geometric Optimization
B.Sc. Seminar on Computational Geometry
Research Seminar on Computational Geometry
Recent Papers:
(Some links do not point to a file; please contact me by email if you
need a copy.)

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

P.K. Agarwal, O. Schwarzkopf and M. Sharir,
The overlay of lower envelopes in 3space and its applications,
Discrete Comput. Geom. 15 (1996), 113.

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

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

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.

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.

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

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.

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.

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.

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

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.

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.

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

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.

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

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

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

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.

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

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.

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.

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.

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

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

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,
Quasiplanar graphs have a linear number of edges,
Combinatorica 17 (1997), 19.

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

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.

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

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.

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

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

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

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.

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.

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

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

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.

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

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.

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

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.

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

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.

G. Pustylnik and M. Sharir,
The Minkowski sum of a simple polygon and a segment,
Information Processing Letters 85 (2003), 179184.

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.

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.

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

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.

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

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.

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.

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.

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.

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.

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

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.

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

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

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.

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.

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

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. 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. Oks and M. Sharir,
Minkowski sums of monotone and general simple polygons,
Discrete Comput. Geom. 35 (2006), 223240.

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.

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, 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 3space,
Discrete Comput. Geom., 38 (2007), 399441.

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.

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.

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.

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 and M. Sharir,
A single cell in an arrangement of convex polyhedra in R^3,
Discrete Comput. Geom., 37 (2007), 2141.

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.

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

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

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

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

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

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.

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

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

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.

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

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

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.

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

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.

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.

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.

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.

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,
Discrete Comput. Geom., submitted.

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.

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

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.

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.

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.

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, M. Katz, G. Morgenstern and M. Sharir,
Optimal cover of points by disks in a simple polygon,
Proc. European Symposium on Algorithms (2010), 475486.
Also in SIAM J. Comput. 40 (2011), 16471661.

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.

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.

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

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.

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 ACMSIAM Symp. on Discrete Algorithms (2012),
338355.

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. 23 (2013), 335355.
Also in Proc. 28th ACM Symp. on Computational Geometry (2012),
287292.

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.

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.

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.

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.

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. Dulieu, R. Pinchasi, and M. Sharir,
On the union complexity of diametral disks,
Electronic J. Combinat. 20(2) (2013), P53.

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.

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.

A. Sheffer, M. Sharir, and J. Zahl,
Improved bounds for incidences between points and circles,
Combinat. Probab. Comput., in press.
Published online Oct. 2, 2014.
Also in Proc. 29th ACM Symp. on Computational Geometry (2013), 97106.
Also in arXiv:1208.0053.

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.

M. Sharir and J. Solymosi,
Distinct distances from three points,
Combinat. Probab. Comput. , accepted.
Also in arXiv:1308.0814.

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.

M. Sharir and S. Zaban,
Outputsensitive tools for range searching in higher dimensions,
Comput. Geom. Theory Appls. , submitted.

O. Raz, M. Sharir and J. Solymosi,
Polynomials vanishing on grids: The ElekesR\'onyai problem revisited,
Proc. 30th ACM Symp. on Computational Geometry (2014), 251260.
Also Amer. J. Math., accepted.
Also in arXiv:1401.7419.

O. Raz, M. Sharir and J. Solymosi,
On triple intersections of three families of unit circles,
Proc. 30th ACM Symp. on Computational Geometry (2014), 198205.
Also Discrete Comput. Geom., submitted.
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,
Proc. 30th ACM Symp. on Computational Geometry (2014), 377386.
Also ACM Trans. Algorithms, accepted.

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

P. K. Agarwal, J. Gao. L. Guibas, H. Kaplan, N. Rubin and M. Sharir,
Stable Delaunay graphs,
Discrete Comput. Geom., submitted.

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

O. E. Raz, O. RocheNewton and M. Sharir,
Sets with few distinct distances do not have heavy lines,
In arXiv:1410.1654.

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$,
in arXiv:1411.0777.
Last update: December 18, 2014