7.

# REFERENCES

[1] I. Abraham, D. Dolev, and D. Malkhi. Lls: A locality aware location service for mobile ad hoc networks. In Proc. of 2nd Joint Workshop on Foundations of Mobile Computing DIALM-POMC), 2004.

[2] K. Alzoubi, P.-J. Wan, and O. Frieder. Message-optimal connected dominating sets in mobile ad hoc networks. In MobiHOC, 2002.

[3] P. Assouad. Plongements lipschitziens dans R^{n}. Bull. Soc. Math. France, 111(4):429–448, 1983.

[4] B. Awerbuch. Complexity of network synchronization. Journal of the ACM JACM), 32(4):804–823, 1985.

[5] B. Awerbuch, A. V. Goldberg, M. Luby, and S. A. Plotkin. Network decomposition and locality in distributed computation. In Proc. of the 30th Symp. on Foundations of Computer Science FOCS), pages 364–369, 1989.

[6] B. Awerbuch and D. Peleg. Routing with polynomial communication-space trade-off. SIAM J. Discret. Math., 5(2):151–162, 1992.

[7] Y. Bartal, J. W. Byers, and D. Raz. Global optimization using local information with applications to flow control. In Proc. of the 38th IEEE Symp. on the Foundations of Computer Science FOCS), pages 303–312, 1997.

[8] S. Capkun, M. Hamdi, and J. P. Hubaux. Gps-free positioning in mobile ad-hoc networks. Cluster Computing, 5(2), April 2002.

[9] R. Cole and U. Vishkin. Deterministic coin tossing with applications to optimal parallel list ranking. Information and Control, 70(1):32–53, 1986.

[10] J. Gao, L. Guibas, J. Hershberger, L. Zhang, and A. Zhu. Discrete mobile centers. In Proc. of the 17th annual symposium on Computational geometry SCG), pages 188–196. ACM Press, 2001.

[11] A. Goldberg, S. Plotkin, and G. Shannon. Parallel symmetry-breaking in sparse graphs. SIAM Journal on Discrete Mathematics SIDMA), 1(4):434–446, 1988.

[12] A. Gupta, R. Krauthgamer, and J. Lee. Bounded geometries, fractals, and low-distortion embeddings. In Proc. of 44th IEEE Symp. on Foundations of Computer Science FOCS), 2003.

[13] J. Heinonen. Lectures on Analysis of Metric Spaces. Springer-Verlag, New York, 2001.

[14] J. Kleinberg, A. Slivkins, and T. Wexler. Triangulation and embedding using small sets of beacons. In Proc. of 45th IEEE Symp. on Foundations of Computer Science FOCS), 2004.

[15] R. Krauthgamer and J. Lee. Navigating nets: Simple algorithms for proximity search. In Proc. of 15th ACM-SIAM Symp. on Discrete Algorithms SODA), 2004.

[16] F. Kuhn, T. Moscibroda, and R. Wattenhofer. The price of being near-sighted. submitted, 2004.

[17] F. Kuhn, T. Moscibroda, and R. Wattenhofer. What cannot be computed locally! In Proc. of the 23rd ACM Symposium on Principles of Distributed Computing PODC), pages 300–309, 2004.

[18] F. Kuhn and R. Wattenhofer. Constant-time distributed dominating set approximation. In Proc. of the 22nd ACM Symp. on Principles of Distributed Computing PODC), pages 25–32, 2003.

[19] F. Kuhn, R. Wattenhofer, Y. Zhang, and A. Zollinger. Geometric ad-hoc routing: Of theory and practice. In Proc. of 22nd ACM Symp. on Principles of Distributed Computing PODC), 2003.

[20] N. Linial. Locality in distributed graph algorithms. SIAM Journal on Computing, 21(1):193–201, February 1992.

[21] N. Linial and M. Saks. Low diameter graph decompositions. Combinatorica, 13(4):441–454, 1993.

[22] M. Luby. A simple parallel algorithm for the maximal independent set problem. SIAM Journal on Computing, 15:1036–1053, 1986.

[23] A. Panconesi and A. Srinivasan. Improved distributed algorithms for coloring and network decomposition problems. In Proc. of the 24th annual ACM symposium on Theory of computing STOC), pages 581–592. ACM Press, 1992.

[24] C. G. Plaxton, R. Rajaraman, and A. W. Richa. Accessing nearby copies of replicated objects in a distributed environment. In Proceedings of the 9th Annual ACM Symposium on Parallel Algorithms and Architectures SPAA), pages 311–320, 1997.

[25] P. Raghavan and C. D. Thompson. Randomized rounding: A technique for provably good algorithms and algorithmic proofs. Combinatorica, 7(4):365–374, 1987.

[26] K. Talwar. Bypassing the embedding: Approximation schemes and compact representations for low dimensional metrics. In Proc. of 36th ACM Symp. on Theory of Computing STOC), 2004.

[27] Y. Wang and X.-Y. Li. Localized construction of bounded degree and planar spanner for wireless ad hoc networks. In Proc. of 1st Joint Workshop on Foundations of Mobile Computing DIALM-POMC), 2003.

[28] R. Wattenhofer, L. Li, P. Bahl, and Y.-M. Wang. Distributed topology control for power efficient operation in multihop wireless ad hoc networks. In Proc. of 20th INFOCOM, 2001.