Jie Gao

                                                                                jgao at graphics dot stanford dot edu

I graduated with Ph.D from Department of Computer Science, Stanford University in September 2004, under the surpervision of Professor Leonidas Guibas. I'll join Department of Computer Science, State University of New York at Stony Brook as an assistant professor in Fall 2005. During 2004-2005 I stay with the Center for the Mathematics of Information, Caltech. I got my BS degree from the Special Class for the Gifted Young, University of Science and Technology of China in July 1999.


My research focuses on design and analysis of geometric algorithms with applications in ad hoc communication and sensor networks, computational biology, etc. Read my research statement to see the details (w/ videos and pictures). 

  1. Efficient distributed clustering algorithm with good quality on moving points. 
  2. Good spanner graph for routing in mobile ad hoc networks. 
  3. Efficiently maintainable space partition structures on moving points, e.g., k-d-trees.
  4. Maintenance of approximate median/centerpoint of moving points.
  5. Load balancing routing in wireless networks.
  6. Well-separated pair decomposition for the unit-disk graph metric and its applications.
  7. Linear-size deformable spanners.
  8. Finding and bypassing "holes" in wireless sensor networks.
  9. Fractionally cascaded information in sensor networks.
  10. Distributed proximity maintenance between moving objects.
Selected Publications:

Ad hoc Communication and Sensor Networks

Q. Fang, J. Gao, L. J. Guibas, Landmark-Based Information Storage and Retrieval in Sensor Networks, to appear in the 25th Conference of the IEEE Communication Society (INFOCOM'06), April, 2006.

J. Bruck, J. Gao, A. Jiang, MAP: Medial Axis Based Geometric Routing in Sensor Networks, Proc. of the 11th Annual International Conference on Mobile Computing and Networking (MobiCom'05), 88-102, August, 2005.

J. Bruck, J. Gao, A. Jiang, Localization and Routing in Sensor Networks by Local Angle Information, Proc. of the Sixth ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc'05), 181-192, May, 2005.

J. Gao, L. J. Guibas, An Nguyen, Distributed Proximity Maintenance in Ad Hoc Mobile Networks, Proc. of the IEEE International Conference on Distributed Computing in Sensor Systems (DCOSS'05), 4-19, June, 2005. Here is the full version.

Q. Fang, J. Gao, L. J. Guibas, Vin de Silva, Li Zhang, "GLIDER: Gradient landmark-based distributed routing for sensor networks", IEEE INFOCOM'05, March, 2005.

J. Gao, L. Zhang, " Tradeoff between Stretch Factor and Load Balancing Ratio in Wireless Network Routing", ACM Symposium on Principles of Distributed Computing (PODC'04), pages 189-196, July, 2004 .

J. Gao, L. J. Guibas, J. Hershberger, L. Zhang, "Fractionally Cascaded Information in a Sensor Network", The 3rd International Symposium on Information Processing in Sensor Networks (IPSN'04), 311-319, April, 2004.

J. Gao, L. Zhang, "Load Balanced Short Path Routing in Wireless Networks", The 23rd Conference of the IEEE Communications Society (INFOCOM), vol. 23, no. 1, 1099-1108 March, 2004. Journal version to appear in IEEE Transactions on Parallel and Distributed Systems, Special Issue on Localized Communications, 2005.

Q. Fang, J. Gao, L. J. Guibas, "Locating and Bypassing Routing Holes in Sensor Networks", The 23rd Conference of the IEEE Communications Society (INFOCOM), vol. 23, no. 1, 2458-2468, March 2004. Journal version to appear in MONET Special Issue on Foundations of Mobile Computing, 2005.

J. Gao, L. J. Guibas, J. Hershberger, L. Zhang, A. Zhu, "Geometric Spanner for Routing in Mobile Networks ", In Proceedings of the 2nd ACM Symposium on Mobile Ad Hoc Networking & Computing (MobiHoc'01), 45-55, October, 2001. Journal version in IEEE Journal on Selected Areas in Communications Wireless Ad Hoc Networks, 2005, to appear.

Computational Geometry

J. Gao, M. Langberg, L. Schulman, Analysis of Incomplete Data and an Intrinsic-Dimension Helly Theorem, ACM-SIAM Symposium on Discrete Algorithms (SODA'06), January, 2006.

P. K. Agarwal, M. de Berg, J. Gao, L. J. Guibas, S. Har-Peled, Staying in the Middle: Exact and Approximate Medians in R1 and R2 for Moving Points, Proc. of the 17th Canadian Conference on Computational Geometry (CCCG'05), 42-45, August, 2005. The full paper is here.

J. Gao, L. J. Guibas, A. Nguyen, " Deformable Spanners and their Applications", The 20th ACM Annual Symposium on Computational Geometry (SoCG'04), 190-199, June, 2004. Journal version invited to Computational Geometry : Theory and Applications, to appear, 2005.

J. Gao, L. Zhang, "Well-Separated Pair Decomposition for the Unit-Disk Graph Metric and its Applications", In Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC '03), 483-492, June, 2003. Journal version in SIAM J. Computing, 35(1), 151-169, 2005.

P. K. Agarwal, J. Gao, L. J. Guibas, "Kinetic Medians and kd-trees", In Proceedings of the 10th Annual European Symposium on Algorithms (ESA'02), Lecture Notes in Computer Science 2461, 5-16, September, 2002.

J. Gao, L. J. Guibas, J. Hershberger, L. Zhang, A. Zhu, "Discrete Mobile Centers", Proceedings of the 17th ACM Symposium on Computational Geometry (SoCG'01), 188-196, June, 2001. Journal version invited to Discrete and Computational Geometry, 30(1), 45-65, 2003.


J. Gao, "Hierarchical Data Structures for Mobile Networks", Ph.D dissertation, Stanford University, August, 2004.

Other Writings:

J. Gao, "The 2-D k-set Problem in Computational Geometry", survey paper, April, 2002.

A collision-detection web page, March, 2000.

SCGY94 Forever!
Just for FUN!
Some Animations I did in CS348C: Computer Animation.
My daffodil 1 , 2
Photoes of my trip to Italy.  
Check out what WWW thinks of me: $%&*@@#!  
A wonderful book: LINKED: the new science of networks.
A good article for women.

Last updated: 11/02/2003