ISSN:
1432-2315
Keywords:
Triangulations
;
Hamiltonian paths
;
Quadrangulation
;
Rendering
;
Computer graphics
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01782475
Permalink
