List of Publications


Alon Efrat



A. Patents

Buddy Tracking - A system for proximity alerts between friends.

B. 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 (CGTA) 3 (1994), 277-288.
3 "Subpixel Image Registration Using Circular Fiducials", with C. Gotsman, International J. of Computational Geometry and Applications (IJCGA) 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 (CGTA) 4 (1995), 119-136.
5 " A near-linear algorithm for the planar segment center problem" with M. Sharir, Discrete and Computational Geometry (DCG) 16 (1996), 239-257.
6 " Separating and shattering long line segments" with O. Schwarzkopf, Information Processing Letters 64 (1998), 309-314.
7 " Geometric pattern matching in d-dimensional space" with L.P. Chew, D. Dor and K. Kedem, Discrete and Computational Geometry (DCG), 21 (1999) 257-274.
8 " On the Union of $\alpha$-Curved Objects" with M. Katz, Computational Geometry: Theory and Applications (CGTA). 14 (1999), 241-254.
9 " On the complexity of the union of fat objects in the plane" with M. Sharir, Discrete and Computational Geometry (DCG). 23 (2000), 171-189.
10 " Vertical decomposition of shallow levels in 3-dimensional arrangements and its applications", with P. K. Agarwal and M. Sharir, SIAM J. Computing 29 (2000), 912-953 .
11 "Dynamic data structures for fat objects and their applications" with M. J. Katz, F. Nielsen and M. Sharir, Computational Geometry: Theory and Applications (CGTA), 15 (2000), 215-227.
12 " Computing an Euclidean Bottleneck Matching in Higher dimension" with M. Katz, Information Processing Letters (IPL), 4 (2000), 169-174.
13 " Geometry helps in bottleneck matching and related problems" with M. Katz and A. Itai, Algorithmica, 1 (2001) 1-28.
14 " Efficient Algorithms and Regular Data Structures for Dilation, Location and Proximity Problems", with A. Amir, P. Indyk and H. Samet, Algorithmica. (2001) 166-187.
15 " 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 (DCG). 25 (2001), 203-220.
16 " "Fly Cheaply: On the Minimum Fuel-Consumption Problem" , with Timothy M. Chan, J. Algorithm 41 (2001), 330-337.
17 "Using and Determining Location in a Context-Sensitive Tour Guide: The Guide Experience", with Nigel Davis, Keith Cheverst and Keith Mitchell. IEEE computers 34 (2001), 35-41.
18 "Geometric Algorithms for the Analysis of 2D-Electrophoresis Gels", with F. Hoffmann, K. Kriegel, C. Schultz and C. Wenk, Journal of Computational Biology (JCB), special issue dedicated to RECOMB), 9 (2002), 299-316.
19 "Similarity Measures between Polylines with Applications to Morphing and Polygon Sweeping", with L. J. Guibas, S. Har-Peled, J. S. B. Mitchell and T.M. Murali. Discrete and Computational Geometry (DCG), (2002), 535-569.
20 ""Covering Shapes by Ellipses", with F. Hoffmann, K. Kriegel, C. Knauer, G. Rote and C. Wenk, Algorithmica - special issue on Shape Algorithms, (2003), 145-160.
21 "Search the Audio, Browse the Video - A Generic Paradigm for Video Collections", with A. Amir and S. Srinivasan, EURASIP Journal on Applied Signal Processing , 2(2003), 209-222.
22 "Matching Planar Maps", with H. Alt, G. Rote and C. Wenk, J. Algorithms , 49 (2003) 262-283.
23 "Pattern Matching for Sets of Segments" with P. Indyk and S. Venkatasubramanian, Algorithmica, 40(2004), 147-160 .
24 The Complexity of the Union of $(\alpha,\beta)$-Covered Objects", SIAM J. Computing , 34(2005), 755-787.
25 "Computing Homotopic Shortest Paths Efficiently", with S. Kobourov and A. Lubiw, Computational Geometry Theory and Applications (CGTA) to appear.
26 "On the Union of $\kappa$-Round Objects in Three and Four Dimensions", with B. Aronov, V. Koltun and M. Sharir, Discrete and Computational Geometry (DCG) (special issue dedicated to best papers from SoCG 2004), to appear.
27 "On Simultaneous, Planar Graph Embeddings", with P. Brass, E. Cenek, C. A. Duncan, C. Erten, D. Ismailescu, S. G. Kobourov, A. Lubiw and J. S. B. Mitchell, Comp. Geom. Theorey and Application (CGTA), to appear .
28 "On Incremental Rendering of Silhouette Maps of a Polyhedral Scene", with L.J. Guibas and O.A. Hall-Holt and L. Zhang, Computational Geometry Theory and Applications (CGTA), to appear.
29 "On Finding a Guard that Sees Most and a Shop that Sells Most", with O. Cheong and S. Har-Peled, Disc. Computational Goemetry (DCG) to appear.
30 "Fixed-Location Circular Arc Drawings", with C. Erten and S. Kobourov, Journal of Graph Algorithms and Applications, to appear.
31 "Locating Guards in Art Galleries", with S. Har-Peled, Information Processing Letters (IPL), to appear.
32 "Drawing with Fat Edges", with C. A. Duncan, A. Efrat, S. G. Kobourov and C. Wenk, Int. Journal of Foundations of Computer Science (IJFCS). Special Issue of on Graph Drawing. to appear.
33 "Buddy tracking, efficient proximity detection among mobile friends", with A. Amir, J. Myllymaki, L. Palaniappan and K. Wampler, Pervasive and Mobile Computing to appear after revision.
34 ""Curve Matching, Time Warping, and Light Fields, New Algorithms for Computing Similarity between Curves", with Q. Fan and S. Venkatasubramanian, J. Mathematic Imaging and Vision, to appear after revision.
35 "Maximizing lifetime of wireless sensor networks through optimal single-session flow routing," with Y.T. Hou, Y. Shi, J. Pan and S.F. Midkiff, in IEEE Transactions on Mobile Computing, to appear.
36 "Phenotypes of Drosophila Brain Neurons in Primary Culture Reveal a Role for Fascin in Neurite Shape and Trajectory", with R. Kraft, M. Escobar, M. Narro, J. Kurtis, K. Barnard, and L. Restifo, The Journal of Neuroscience, to appear.


