License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2016.55
URN: urn:nbn:de:0030-drops-59471
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/5947/
Go to the corresponding LIPIcs Volume Portal

Nayyeri, Amir ; Xu, Hanzhong

On Computing the Fréchet Distance Between Surfaces

pdf-format:
LIPIcs-SoCG-2016-55.pdf (0.6 MB)

Abstract

We describe two (1+epsilon)-approximation algorithms for computing the Fréchet distance between two homeomorphic piecewise linear surfaces R and S of genus zero and total complexity n, with Frechet distance delta.

(1) A 2^{O((n + ( (Area(R)+Area(S))/(epsilon.delta)^2 )^2 )} time algorithm if R and S are composed of fat triangles (triangles with angles larger than a constant).

(2) An O(D/(epsilon.delta)^2) n + 2^{O(D^4/(epsilon^4.delta^2))} time algorithm if R and S are polyhedral terrains over [0,1]^2 with slope at most D.

Although, the Fréchet distance between curves has been studied extensively, very little is known for surfaces. Our results are the first algorithms (both for surfaces and terrains) that are guaranteed to terminate in finite time. Our latter result, in particular, implies a linear time algorithm for terrains of constant maximum slope and constant Frechet distance.

BibTeX - Entry

@InProceedings{nayyeri_et_al:LIPIcs:2016:5947,
  author =	{Amir Nayyeri and Hanzhong Xu},
  title =	{{On Computing the Fr{\'e}chet Distance Between Surfaces}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{55:1--55:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{S{\'a}ndor Fekete and Anna Lubiw},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/5947},
  URN =		{urn:nbn:de:0030-drops-59471},
  doi =		{10.4230/LIPIcs.SoCG.2016.55},
  annote =	{Keywords: Surfaces, Terrains, Frechet distance, Parametrized complexity, normal coordinates}
}

Keywords: Surfaces, Terrains, Frechet distance, Parametrized complexity, normal coordinates
Collection: 32nd International Symposium on Computational Geometry (SoCG 2016)
Issue Date: 2016
Date of publication: 10.06.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI