Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Curve Reconstruction in Arbitrary Dimension and the Traveling Salesman Problem

  • Conference paper
  • First Online:

Part of the book series:Lecture Notes in Computer Science ((LNCS,volume 1568))

Included in the following conference series:

  • 718Accesses

Abstract

Given a finite set of points sampled from a curve, we want to reconstruct the ordering of the points along the curve. Every ordering of the sample points can be defined by a polygon through these points. We show that for simple, regular curves Traveling Salesman Paths give the correct polygonal reconstruction, provided the points are sampled densely enough. In this case the polygonal reconstruction is part of the Delaunay Triangulation of the sample points. We use this observation to design an efficient algorithm for the reconstruction problem.

This work was supported by grants from the Swiss Federal Office for Education and Science (Projects ESPRIT IV LTR No. 21957 CGAL and No. 28155 GALIA)

Similar content being viewed by others

Keywords

References

  1. A.D. Alexandrov, Yu.G. ReshetnyakGeneral Theory of Irregular Curves, Kluwer Academic Publishers (1989)

    Google Scholar 

  2. N. Amenta, M. Bern, D. EppsteinThe Crust and the β-Skeleton: Combinatorial Curve Reconstruction, Graphical Models and Image Processing60/2:2, pp. 125–135 (1998)

    Article  Google Scholar 

  3. D. Attalir-Regular Shape Reconstruction from Unorganized Points, Proc. 13th Ann. ACM Symp. on Computational Geometry 1997, pp. 248–253 (1997)

    Google Scholar 

  4. M. de Berg, M. van Kreveld, M. Overmars, O. SchwarzkopfComputational Geometry, Springer (1997)

    Google Scholar 

  5. F. Bernardini, C.L. BajajSampling and Reconstructing Manifolds Using Alpha-Shapes, Proc. of the Ninth Canadian Conference on Computational Geometry 1997, pp. 193–198 (1997)

    Google Scholar 

  6. T.H. Cormen, C.E. Leiserson, R.L. RivestIntroduction to Algorithms, MIT Press (1990)

    Google Scholar 

  7. H. EdelsbrunnerAlgorithms in Combinatorial Geometry, Springer (1987)

    Google Scholar 

  8. D.G. Kirkpatrick, J.D. RadkeA framework for computational morphology, Computational Geometry (G. Toussaint, ed.), Elsevier pp. 217–248 (1983)

    Google Scholar 

  9. K. MengerUntersuchungen über eine allgemeine Metrik. Vierte Untersuchung. Zur Metrik der Kurven, Math. Ann.103, pp. 467–501 (1932)

    MathSciNet  Google Scholar 

  10. J. O’Rourke, H. Booth and R. WashingtonConnect-the-dots: A New Heuristic, Comp. Vision, Graph. Image Proc.39, pp. 258–266 (1987)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institut für Theoretische Informatik, ETH Zürich, CH-8092, Zürich, Switzerland

    Joachim Giesen

Authors
  1. Joachim Giesen

    You can also search for this author inPubMed Google Scholar

Editor information

Editors and Affiliations

  1. ESIEE, 2, Bd. Blaise Pascal, B.P. 99, F-93162 Noisy-Le-Grand Cedex, France

    Gilles Bertrand , Michel Couprie  & Laurent Perroton ,  & 

Rights and permissions

Copyright information

© 1999 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Giesen, J. (1999). Curve Reconstruction in Arbitrary Dimension and the Traveling Salesman Problem. In: Bertrand, G., Couprie, M., Perroton, L. (eds) Discrete Geometry for Computer Imagery. DGCI 1999. Lecture Notes in Computer Science, vol 1568. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-49126-0_13

Download citation

Publish with us

Societies and partnerships

[8]ページ先頭
©2009-2025 Movatter.jp