next up previous
Next: About this document ...

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 research assistant
Computer Science Department
Stanford University
Supervisor: Prof. Leonidas J. Guibas.

List of Publications

A. Papers in Journals

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

15.
A. Efrat and M.J. Katz, Computing an Euclidean Bottleneck Matching in Higher dimension. Information Processing Letters. To appear.




B. Papers in Proceedings of Conferences

1.
R. Bar-Yehuda, A. Efrat and A. Itai, A simple algorithm for maintaining the center of a planar point-set, Proc. 5th Canad. Conf. Comput. Geom. 1993, 252-257.
2.
A. Efrat, M. Lindenbaum and M. Sharir, Finding maximally consistent sets of halfspaces, Proc. 5th Canad. Conf. Comput. Geom., 1993, 432-436.

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

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

C. Reports

1.
N. Cohen, A. Efrat and F. Bruckstein, On Ants Crickets and Frogs in circular pursuit. Report. CIS-9309. Faculty of Computer Science, Technion - IIT.
2.
A. Efrat, Finding approximate matching of points and segments under translation, manuscript 1995.

D. In Preparation

1.
A. Efrat, P. Indyk and Suresh Venkatasubramanian. Pattern Matching for Sets of Segments. In Preparation.

2.
Alon Efrat, Frank Hoffmann, Klaus Kriegel and Christof Schultz, Covering Simple Polygonal Regions by Ellipses. In Preparation.

Education

1998 Ph.D. in Computer Science, Tel-Aviv University, Israel.  
  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 Dr. Reuven Bar-Yehuda  
     
1991 B.Sc. in Applied Mathematics, Mathematics Department, The Technion, Israel.  
     



Awards and Grants

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



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.

References












 
next up previous
Next: About this document ...
Alon Efrat
1999-12-16