Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Hamiltonian triangulations for fast rendering

  • Original Articles
  • Published:
The Visual Computer Aims and scope Submit manuscript

Abstract

High-performance rendering engines are often pipelined; their speed is bounded by the rate at which triangulation data can be sent into the machine. An ordering such that consecutive triangles share a face, which reduces the data rate, exists if and only if the dual graph of the triangulation contains a Hamiltonian path. We (1) show thatany set ofn points in the plane has a Hamiltonian triangulation; (2) prove that certain nondegenerate point sets do not admit asequential triangulation; (3) test whether a polygonP has a Hamiltonian triangulation in time linear in the size of its visibility graph; and (4) show how to add Steiner points to a triangulation to create Hamiltonian triangulations that avoid narrow angles.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

We’re sorry, something doesn't seem to be working properly.

Please try refreshing the page. If that doesn't work, please contact support so we can address the problem.

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Avis D, ElGindy H (1987) Triangulating point sets in space. Discrete Comput Geom 2:99–111

    Google Scholar 

  2. Bern M, Eppstein D (1992) Mesh generation and optimal triangulation. Computing in Euclidean geometry. (Lecture Notes in Computer Science, Vol 1) World Scientific, Singapore

    Google Scholar 

  3. Bhattacharya P, Rosenfeld A (1994) Polygonal ribbons in two and three dimensions. Report, Department of Computer Science, University of Maryland, College Park, MD

    Google Scholar 

  4. Bose J, Toussaint G (1995) No quadrangulation is extremely odd. Technical Report 95-03, Department of Computer Science, University of British Columbia, Vancouver, BC

    Google Scholar 

  5. Cassidy R, Gregg E, Reeves R, Turmelle J (1991) IGL: the graphics library for the i860

  6. Chazelle B (1985) On the convex layers of a planar set. IEEE Trans Inform Theory IT-31:509–517

    Google Scholar 

  7. Christofides N (1976) Worst-case analysis of a new heuristic for the traveling salesman problem. In: Traub JF (ed) Symposium on New Directions and Recent Results in Algorithms and Complexity, New York, Academic Press, p 441

    Google Scholar 

  8. Croap H, Laumond JP (1989) Hamiltonian cycles in Delaunay complexes. Geometry and Robotics Workshop Proceedings, Toulouse, France (Lecture Notes in Computer Science, vol 391). Springer, Berlin Heildelberg New York, pp 292–305

    Google Scholar 

  9. Das G, Heffernan P, Narasimhan G (1993) LR-visibility in polygons. Proceedings of the 5th Canadian Conference on Computational Geometry, Waterloo, Canada, pp 303–308

  10. Dillencourt MB (1987) A non-Hamiltonian, nondegenerate Delaunay triangulation. Inform Process Lett 25:149–151

    Google Scholar 

  11. Dillencourt MB (1990) Hamiltonian cycles in planar triangulations with no separating triangles. J Graph Theory 14:31–49

    Google Scholar 

  12. Dillencourt MB (1992) Finding Hamiltonian cycles in Delaunay triangulations is NP-complete. Proceedings of the 4th Canadian Conference on Computational Geometry, St. John's, Newfoundland, Canada, pp 223–228

  13. Garey M, Johnson D, Tarjan R (1976) The planar Hamiltonian circuit problem is NP-complete. SIAM J Comput 5:704–714

    Google Scholar 

  14. Gray F (1953) Pulse code communication. United States Patent Number 2:632–058

    Google Scholar 

  15. Hershberger J (1989) An optimal visibility graph algorithm for triangulated simple polygons. Algorithmica 4:141–155

    Google Scholar 

  16. Koenderink J (1989) Solid shape, MIT Press, MA

    Google Scholar 

  17. Narasimhan G (1996) On Hamiltonian triangulations in simple polygons. Unpublished manuscript

  18. O'Rourke J, Supowit KJ (1983) SomeN P-hard polygon decomposition problems. IEEE Trans Inform Theory IT 29:181–190

    Google Scholar 

  19. O'Rourke J, Booth H, Washington R (1987) Connect-thedots: a new heuristic. Comput Vision Graph Image Processing 39:258–266

    Google Scholar 

  20. Prabhu N (1990) Hamiltonian simple polytopes. Technical Report 90-17, DIMACS, Rutgers University, New Brunswick, NJ

    Google Scholar 

  21. Ramaswami S, Ramos P, Toussaint G (1995) Converting triangulations to quadrangulations. Proceedings of the 7th Canadian Conference on Computational Geometry, Québec, QU, Canada, pp 297–302

  22. Savage C (1989) Gray code sequences of partitions. J Algorithms 10:577–595

    Google Scholar 

  23. Seidel R (1993) Backwards analysis of randomized geometric algorithms, Pach J (ed) New trends in discrete and computational geometry, vol 10 of Algorithms and combinatorics. Springer, Berlin Heidelberg New York, pp 37–68

    Google Scholar 

  24. Silicon Graphics (1991) Graphics library programming guide

  25. Tseng LH, Lee DT (1992) Two-guard walkability of simple polygons. Manuscript

  26. Wilf H (1989) Combinatorial algorithms: an update. Society for Industrial and Applied Mathematics. Philadelphia

    Google Scholar 

  27. Yvinec M (1989) Triangulation in 2D and 3D space. Geometry and Robotics Workshop Proceedings, Toulouse, France (Lecture Notes in Computer Science, vol 391). Springer, Berlin Heidelberg New York, pp 275–291

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Applied Mathematics and Statistics, State University of New York, 11794-3600, Stony Brook, NY, USA

    Esther M. Arkin, Martin Held & Joseph S. B. Mitchell

  2. Institut für Computerwissenschaften, Paris-Lodron Universität Salzburg, A-5020, Salzburg, Austria

    Martin Held

  3. Department of Computer Science, State University of New York, 11794-4400, Stony Brook, NY, USA

    Steven S. Skiena

Authors
  1. Esther M. Arkin
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Martin Held
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Joseph S. B. Mitchell
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Steven S. Skiena
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Arkin, E.M., Held, M., Mitchell, J.S.B. et al. Hamiltonian triangulations for fast rendering. The Visual Computer 12, 429–444 (1996). https://doi.org/10.1007/BF01782475

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01782475

Key words

Search

Navigation