Mridul Aanjaneya
Frederic Chazal
ABSTRACT
Many real-world data sets can be viewed of as noisy samples of special types of metric spaces called metric graphs [16]. Building on the notions of correspondence and Gromov-Hausdorff distance in metric geometry, we describe a model for such data sets as an approximation of an underlying metric graph. We present a novel algorithm that takes as an input such a data set, and outputs the underlying metric graph with guarantees. We also implement the algorithm, and evaluate its performance on a variety of real world data sets.
- Earthquake search. http://earthquake.usgs.gov/earthquakes/eqarchives/epic/.Google Scholar
- Openstreetmap. http://www.openstreetmap.org/.Google Scholar
- H. Abramowicz, D. Horn, U. Naftaly, and C. Sahar-Pikielny. Orientation selective neural network for cosmic muon identification. Nuclear Instruments and Methods in Physics Research Section A: Accelerators, Spectrometers, Detectors and Associated Equipment, 389(1--2):163--166, 1997. New Computing Techniques in Physics Research V.Google Scholar
- N. Amenta, M. Bern, and D. Eppstein. The crust and the β-skeleton: Combinatorial curve reconstruction. Graph. Models Image Process., 60(2):125--135, 1998. Google ScholarDigital Library
- E. Arias-Castro, D. L. Donoho,, and X. Huo. Adaptive multiscale detection of filamentary structures in a background of uniform random points. Annals of Statistics, 34(1):326--349, 2006.Google ScholarCross Ref
- D. Burago, Y. Burago, and S. Ivanov. A Course in Metric Geometry, volume 33 of Graduate Studies in Mathematics. American Mathematical Society, Providence, RI, 2001.Google Scholar
- F. Chazal, D. Cohen Steiner, and Q. Mérigot. Geometric Inference for Measures based on Distance Functions. Research Report RR-6930, INRIA, 2010.Google Scholar
- D. Chen, L. J. Guibas, J. Hershberger, and J. Sun. Road network reconstruction for organizing paths. In Proceedings 21st ACM-SIAM Symposium on Discrete Algorithms (SODA), 2010. Google ScholarDigital Library
- E. Choi, N. A. Bond, M. A. Strauss, A. L. Coil, M. Davis, and C. N. A. Willmer. Tracing the filamentary structure of the galaxy distribution at z~0.8. Monthly Notices of the Royal Astronomical Society, pages 692--, May 2010.Google Scholar
- T. K. Dey, K. Mehlhorn, and E. A. Ramos. Curve reconstruction: Connecting dots with good reason. In Proceedings of the Fifteenth Annual Symposium on Computational Geometry, pages 197--206. ACM, 1999. Google ScholarDigital Library
- T. K. Dey and R. Wenger. Reconstructing curves with sharp corners. Comput. Geom. Theory Appl., 19:89--99, July 2001. Google ScholarDigital Library
- C. R. Genovese, M. Perone-Pacifico, I. Verdinelli, and L. Wasserman. On the path density of a gradient field. Annals of Statistics, 37(6A):3236--3271, 2009.Google ScholarCross Ref
- C. R. Genovese, M. Perone-Pacifico, I. verdinelli, and L. Wasserman. Nonparametric Filament Estimation. ArXiv e-prints, Mar. 2010.Google Scholar
- M. Gromov. Metric Structures for Riemannian and Non-Riemannian Spaces. Birkhäuser, 2nd edition, 2007.Google Scholar
- K. Heath, N. Gelfand, M. Ovsjanikov, M. Aanjaneya, and L. J. Guibas. Image webs: Computing and exploiting connectivity in image collections. Twenty-Third IEEE Conference on Computer Vision and Pattern Recognition, 2010.Google ScholarCross Ref
- P. Kuchment. Quantum graphs I. Some basic structures. Waves in Random Media, 14(1):S107--S128, 2004.Google ScholarCross Ref
- N. Qaddoumi, E. Ranu, J. D. McColskey, R. Mirshahi, and R. Zoughi. Microwave detection of stress-induced fatigue cracks in steel and potential for crack opening determination. Research in Nondestructive Evaluation, 12(2):87--104, 2000.Google ScholarCross Ref
- J. Siek, L.-Q. Lee, and A. Lumsdaine. Boost graph library. http://www.boost.org/libs/graph/, June 2000.Google Scholar
- F. Tupin, H. Maitre, Mangin, N. J.-F., J.-M., and E. Pechersky. Detection of linear features in SAR images: Application to road network extraction. IEEE Transactions on Geoscience and Remote Sensing, 36:434--453, 1998.Google ScholarCross Ref
- Metric graph reconstruction from noisy data
Recommendations
Statistical analysis of metric graph reconstruction
A metric graph is a 1-dimensional stratified metric space consisting of vertices and edges or loops glued together. Metric graphs can be naturally used to represent and model data that take the form of noisy filamentary structures, such as street maps, ...
A conjecture on the reconstruction of graphs from metric balls of their vertices
In this paper we investigate a new graph reconstruction problem which was introduced in a paper by Levenshtein, Konstantinova, Konstantinov and Molodtsov [Reconstruction of a graph from 2-vicinities of its vertices, Discrete Appl. Math., accepted for ...
Rank-determining sets of metric graphs
A metric graph is a geometric realization of a finite graph by identifying each edge with a real interval. A divisor on a metric graph @C is an element of the free abelian group on @C. The rank of a divisor on a metric graph is a concept appearing in ...
Comments