2 Search Results for "Telang, Gaurish"

Document
DOI: 10.4230/LIPIcs.ITCS.2023.51
On Flipping the Fréchet Distance

Authors: Omrit Filtser, Mayank Goswami, Joseph S. B. Mitchell, and Valentin Polishchuk

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract
The classical and extensively-studied Fréchet distance between two curves is defined as an inf max, where the infimum is over all traversals of the curves, and the maximum is over all concurrent positions of the two agents. In this article we investigate a "flipped" Fréchet measure defined by a sup min - the supremum is over all traversals of the curves, and the minimum is over all concurrent positions of the two agents. This measure produces a notion of "social distance" between two curves (or general domains), where agents traverse curves while trying to stay as far apart as possible. We first study the flipped Fréchet measure between two polygonal curves in one and two dimensions, providing conditional lower bounds and matching algorithms. We then consider this measure on polygons, where it denotes the minimum distance that two agents can maintain while restricted to travel in or on the boundary of the same polygon. We investigate several variants of the problem in this setting, for some of which we provide linear time algorithms. Finally, we consider this measure on graphs. We draw connections between our proposed flipped Fréchet measure and existing related work in computational geometry, hoping that our new measure may spawn investigations akin to those performed for the Fréchet distance, and into further interesting problems that arise.
Cite as

Omrit Filtser, Mayank Goswami, Joseph S. B. Mitchell, and Valentin Polishchuk. On Flipping the Fréchet Distance. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 51:1-51:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{filtser_et_al:LIPIcs.ITCS.2023.51,
  author =	{Filtser, Omrit and Goswami, Mayank and Mitchell, Joseph S. B. and Polishchuk, Valentin},
  title =	{{On Flipping the Fr\'{e}chet Distance}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{51:1--51:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.51},
  URN =		{urn:nbn:de:0030-drops-175548},
  doi =		{10.4230/LIPIcs.ITCS.2023.51},
  annote =	{Keywords: curves, polygons, distancing measure}
}
Document
DOI: 10.4230/LIPIcs.SOCG.2015.615
Computing Teichmüller Maps between Polygons

Authors: Mayank Goswami, Xianfeng Gu, Vamsi P. Pingali, and Gaurish Telang

Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)

Abstract
By the Riemann mapping theorem, one can bijectively map the interior of an n-gon P to that of another n-gon Q conformally (i.e., in an angle preserving manner). However, when this map is extended to the boundary it need not necessarily map the vertices of P to those of Q. For many applications it is important to find the "best" vertex-preserving mapping between two polygons, i.e., one that minimizes the maximum angle distortion (the so-called dilatation). Such maps exist, are unique, and are known as extremal quasiconformal maps or Teichmüller maps. There are many efficient ways to approximate conformal maps, and the recent breakthrough result by Bishop computes a (1+epsilon)-approximation of the Riemann map in linear time. However, only heuristics have been studied in the case of Teichmüller maps. We present two results in this paper. One studies the problem in the continuous setting and another in the discrete setting. In the continuous setting, we solve the problem of finding a finite time procedure for approximating Teichmüller maps. Our construction is via an iterative procedure that is proven to converge in O(poly(1/epsilon)) iterations to a (1+epsilon)-approximation of the Teichmuller map. Our method uses a reduction of the polygon mapping problem to the marked sphere problem, thus solving a more general problem. In the discrete setting, we reduce the problem of finding an approximation algorithm for computing Teichmüller maps to two basic subroutines, namely, computing discrete 1) compositions and 2) inverses of discretely represented quasiconformal maps. Assuming finite-time solvers for these subroutines we provide a (1+epsilon)-approximation algorithm.
Cite as

Mayank Goswami, Xianfeng Gu, Vamsi P. Pingali, and Gaurish Telang. Computing Teichmüller Maps between Polygons. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 615-629, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{goswami_et_al:LIPIcs.SOCG.2015.615,
  author =	{Goswami, Mayank and Gu, Xianfeng and Pingali, Vamsi P. and Telang, Gaurish},
  title =	{{Computing Teichm\"{u}ller Maps between Polygons}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{615--629},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Arge, Lars and Pach, J\'{a}nos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.615},
  URN =		{urn:nbn:de:0030-drops-50997},
  doi =		{10.4230/LIPIcs.SOCG.2015.615},
  annote =	{Keywords: Teichm\"{u}ller maps, Surface registration, Extremal Quasiconformal maps, Computer vision}
}
  • Refine by Author
  • 2 Goswami, Mayank
  • 1 Filtser, Omrit
  • 1 Gu, Xianfeng
  • 1 Mitchell, Joseph S. B.
  • 1 Pingali, Vamsi P.
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Computational geometry
  • 1 Theory of computation → Design and analysis of algorithms

  • Refine by Keyword
  • 1 Computer vision
  • 1 Extremal Quasiconformal maps
  • 1 Surface registration
  • 1 Teichmüller maps
  • 1 curves
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2015
  • 1 2023

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