- Education
- BS Tel Aviv University 1970
- MS Tel Aviv University 1972
- PhD Tel Aviv University 1976 Advisor: Aldo Lazar
- Current Positions
- Professor -- Tel Aviv University
- Computer Science
- 972-3-6408804 (voice)
- 972-3-6409357 (fax)
- sharir@math.tau.ac.il
- Computational Geometry
- Advanced Topics in Computational Geometry
- Computation
- Research Professor -- New York University
- Courant Institue of Mathematical Sciences
- Department of Computer Science
- 212-998-3376
- sharir@cs.nyu.edu
- Current Interests:
- Computational Geometry
- Combinatorical Geometry
- Motion Planning Algorithms
- Robotics
- Honors
- The Celia and Marcos Maus Annual Prizes in
Computer Science at the school of Mathematical
Sciences -- 1990 - Gave keynote address
- Some recent papers:
- M. Sharir and P.K. Agarwal, Davenport-Schinzel
Sequences and Their Geometric Applications, Cambridge
University Press, Cambridge-New York-Melbourne, 1995.
- P.K. Agarwal, O. Schwarzkopf and M. Sharir, The
overlay of lower envelopes in 3-space and its applications,
Discrete Comput. Geom. 15 (1996), 1--13.
- M. Sharir, A near-linear algorithm for the planar
2-center problem, Discrete Comput. Geom. 15 (1996)
(in press).
- 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, Davenport-Schinzel
sequences and their geometric applications, Chapter in
Handbook of Computational Geometry, J.R. Sack (Ed.),
North-Holland, submitted for publication.
- B. Aronov and M. Sharir, On translational motion
planning of a convex polyhedron in 3-space, To appear
in SIAM J. Computing.
- L.P. Chew, K. Kedem, M. Sharir, B. Tagansky and
E. Welzl, Voronoi diagrams of lines in three dimensions
under polyhedral convex distance functions, To appear
in J. Algorithms
- B. Aronov and M. Sharir, The common exterior of
convex polygons in the plane, To appear in Computational
Geometry, Theory and Appls.
- P.K. Agarwal, B. Aronov and M. Sharir, Computing
lower envelopes in four dimensions with applications,
To appear in SIAM J. Computing.
- M. Katz and M. Sharir, An expander-based approach
to geometric optimization, To appear in SIAM J. Computing.
- S. Mohaban and M. Sharir, Ray shooting amidst
spheres in 3 dimensions and related problems, To appear
in SIAM J. Computing.
- A. Efrat and M. Sharir, A near-linear algorithm for
the planar segment center problem, To appear in Discrete
Comput. Geom.
- J. Matousek, M. Sharir and E. Welzl, A subexponential
bound for linear programming and related problems, To
appear in Algorithmica.
- P.K. Agarwal and M. Sharir, Efficient randomized
algorithms for some geometric optimization problems,
To appear in Discrete Comput. Geom.
- D. Halperin and M. Sharir, A near-quadratic algorithm
for planning the motion of a polygon in a polygonal environment,
To appear in Discrete Comput. Geom.
- B. Aronov, M. Sharir and B. Tagansky, The union of
convex polyhedra in three dimensions, To appear in
SIAM J. Computing.
- M. Sharir, Excess in arrangements of segments,
Submitted to Information Processing Letters.
- P. Agarwal, N. Amenta and M. Sharir, Largest
placement of one convex polygon inside another,
Submitted to Discrete Comput. Geom.
- P. Agarwal, A. Efrat and M. Sharir, Vertical
decomposition of shallow levels in 3-dimensional
arrangements and its applications, Submitted to SIAM
J. Computing.
- G. Barequet and M. Sharir, Partial surface and
volume matching in three dimensions, Submitted to
IEEE Trans. on Pattern Recognition and Machine
Intelligence.
- J.D. Boissonnat, M. Sharir, B. Tagansky and
M. Yvinec, Voronoi diagrams in higher dimensions
under certain polyhedral distance functions, Submitted
to Discrete Comput. Geom.
- K. Kedem, M. Sharir and S. Toledo, On critical
orientations in the Kedem-Sharir motion planning
algorithm, Submitted to Discrete Comput. Geom.
- 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, Proc. Symp. on Graph Drawing, GD' 95
(Franz J. Brandenburg, ed.), Lecture Notes in Computer
Science 1027, Springer-Verlag, Berlin, 1996, pp. 1--7.
- 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
and its applications, Proc. 12th ACM Symp. on Computational
Geometry (1996), to appear.
- M. Sharir and E. Welzl, Rectilinear and polygonal
p-piercing and p-center problems, Proc. 12th ACM Symp.
on Computational Geometry (1996), to appear.
- S. Har-Peled, M. Sharir and K. Varadarajan,
Approximate shortest paths on a convex polytope in three
dimensions, Proc. 12th ACM Symp. on Computational
Geometry (1996), to appear.
- G. Barequet and M. Sharir, Partial surface matching by using directed footprints, Proc. 12th ACM Symp. on Computational Geometry (1996), to appear.

- Micha Sharir's Home Page
at Tel Aviv University
#### Additional Related Information:

- Learn about Jacob T Schwartz
- Some notes on
**Planning, Geometry, and Complexity of Robot Motion**

-- Edited by Jacob T. Schwartz, Micha Sharir, John Hopcroft

*Report by Eric Johnson, CPSC 643, Fall 1996*