C. Papers in Proceedings of Competitive Peer-Reviewed Conferences
1 " Computing the smallest k-enclosing circle and related problems" with M. Sharir and A. Ziv, Proc. Workshop Algorithms Data Structures (WADS) 1993, LNCS vol. 709 325-336.
2 " A near-linear algorithm for the planar segment center problem", with M. Sharir, in Proc. 5th ACM-SIAM Symp. Discrete Algorithms (SODA), 1994, 87-97.
3 "Subpixel Image Registration Using Circular Fiducials", with C. Gotsman, in Proc. of the second Israeli Symposium on Theory of Computing and Systems 1994, 127-136.
4 " Vertical decomposition of shallow levels in 3-dimensional arrangements and its applications", with P.K. Agarwal and M. Sharir, in Proc. 11th Symposium on Computational Geometry (SoCG) , 1995, 39-50.
5 " Geometric pattern matching in d-dimensional space", with L.P. Chew, D. Dor and K. Kedem, Third European Symposium on Algorithms (ESA), 1995, LNCS vol. 979, 264-279.
6 " Improvements on bottleneck matching and related problems, using geometry", with A. Itai, in Proc. 12th Symp. on Computational Geometry (SoCG), 1996, 301-310.
7 " Computing most-uniform and minimum deviation matchings in geometric settings" with M.J. Katz, in Proc. 7th International Symp. on Algorithms and Computational (ISAAC), 1996, 115-125.
8 " Separating and shattering long line segments", with O. Schwarzkopf, in Proc. International Symp. Algorithms and Computational (ISAAC), 1996, 36-44.
9 " On the complexity of the union of fat objects in the plane", with M. Sharir, in Proc. 13th Symp. Computational Geometry (SoCG), 1997, 104-112.
10 "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) 1997, 297-396.
11 " On the Union of $\alpha$-Curved Objects", with M. Katz, in Proc. 14th Annual Symposium on Computational Geometry (SoCG), 1998, 206-213.
12 " Fly Cheaply: On the Minimum Fuel-Consumption Problem", with S. Har-Peled, in Proc. 14th Annual Symposium on Computational Geometry (SoCG), 1998, 143-145.
13 " 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 (SWAT), 1998, 322-334.
14 " The Complexity of the Union of $(\alpha,\beta)$-Covered Objects", Proc. 15th Annual Symposium on Computational Geometry (SoCG), 1999, 134-142.
15 " Efficient Algorithms and Regular Data Structures for Dilation, Location and Proximity Problems". with A. Amir, P. Indyk and H. Samet, in Proc. 40 IEEE Symposium on Foundations of Computer Science (FOCS), 1999. 160-170.
16 " 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, 345-352.
17 " On Incremental Rendering of Silhouette Maps of a Polyhedral Scene" with L. Zhang, L.J. Guibas and O.A. Hall-Holt, in Proc. 11th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2000, 910-917. (Journal's version).
18 " 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 (SODA), 2000, 297-936.
19 "Pattern Matching for Sets of Segments" with P. Indyk and S. Venkatasubramanian, Proc. 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 295-304, 2001. (Journal's version).
20 "Morphing between Curves" with S. Har-Peled, L. Guibas and T.M. Murali, in Proc. 12th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2001, 680-689.
21 "Geometric Algorithms for the Analysis of 2D-Electrophoresis Gels" with rank Hoffmann, Klaus Kriegel, Christof Schultz and Carola Wenk, in The Fifth International Conference on Computational Molecular Biology. (RECOMB) 2001, 114-123.
22 "Drawing with Fat Edges" with C. A. Duncan, S. G. Kobourov and C. Wenk, Graph Drawing (GD) 2001. LNCS vol. 2265, 162-177.
23 "Developments in Phonetic Word Retrieval" with A. Amir, and S. Srinivasan, ACM Tenth International Conference on Information and Knowledge Management (CIKM), 2001, 580-582.
24 "Covering Shapes by Ellipses" with F. Hoffmann, K. Kriegel, C. Knauer, G. Rote and C. Wenk, in ACM-SIAM Symposium on Discrete Algorithms (SODA), 2002, 453-454.
25 " Locating Guards in Art Galleries" with S. Har-Peled, 2nd International Conference on Theoretical Computer Science (IFIP) 2002, 181-192. (Journal Version).
26 "Computing Homotopic Shortest Paths Efficiently", with S. Kobourov and A. Lubiw, European Symposium on Algorithms (ESA) 2002, 411-423.
27 "Matching Planar Maps", with H. Alt, G. Rote and C. Wenk, ACM-SIAM Symposium on Discrete Algorithms (SODA), 2003, 589-592. ( Journal's version).
28 "Optimal Motion Strategies to Track and Capture a Predict able Target", with H. H. Gonzalez-Banos, S. Kobourov and L. Palaniappan, IEEE International Conference on Robotics and Automation (ICRA), 2003.
29 "Touring a Sequence of Polygons" with M. Dror, A. Lubiw and J. S. B. Mitchell, ACM Symposium on Theory of Computing (STOC), 2003, 473-482.
30 On Simultaneous, Planar Graph Embeddings, with P. Brass, E. Cenek, C. A. Duncan, C. Erten, D. Ismailescu, S. G. Kobourov, A. Lubiw and J. S. B. Mitchell, Workshop on Data Structures (WADS) 2003, 243-255.
31 "Fixed-Location Circular-Arc Drawing of Planar Graphs", with C. Erten and S. Kobourov, Graph Drawing (GD). 2003, 147-158.
32 "On Finding a Guard that Sees Most and a Shop that Sells Most", O. Cheong, A. Efrat and S. Har-Peled, ACM-SIAM Symposium on Discrete Algorithms (SODA), 2004, 1098-1107. (Journal's vesion)
33 "Buddy tracking - efficient proximity detection among mobile friends" A. Amir, A. Efrat, J. Myllymaki, L. Palaniappan and K. Wampler, The 23rd Conference of the IEEE Communications Society (INFOCOM) 2004. (Journal's version).
34 An Efficient Flooding Algorithm for Mobile Ad-hoc Networks, with J. Arango, M. Degermark and S. Pink, Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt) , 2004.
35 On the Union of Kappa-Round Objects in Three and Four Dimensions, with B. Aronov, V. Koltun and M. Sharir, Proc. 20th Annual Symposium on Computational Geometry (SoCG), 2004, 383--390. (journal's version).
36 "Hardware-Assisted Natural Neighbor Interpolation", with Q. Fan and V. Koltun, S. Krishnan and S. Venkatasubramanian, in Workshop on Algorithm Engineering and Experiments (ALENEX) 2005.
37 ""Approximation Algorithms for Two Optimal Location Problems in Sensor Networks", with S. Har-Peled and J. Mitchell, in IEEE 2nd Int. conf. on Broadband Communication, Networks and systems. (BROADNET) 2005.
38 " Force-Directed Approaches to Sensor Localization, with C. Erten, D. Forrester, A. Iyer, and S. G. Kobourov, 8th Workshop on Algorithm Engineering and Experiments (ALENEX) 2006.
39 "On the ICP Algorithm", with E. Ezra and M. Sharir ACM Symp. Computational Geometry (SoCG), 2006.
40 " "Retransmission and Back-off Strategies for Broadcasting in Multi-hop Wireless Networks", with J. Arango, S. Ramasubramanian and M. Krunz, in IEEE 3rd Int. conf. on Broadband Communication, Networks and systems. (BROADNET) 2006.
41. "Algorithm Design for Base Station Placement Problems in Sensor Networks", with Y. Shi and Y. T. Hou, in 3rd Int. Conf. on Quality of Service in Heterogeneous Wired/Wireless Networks 2006, to appear.
42. "Onroad Vehicular Broadcast" with Jesus Arango, Marwan Krunz and Srinivasan Ramasubramanian, 15th International Conference on Computer Communications and Networks (ICCCN'06) a Networks 2006, to appear.
43. "Coverage time optimization in sensor networks" with Ravi Balasubramanian and and Srinivasan Ramasubramanian Third IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS'06) 2006, to appear.
44. "Matching Slides To Presentation Videos", Q. Fan, A. Amir, K, Barnard, A. Efrat, and L. Ming, ACM SIGMM International Workshop on Multimedia Information Retrieval.
45. "Restricted strip covering and the sensor cover problem", A. L. Buchsbaum, A. Efrat S. Jain and S. Venkatasubramanian, Proc. 18th ACM-SIAM Symp. Discrete Algorithms (SODA) 2007, to appear.

D. Papers in Non-Competitive Venues.
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 (CCCG)., 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. (CCCG), 1993, 115-120.
4. Video contribution: "Growing Fat Graphs", with S. Kobourov, M. Stepp, and C. Wenk, ACM Symp. On Comp. Geometry, (SoCG) 277-278, 2002.
5. Video contribution: "Finding a curve in a map", with C. Wenk, H. Alt, L. Palaniappan and G�nter Rote, ACM Symp. On Comp. Geometry, (SoCG) 384-385, 2003.
6. "The LSST moving object pipeline", with K. Barnard, A. Connolly, L. Denneau, J. N. Heasley, R. Jedicke, J. M. Kubica, B. Moon, A. Moore, S. Morris, P. Rao, Observatory operations: strategies, processes, and systems, proceedings of SPIE Vol. #6270, 2006.
7. "Efficiently Tracking Moving Sources in the LSST" with J. Kubica, T. Axelrod, K. Barnard, A. Connolly, L. Denneau, J. Heasley, R. Jedicke, B. Moon, A. Moore, S. Morris, P. Rao, The 207th meeting of the American Astronomical Association. (AAS) 2006.
E. 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.