日本語
 
Help Privacy Policy ポリシー/免責事項
  詳細検索ブラウズ

アイテム詳細

  Why Walking the Dog Takes Time: Frechet Distance Has no Strongly Subquadratic Algorithms Unless SETH Fails

Bringmann, K. (2014). Why Walking the Dog Takes Time: Frechet Distance Has no Strongly Subquadratic Algorithms Unless SETH Fails. Retrieved from http://arxiv.org/abs/1404.1448.

Item is

基本情報

表示: 非表示:
資料種別: 成果報告書
LaTeX : Why Walking the Dog Takes Time: {Frechet} Distance Has no Strongly Subquadratic Algorithms Unless {SETH} Fails

ファイル

表示: ファイル
非表示: ファイル
:
arXiv:1404.1448.pdf (プレプリント), 303KB
ファイルのパーマリンク:
https://hdl.handle.net/11858/00-001M-0000-0024-41D2-3
ファイル名:
arXiv:1404.1448.pdf
説明:
File downloaded from arXiv at 2014-11-27 09:04
OA-Status:
閲覧制限:
公開
MIMEタイプ / チェックサム:
application/pdf / [MD5]
技術的なメタデータ:
著作権日付:
-
著作権情報:
-
CCライセンス:
http://arxiv.org/help/license

関連URL

表示:

作成者

表示:
非表示:
 作成者:
Bringmann, Karl1, 著者                 
所属:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

内容説明

表示:
非表示:
キーワード: Computer Science, Computational Geometry, cs.CG
 要旨: The Frechet distance is a well-studied and very popular measure of similarity of two curves. Many variants and extensions have been studied since Alt and Godau introduced this measure to computational geometry in 1991. Their original algorithm to compute the Frechet distance of two polygonal curves with n vertices has a runtime of O(n^2 log n). More than 20 years later, the state of the art algorithms for most variants still take time more than O(n^2 / log n), but no matching lower bounds are known, not even under reasonable complexity theoretic assumptions. To obtain a conditional lower bound, in this paper we assume the Strong Exponential Time Hypothesis or, more precisely, that there is no O*((2-delta)^N) algorithm for CNF-SAT for any delta > 0. Under this assumption we show that the Frechet distance cannot be computed in strongly subquadratic time, i.e., in time O(n^{2-delta}) for any delta > 0. This means that finding faster algorithms for the Frechet distance is as hard as finding faster CNF-SAT algorithms, and the existence of a strongly subquadratic algorithm can be considered unlikely. Our result holds for both the continuous and the discrete Frechet distance. We extend the main result in various directions. Based on the same assumption we (1) show non-existence of a strongly subquadratic 1.001-approximation, (2) present tight lower bounds in case the numbers of vertices of the two curves are imbalanced, and (3) examine realistic input assumptions (c-packed curves).

資料詳細

表示:
非表示:
言語: eng - English
 日付: 2014-04-052014-07-312014
 出版の状態: オンラインで出版済み
 ページ: 21 p.
 出版情報: -
 目次: -
 査読: -
 識別子(DOI, ISBNなど): arXiv: 1404.1448
URI: http://arxiv.org/abs/1404.1448
BibTex参照ID: bringmann_walking_arXiv_2014
 学位: -

関連イベント

表示:

訴訟

表示:

Project information

表示:

出版物

表示: