Abstract
We consider the problem of computing the discrete Fréchet distance between two polygonal curves when their vertices are imprecise. An imprecise point is given by a region and this point could lie anywhere within this region. By modelling imprecise points as balls in dimension d, we present an algorithm for this problem that returns in time \(2^{O(d^2)} m^2n^2\log^2(mn)\) the Fréchet distance lower bound between two imprecise polygonal curves with n and m vertices, respectively. We give an improved algorithm for the planar case with running time O( mn log2(mn) + (m 2 + n 2)log(mn)). In the d-dimensional orthogonal case, where points are modelled as axis-parallel boxes, and we use the L ∞ distance, we give an O(dmn log(dmn))-time algorithm.
We also give efficient O(dmn)-time algorithms to approximate the Fréchet distance upper bound, as well as the smallest possible Fréchet distance lower/upper bound that can be achieved between two imprecise point sequences when one is allowed to translate them. These algorithms achieve constant factor approximation ratios in “realistic” settings (such as when the radii of the balls modelling the imprecise points are roughly of the same size).
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Agarwal, P.K., Sharir, M.: Efficient algorithms for geometric optimization. Computing Surveys 30(4), 412–458 (1998)
Agarwal, P.K., Sharir, M., Toledo, S.: Applications of parametric searching in geometric optimization. J. Algorithms 17(3), 292–318 (1994)
Alt, H., Godau, M.: Computing the Fréchet distance between two polygonal curves. International Journal of Computational Geometry and Applications 5, 75–91 (1995)
Alt, H., Knauer, C., Wenk, C.: Matching polygonal curves with respect to the Fréchet distance. In: Ferreira, A., Reichel, H. (eds.) STACS 2001. LNCS, vol. 2010, pp. 63–74. Springer, Heidelberg (2001)
Alt, H., Knauer, C., Wenk, C.: Comparison of distance measures for planar curves. Algorithmica 38(1), 45–58 (2003)
Aronov, B., Har-Peled, S., Knauer, C., Wang, Y., Wenk, C.: Fréchet distance for curves, revisited. In: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol. 4168, pp. 52–63. Springer, Heidelberg (2006)
Dyer, M.E.: A class of convex programs with applications to computational geometry. In: Proc. 8th Symposium on Computational Geometry, pp. 9–15. ACM, New York (1992)
Edelsbrunner, H.: Geometry and Topology for Mesh Generation. Cambridge University Press, Cambridge (2001)
Eiter, T., Mannila, H.: Computing discrete Fréchet distance. Tech. Rep. CD-TR 94/64, Christian Doppler Laboratory for Expert Systems, TU Vienna, Austria (1994)
Frederickson, G.N., Johnson, D.B.: Generalized selection and ranking: Sorted matrices. SIAM Journal on Computing 13(1), 14–30 (1984)
Khanban, A.A., Edalat, A.: Computing Delaunay triangulation with imprecise input data. In: Proc. 15th Canadian Conference on Computational Geometry, pp. 94–97 (2003)
Knauer, C., Löffler, M., Scherfenberg, M., Wolle, T.: The directed Hausdorff distance between imprecise point sets. In: ISAAC. LNCS, vol. 5878, pp. 720–729. Springer, Heidelberg (2009)
Löffler, M., van Kreveld, M.J.: Largest and smallest tours and convex hulls for imprecise points. In: Arge, L., Freivalds, R. (eds.) SWAT 2006. LNCS, vol. 4059, pp. 375–387. Springer, Heidelberg (2006)
Löffler, M., Snoeyink, J.: Delaunay triangulation of imprecise points in linear time after preprocessing. Computational Geometry: Theory and Applications 43(3), 234–242 (2010)
Moffat, A., Turpin, A.: Compression and Coding Algorithms. Kluwer, Dordrecht (2002)
Rote, G.: Computing the Fréchet distance between piecewise smooth curves. Computational Geometry: Theory and Applications 37(3), 162–174 (2007)
Sember, J., Evans, W.: Guaranteed Voronoi diagrams of uncertain sites. In: Proc. 20th Annual Canadian Conference on Computational Geometry (2008)
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
Ahn, HK., Knauer, C., Scherfenberg, M., Schlipf, L., Vigneron, A. (2010). Computing the Discrete Fréchet Distance with Imprecise Input. In: Cheong, O., Chwa, KY., Park, K. (eds) Algorithms and Computation. ISAAC 2010. Lecture Notes in Computer Science, vol 6507. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-17514-5_36
Download citation
DOI: https://doi.org/10.1007/978-3-642-17514-5_36
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-17513-8
Online ISBN: 978-3-642-17514-5
eBook Packages: Computer ScienceComputer Science (R0)