Curriculum Vitae Alon Efrat

Curriculum Vitae


Alon Efrat


Areas of Scientific Interest
I am interested in Computational Geometry, and in applications of geometric algorithms to real life problems. More specifically, I show interest in the following topic;

Personal

Place and date of birth: Haifa, Israel 1965
Marital status: Single
Citizenship: Israel

Address:
Computer Science Department
Gates 375, 353 Serra Mall
Stanford University, Stanford, CA 94305
alon@cs.stanford.edu
Office phone: 650-7236838; Home phones: 650-3298589
Fax: 650-723-0033


Current position

Post-Doctorate
Computer Science Department
Stanford University
Supervisor: Prof. Leonidas J. Guibas.

List of Publications

A. Papers in Journals

1.
"Computing a segment-center for a planar point set", with P. K. Agarwal, M. Sharir and S. Toledo, J. Algorithms 15 (1993), 314-323.
2.
"On the union of fat wedges and separating a collection" of segments by a line, with M. Sharir and G. Rote. Computational Geometry: Theory and Applications 3 (1994), 277-288.
3.
"Subpixel image registration using circular fiducials", with C. Gotsman, International J. of Computational Geometry and Applications 4 (1994), 403-422.
4.
"Computing the smallest k-enclosing circle and related problems", with M. Sharir and A. Ziv, Computational Geometry: Theory and Applications 4 (1995), 119-136.
5.
"A near-linear algorithm for the planar segment center problem" with M. Sharir, Discrete and Computational Geometry 16 (1996), 239-257.
6.
"Separating and shattering long line segments" with O. Schwarzkopf, Information Processing Letters 64 (1998), 309-314.
7.
"Vertical decomposition of shallow levels in 3-dimensional arrangements and its applications", with P. K. Agarwal and M. Sharir, SIAM J. Computing. To appear.
8.
"Geometric pattern matching in d-dimensional space" with L.P. Chew, D. Dor and K. Kedem, Discrete and Computational Geometry. To appear
9.
Geometry helps in bottleneck matching and related problems" with M. Katz and A. Itai,, Algorithmica, to appear.
10.
"On the complexity of the union of fat objects in the plane" with M. Sharir, Discrete and Computational Geometry. To appear.
11.
"Efficient Algorithms and Regular Data Structures for Dilation, Location and Proximity Problems", with A. Amir, P. Indyk and H. Samet, Algorithmica. To appear.
12.
"On the Union of $\alpha$-Curved Objects" with M. Katz, Computational Geometry: Theory and Applications. To appear.
13.
" A subquadratic bound on the number of regular vertices of the union of Jordan regions", with B. Aronov, D. Halperin and M. Sharir, Discrete and Computational Geometry. To appear.
14.
"Dynamic data structures for fat objects and their applications" with M. J. Katz, F. Nielsen and M. Sharir, Computational Geometry: Theory and Applications. To appear.
15.
"Computing an Euclidean Bottleneck Matching in Higher dimension" with M. Katz, to appear in Information Processing Letters.
16.
"Fly Cheaply: On the Minimum Fuel-Consumption Problem" , with Timothy M. Chan and S. Har-Peled, to appear in J. Algorithm.




B. Papers in Proceedings of Conferences

