Micha Sharir


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.

Links

For further information on Micha Sharir, see:

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

Eric's Home Page