TSP-Based Curve Reconstruction in Polynomial Time

Althaus, Ernst; Mehlhorn, Kurt

アイテム詳細

登録内容を編集ファイル形式で保存

一時保存へ追加

タグ情報を表示リリース履歴を表示詳細要約

公開

会議論文

TSP-Based Curve Reconstruction in Polynomial Time

MPS-Authors

/persons/resource/persons44003

Althaus, Ernst
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons45021

Mehlhorn, Kurt
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource

There are no locators available

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

フルテキスト (公開)

公開されているフルテキストはありません

付随資料 (公開)

There is no public supplementary material available

引用

Althaus, E., & Mehlhorn, K. (2000). TSP-Based Curve Reconstruction in Polynomial Time. In Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-00) (pp. 686-695). New York, USA: ACM.

引用: https://hdl.handle.net/11858/00-001M-0000-000F-3336-4

要旨

An instance of the curve reconstruction problem is a finite sample set $V$ of an unknown curve $\gamma$. The task is to connect the points in $V$ in the order in which they lie on $\gamma$. Giesen~\cite{SCG99*207} showed recently that the Traveling Salesman tour of $V$ solves the reconstruction problem under fairly week assumptions on $\gamma$ and $V$. We extend his result along three dimensions. We weaken the assumptions, give an alternate proof, and show that in the context of curve reconstruction, the Traveling Salesman tour can be constructed in polynomial time.