1.
"A simple algorithm for maintaining the center of a planar point-set" with R. Bar-Yehuda and A. Itai, in Proc. 5th Canad. Conf. Comput. Geom. 1993, 252-257.
2.
"Finding maximally consistent sets of halfspaces", with M. Lindenbaum and M. Sharir, in Proc. 5th Canad. Conf. Comput. Geom., 1993, 432-436.
3.
"On the union of fat wedges and separating a collection of segments by a line", with M. Sharir and G. Rote, in Proc. 5th Canad. Conf. Comput. Geom., 1993, 115-120.
4.
"Computing the smallest k-enclosing circle and related problems" with M. Sharir and A. Ziv, Proc. Third Workshop Algorithms Data Structes Lecture Notes in Computer Science 1993, vol. 709, Springer-Verlag, New York-Berlin-Heidelberg, 325-336.
5.
"A near-linear algorithm for the planar segment center problem", with M. Sharir, in Proc. 5th ACM-SIAM Sympos. Discrete Algorithms, 1994, 87-97.
6.
"Vertical decomposition of shallow levels in 3-dimensional arrangements and its applications", with P.K. Agarwal and M. Sharir, in Proc. 11th Annual Symposium on Computational Geometry, 1995, 39-50.
7.
"Geometric pattern matching in d-dimensional space", with L.P. Chew, D. Dor and K. Kedem, Third European Symposium on Algorithms (ESA), Lecture Notes in Computer Science 1995, vol. 979 (P. Spirakis ed.) Springer-Verlag, New York-Berlin-Heidelberg, 264-279.
8.
"Improvements on bottleneck matching and related problems, using geometry", with A. Itai, in Proc. 12th Annual Symposium on Computational Geometry, 1996, 301-310.
9.
"Computing most-uniform and minimum deviation matchings in geometric settings" with M.J. Katz, in Proc. 7th Annual International Symposium on Algorithms and Computational (ISAAC), 1996, 115-125.
10.
"Separating and shattering long line segments", with O. Schwarzkopf, Proc. 7th Annual International Symposium on Algorithms and Computational (ISAAC), 1996, 36-44.
11.
"On the complexity of the union of fat objects in the plane", with M. Sharir, in Proc. 13th Annual Symposium on Computational Geometry, 1997, 104-112.
12.
"Dynamic data structures for fat objects and their applications", with M.J. Katz, F. Nielsen and M. Sharir, in Proc. 5th Workshop on Algorithms and Data Structures (WADS'97), 297-396.
13.
On the Union of $\alpha$-Curved Objects, with M. Katz, in Proc. 14th Annual Symposium on Computational Geometry, 1998, 206-213.
14.
Fly Cheaply: On the Minimum Fuel-Consumption Problem, with S. Har-Peled, in Proc. 14th Annual Symposium on Computational Geometry, 1998, 143-145.
15.
"A subquadratic bound on the number of regular vertices of the union of Jordan regions", with B. Aronov, D. Halperin and M. Sharir, in Proc. 6th Scand. Workshop on Algorithms Theory, 1998, 322-334.
16.
"The Complexity of the Union of $(\alpha,\beta)$-Covered Objects", Proc. 15th Annual Symposium on Computational Geometry, 1999, 134-142.
17.
"Efficient Algorithms and Regular Data Structures for Dilation, Location and Proximity Problems". with A. Amir, P. Indyk and H. Samet, in Proceedings 40 Annual IEEE Symposium on Foundations of Computer Science, 1999. To appear.
18.
"Planning Robot Motion Strategies for Efficient Model Construction", with H Gonzalez-Banos, E. Mao, J.C. Latombe and T. M. Murali, in Proc. 9th International Symposium of Robotics Research, 1999. To appear.

19.
"On Incremental Rendering of Silhouette Maps of a Polyhedral Scene" with L. Zhang, L.J. Guibas and O.A. Hall-Holt, in Proc. 11th Annual ACM-SIAM Symposium on Discrete Algorithms, 2000. To appear.
20.
"Sweeping Simple Polygons with a Chain of Guards" with L.J. Guibas, S. Har-Peled, D.C. Lin, J.S.B. Mitchell and T.M. Murali, in Proc. 11th Annual ACM-SIAM Symposium on Discrete Algorithms, 2000. To appear.

C. Manuscripts

1.
"On Ants Crickets and Frogs in circular pursuit."
With N. Cohen and F. Bruckstein. Report. CIS-9309. Faculty of Computer Science, Technion - IIT.

2.
"Finding approximate matching of points and segments under translation", manuscript 1995.

D. In Preparations

1.
"Pattern Matching for Sets of Segments" with P. Indyk and S. Venkatasubramanian.
2.
"Covering Simple Polygonal Regions by Ellipses" with F. Hoffmann, K. Kriegel and C. Schultz.

Education

1998 Ph.D. in Computer Science, Tel-Aviv University.  
  Subject of thesis: Optimal Geometric Location Problems  
  Advisor: Prof. Micha Sharir  
     
1993 M.Sc. in Computer Science, The Technion, Israel.  
  Subject of thesis: Maintaining the Smallest Enclosing Circle  
  Advisors: Prof. Alon Itai and Prof. Reuven Bar-Yehuda  
     
1991 B.Sc. in Applied Mathematics, Mathematics Department, The Technion, Israel.  
     


Awards and Grants

1998 Awarded the Rothschild fellowship (Israel).
   
1998 Minerva fellowship (Israel-Germany).
   
1998 Chateaubriand fellowship (France).
   
1998 Pacific Institute for the Mathematical Sciences (Canada) (Canada).
   
1996 prize and grant for distinguished graduate students, Tel-Aviv University (Israel).
   



Services to the community

Refereed reports for
journals:
Discrete and Computational Geometry, Combinatorica, Information Processing Letters, Computational Geometry: Theory and Applications, International Journal of Computational Geometry and Applications, Journal of Algorithms.

Conferences:
Annual ACM-SIAM Symposium on Discrete Algorithms, IEEE Symposium on Foundations of Computer Science, ACM Annual Symposium on Computational Geometry.

Maintain a web page of pointers to full versions of papers that appeared in the ACM Annual Symposium on Computational Geometry. Also maintain pointers to java demos of algorithms in Computational Geometry, Data Structures and Graph Algorithms. The motivation is to give students in my courses, as well as other, an efficient tool to visualize over the web, common algorithms in these area.



Employment

95-98

 Worked as a lecturer and TA in different institutes.  
  (see list under "Teaching experience").  

86-87

 Worked as a designer and programmer at Yaam -- (a software company in Israel).  

85-86

 Worked as a designer and programmer at Israeli Defense Forces.  



Teaching Experience



Students evaluations of my teaching will be supplied upon request.


Main reference for teaching abilities

Prof. Judith Gal-Ezer
The Open University of Israel
16, Klausner St. Tel-Aviv 61392,
Israel
E-mail: galezer@cs.openu.ac.il    Phone: 972-3-6460744

Further references regards teaching would be supplied by request.