IntroductionAlgorithmAppletBibliography |
The AlgorithmThe algorithm described in [5] builds a Hamiltonian cycle incrementally. It starts by picking two arbitrary adjacent triangles and building a 2-vertex cycle. It then repeatedly grows the current cycle by incorporating an arbitrary triangle adjacent to one of the triangles already in the cycle. The algorithm stops when all the triangles in the given triangulation have been incorporated in the cycle. Thus, a triangle is consumed at each iteration of the procedure and hence the algorithm runs in linear time. Each triangle t in the cycle has a predecessor pred(t) and a successor succ(t). If t shares an edge with a triangle s, then we say t and s are adjacent. If t shares only one vertex with s, then s and t are vertex-adjacent. Let C be the current cycle. If C includes all the triangles in the triangulation, then the procedure is done. Otherwise, pick an arbitrary triangle s that is adjacent along an edge e to a triangle t in C. Include s in C based on the following cases :
CASE 1: t is vertex-adjacent along e to at least one of its neighbors in C. Suppose that t is vertex-adjacent to pred(t). Then insert s before t. Thus, the cycle becomes ... pred(t), s, t, succ(t) ...
CASE 2: t is adjacent to both its neighbors in C. a) If pred(pred(t))
is vertex-adjacent on e to pred(t) and succ(succ(t))
is vertex-adjacent to succ(t). b) Otherwise, insert s before t. Thus, the cycle becomes ... pred(t), s, t, succ(t) ...
CASE 3: t is adjacent to one neighbor and vertex-adjacent through a vertex not incident to e. Suppose t is adjacent to pred(t) and vertex-adjacent to succ(t) a) If pred(pred(t))
is vertex-adjacent on e to pred(t) b) Otherwise, insert s before t. Thus, the cycle becomes ... pred(t), s, t, succ(t) ...
|