Computing the Fréchet distance between real-valued surfaces

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

3 Citations (Scopus)
88 Downloads (Pure)

Abstract

The Fréchet distance is a well-studied measure for the similarity of shapes. While efficient algorithms for computing the Fréchet distance between curves exist, there are only few results on the Fréchet distance between surfaces. Recent work has shown that the Fréchet distance is computable between piecewise linear functions f and g : M → Rk with M a triangulated surface of genus zero. We focus on the case k = 1 and M being a topological sphere or disk with constant boundary. Intuitively, we measure the distance between terrains based solely on the height function. Our main result is that in this case computing the Fréchet distance between f and g is in NP. We additionally show that already for k = 1, computing a factor 2 - ϵ approximation of the Fréchet distance is NP-hard, showing that this problem is in fact NP-complete. We also define an intermediate distance, between contour trees, which we also show to be NP-complete to compute. Finally, we discuss how our and other distance measures between contour trees relate to each other.

Original languageEnglish
Title of host publicationProc. 28th Annual Symposium on Discrete Algorithms (SODA)
EditorsP.N. Klein
Place of PublicationPhiladelphia
PublisherAssociation for Computing Machinery, Inc
Pages2443-2455
Number of pages13
ISBN (Electronic)978-1-61197-478-2
DOIs
Publication statusPublished - 2017
Event28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017) - Barcelona, Spain
Duration: 16 Jan 201719 Jan 2017
Conference number: 28

Conference

Conference28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017)
Abbreviated titleSODA 2017
CountrySpain
CityBarcelona
Period16/01/1719/01/17

Fingerprint Dive into the research topics of 'Computing the Fréchet distance between real-valued surfaces'. Together they form a unique fingerprint.

  • Cite this

    Buchin, K., Ophelders, T., & Speckmann, B. (2017). Computing the Fréchet distance between real-valued surfaces. In P. N. Klein (Ed.), Proc. 28th Annual Symposium on Discrete Algorithms (SODA) (pp. 2443-2455). Association for Computing Machinery, Inc. https://doi.org/10.1137/1.9781611974782.162