1 Search Results for "Xu, Hanzhong"

Document
DOI: 10.4230/LIPIcs.SoCG.2016.55
On Computing the Fréchet Distance Between Surfaces

Authors: Amir Nayyeri and Hanzhong Xu

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

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.
Cite as

Amir Nayyeri and Hanzhong Xu. On Computing the Fréchet Distance Between Surfaces. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 55:1-55:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{nayyeri_et_al:LIPIcs.SoCG.2016.55,
  author =	{Nayyeri, Amir and Xu, Hanzhong},
  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 =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.55},
  URN =		{urn:nbn:de:0030-drops-59471},
  doi =		{10.4230/LIPIcs.SoCG.2016.55},
  annote =	{Keywords: Surfaces, Terrains, Frechet distance, Parametrized complexity, normal coordinates}
}
  • Refine by Author
  • 1 Nayyeri, Amir
  • 1 Xu, Hanzhong

  • Refine by Classification

  • Refine by Keyword
  • 1 Frechet distance
  • 1 Parametrized complexity
  • 1 Surfaces
  • 1 Terrains
  • 1 normal coordinates

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2016

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact