Abstract
We address the problem of localizing homology classes, namely, finding the cycle representing a given class with the most concise geometric measure. We study the problem with different measures: volume, diameter and radius.
For volume, that is, the 1-norm of a cycle, two main results are presented. First, we prove that the problem is NP-hard to approximate within any constant factor. Second, we prove that for homology of dimension two or higher, the problem is NP-hard to approximate even when the Betti number is O(1). The latter result leads to the inapproximability of the problem of computing the nonbounding cycle with the smallest volume and computing cycles representing a homology basis with the minimal total volume.
As for the other two measures defined by pairwise geodesic distance, diameter and radius, we show that the localization problem is NP-hard for diameter but is polynomial for radius.
Our work is restricted to homology over the ℤ2 field. Results over other fields have been studied recently by Dey et al.: In STOC, pp. 221–230 (2010).
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Arkin, E.M., Hassin, R.: Minimum-diameter covering problems. Networks 36(3), 147–155 (2000)
Arora, S., Babai, L., Stern, J., Sweedyk, Z.: The hardness of approximate optima in lattices, codes, and systems of linear equations. J. Comput. Syst. Sci. 54(2), 317–331 (1997)
Ausiello, G., Paschos, V.T.: Reductions, completeness and the hardness of approximability. Eur. J. Oper. Res. 172(3), 719–739 (2006)
Carlsson, E., Carlsson, G., de Silva, V.: An algebraic topological method for feature identification. Int. J. Comput. Geom. Appl. 16(4), 291–314 (2006)
Carlsson, G.: Topology and data. Bull. Am. Math. Soc. 46(2), 255–308 (2009)
Chambers, E.W., Erickson, J., Nayyeri, A.: Homology flows, cohomology cuts. In: STOC (2009)
Chambers, E.W., Erickson, J., Nayyeri, A.: Minimum cuts and shortest homologous cycles. In: Symposium on Computational Geometry (2009)
Chen, C., Freedman, D.: Quantifying homology classes II: Localization and stability. CoRR, abs/0709.2512 (2007)
Chen, C., Freedman, D.: Quantifying homology classes. In: Proceedings of the 25th Annual Symposium on Theoretical Aspects of Computer Science, pp. 169–180 (2008)
Chen, C., Freedman, D.: Measuring and computing natural generators for homology groups. Comput. Geom. 43(2), 169–181 (2010)
Cohen-Steiner, D., Edelsbrunner, H., Morozov, D.: Vines and vineyards by updating persistence in linear time. In: Proceedings of the 22nd ACM Symposium on Computational Geometry, pp. 119–126 (2006)
de Silva, V., Ghrist, R.: Coverage in sensor networks via persistent homology. Algebr. Geom. Topol. 7, 339–358 (2007)
Dey, T.K., Hirani, A.N., Krishnamoorthy, B.: Optimal homologous cycles, total unimodularity, and linear programming. In: STOC, pp. 221–230 (2010)
Dey, T.K., Li, K., Sun, J.: On computing handle and tunnel loops. In: IEEE Proc. NASAGEM (2007)
Dey, T.K., Li, K., Sun, J., Cohen-Steiner, D.: Computing geometry-aware handle and tunnel loops in 3D models. ACM Trans. Graph. 27(3) (2008)
Dey, T.K., Sun, J., Wang, Y.: Approximating loops in a shortest homology basis from point data. In: Symposium on Computational Geometry, pp. 166–175 (2010)
Erickson, J., Har-Peled, S.: Optimally cutting a surface into a disk. Discrete Comput. Geom. 31(1), 37–59 (2004)
Erickson, J., Nayyeri, A.: Minimum cuts and shortest non-separating cycles via homology covers. In: SODA (2011)
Erickson, J., Whittlesey, K.: Greedy optimal homotopy and homology generators. In: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1038–1046 (2005)
Fang, Q., Gao, J., Guibas, L.: Locating and bypassing routing holes in sensor networks. In: Mobile Networks and Applications, vol. 11, pp. 187–200 (2006)
Guskov, I., Wood, Z.J.: Topological noise removal. In: Proceedings of the Graphics Interface 2004 Conference, pp. 19–26 (2001)
Kirsanov, D., Gortler, S.J.: A discrete global minimization algorithm for continuous variational problems. Technical Report TR-14-04, Harvard University (2004)
MacKay, D.J.C.: Information Theory, Inference & Learning Algorithms. Cambridge University Press, Cambridge (2002)
Munkres, J.R.: Elements of Algebraic Topology. Addison–Wesley, Redwood (1984)
Niyogi, P., Smale, S., Weinberger, S.: Finding the homology of submanifolds with high confidence from random samples. Discrete Comput. Geom. 39(1), 419–441 (2008)
Sarkar, R., Yin, X., Gao, J., Luo, F., Gu, X.D.: Greedy routing with guaranteed delivery using Ricci flows. In: Proc. of the 8th International Symposium on Information Processing in Sensor Networks (IPSN’09), pp. 121–132 (2009)
Wikipedia. Book embedding. http://en.wikipedia.org/wiki/Book_embedding
Wikipedia. Suspension. http://en.wikipedia.org/wiki/Suspension_(topology)
Wood, Z.J., Hoppe, H., Desbrun, M., Schröder, P.: Removing excess topology from isosurfaces. ACM Trans. Graph. 23(2), 190–208 (2004)
Zomorodian, A., Carlsson, G.: Localized homology. In: Proceedings of the 2007 International Conference on Shape Modeling and Applications, pp. 189–198 (2007)
Author information
Authors and Affiliations
Corresponding author
Additional information
Partially supported by the Austrian Science Fund under grant P20134-N13.
Rights and permissions
About this article
Cite this article
Chen, C., Freedman, D. Hardness Results for Homology Localization. Discrete Comput Geom 45, 425–448 (2011). https://doi.org/10.1007/s00454-010-9322-8
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-010-9322-8