Abstract
We develop a property testing algorithm with query complexity \(\tilde{\mathcal{O}}(\delta^{-5d} \epsilon^{-5} Dlog^6 \Delta\sqrt{n})\) that tests whether a directed geometric graph G = (P,E) with maximum degree D and vertex set P ⊆ {1,...,Δ}d (for constant d) is a Euclidean (1 + δ)-spanner. Such a property testing algorithm accepts every (1 + δ)-spanner and rejects with high constant probability every graph that is ε-far from this property, i.e., every graph that differs in more than ε|P| edges from every (1 + δ)-spanner.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alon, N., Dar, S., Parnas, M., Ron, D.: Testing of Clustering. SIAM Journal on Discrete Mathematics 16(3), 393–417 (2003)
Ahn, H.-K., Farshi, M., Knauer, C., Smid, M., Wang, Y.: Dilation-Optimal Edge Deletion in Polygonal Cycles. In: Algorthims and Computation, pp. 88–99. Springer, Heidelberg (2007)
Alon, N., Fischer, E., Newman, I., Shapira, A.: A combinatorial characterization of the testable graph properties: it’s all about regularity. SIAM Journal on Computing 39(1), 143–167 (2009)
Agarwal, P.K., Klein, R., Knauer, C., Langerman, S., Morin, P., Sharir, M., Soss, M.: Computing the Detour and Spanning Ratio of Paths, Trees, and Cycles in 2D and 3D. Discr. & Computational Geometry 39(1-3), 17–37 (2007)
Arya, S., Das, G., Mount, M., Salowe, J.S., Smid, M.: Euclidean spanners: short, thin, and lanky. In: Proceedings of the 27th Annnual ACM Symposium on the Theory of Computing (STOC), pp. 489–498 (1995)
Ben-Zwi, O., Lachish, O., Newman, I.: Lower bounds for testing Euclidean Minimum Spanning Trees. Information Processing Letters 102(6), 219–225 (2007)
Batu, T., Fortnow, L., Fischer, E., Kumar, R., Rubinfeld, R., White, P.: Testing Random Variables for Independence and Identity. In: Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science (FOCS), pp. 442–451 (2001)
Batu, T., Fortnow, L., Rubinfeld, R., Smith, W., White, P.: Testing that distributions are close. In: Proceedings of the 41st IEEE Symposium on Foundations of Computer Science (FOCS), pp. 259–269 (2000)
Benjamini, I., Schramm, O., Shapira, A.: Every minor-closed property of sparse graphs is testable. In: Proceedings of the 40th Annnual ACM Symposium on the Theory of Computing (STOC), pp. 393–402 (2008)
Blais, E.: Testing juntas nearly optimally. In: Proceedings of the 41st Annnual ACM Symposium on the Theory of Computing (STOC), pp. 151–158 (2009)
Blum, M., Luby, M., Rubinfeld, R.: Self-Testing/Correcting with Applications to Numerical Problems. In: Proceedings of the 22nd Annnual ACM Symposium on the Theory of Computing (STOC), pp. 73–83 (1990)
Callahan, P.B., Kosaraju, S.R.: Faster algorithms for some geometric graph problems in higher dimensions. In: Proceedings of the 4th Annnual ACM-SIAM Symposium on Discr. Algorithms (SODA), pp. 291–300 (1993)
Chazelle, B., Liu, D., Magen, A.: Sublinear Geometric Algorithms. SIAM Journalon Computing 35(3), 627–646 (2006)
Clarkson, K.L.: Approximating algorithms for shortest path motion planning. In: Proceedings of the 19th Annnual ACM Symposium on the Theory of Computing (STOC), pp. 56–65 (1987)
C̃zumaj, A., Ẽrgün, F., F̃ortnow, L., M̃agen, A., Ñewman, I., R̃ubinfeld, R., S̃ohler, C.: Approximating the Weight of the Minimum Spanning Tree in Sublinear Time. SIAM Journal on Comp. 35(1), 91–109 (2005)
Czumaj, A., Shapira, A., Sohler, C.: Testing hereditary properties of nonexpanding bounded-degree graphs. SIAM Journal on Computing 38(6), 2499–2510 (2009)
Czumaj, A., Sohler, C.: Property Testing with Geometric Queries. In: Meyer auf der Heide, F. (ed.) ESA 2001. LNCS, vol. 2161, pp. 266–277. Springer, Heidelberg (2001)
Czumaj, A., Sohler, C., Ziegler, M.: Property Testing in Computational Geometry. In: Paterson, M. (ed.) ESA 2000. LNCS, vol. 1879, pp. 155–166. Springer, Heidelberg (2000)
Czumaj, A., Sohler, C.: Testing Euclidean minimum spanning trees in the plane. ACM Transactions on Alg. 4(3) (2008)
Czumaj, A., Sohler, C.: Estimating the Weight of Metric Minimum Spanning Trees in Sublinear Time. SIAM Journal on Computing 39(3), 904–922 (2009)
Ergun, F., Kannan, S., Kumar, R., Rubinfeld, R., Viswanathan, M.: Spot-Checkers. J. of Computer and System Sciences 60(3), 717–751 (2000)
Eppstein, D., Wortman, K.A.: Minimum dilation stars. Computational Geometry: Theory and Applications 37(1), 27–37 (2007)
Farshi, M., Giannopoulos, P., Gudmundsson, J.: Finding the best shortcut in a geometric network. In: Proceedings of the 21th Annnual ACM Symposium on Computational Geometry, pp. 327–335 (2005)
Fischer, E., Lehman, E., Newman, I., Raskhodnikova, S., Rubinfeld, R., Samorodnitsky, A.: Monotonicity testing over general poset domains. In: Proceedings of the 34th Annnual ACM Symposium on the Theory of Computing (STOC), pp. 474–483 (2002)
Goldreich, O., Goldwasser, S., Lehman, E., Ron, D., Samorodnitsky, A.: Testing Monotonicity. Combinatorica 20(3), 301–337 (2000)
Goldreich, O., Goldwasser, S., Ron, D.: Property Testing and its Connection to Learning and Approximation. J. of the ACM 45(4), 653–750 (1998)
Har-Peled, S., Mazumdar, S.: On Coresets for k-Means and k-Median Clustering. In: Proceedings of the 36th Annnual ACM Symposium on the Theory of Computing (STOC), pp. 291–300 (2004)
Keil, M.: Approximating the complete Euclidean graph. In: Karlsson, R., Lingas, A. (eds.) SWAT 1988. LNCS, vol. 318, pp. 208–213. Springer, Heidelberg (1988)
Kaufman, T., Sudan, M.: Algebraic property testing: the role of invariance. In: Proceedings of the 40th Annnual ACM Symposium on the Theory of Computing (STOC), pp. 403–412 (2008)
Narasimhan, G., Smid, M.: Approximating the Stretch Factor of Euclidean Graphs. SIAM Journal on Computing, 978–989 (2000)
Narasimhan, G., Smid, M.: Geometric Spanner Networks. Cambridge University Press, Cambridge (2007)
Ron, D., Parnas, M.: Testing the Diameter of Graphs. Random Structures & Algorithms 20(2), 165–183 (2002)
Rademacher, L., Vempala, S.: Testing Geometric Convexity. In: Proceedings of the 24th Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pp. 469–480 (2004)
Rubinfeld, R., Sudan, M.: Robust Characterizations of Polynomials with Applications to Program Testing. SIAM Journal on Computing 25(2), 252–271 (1996)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hellweg, F., Schmidt, M., Sohler, C. (2010). Testing Euclidean Spanners. In: de Berg, M., Meyer, U. (eds) Algorithms – ESA 2010. ESA 2010. Lecture Notes in Computer Science, vol 6346. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-15775-2_6
Download citation
DOI: https://doi.org/10.1007/978-3-642-15775-2_6
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-15774-5
Online ISBN: 978-3-642-15775-2
eBook Packages: Computer ScienceComputer Science (R0)