On Sequential Triangulations of Simple Polygons
Robin Y. Flatland · 2004
Abstract A triangulation is said to be Hamiltonian if its dualgraph contains a Hamiltonian path. A sequential triangulation is a Hamiltonian triangulation having the ad-ditional property that the "turns " in the Hamiltonian path alternate left/right. Such triangulations are usefulin computer graphics rendering and are related to a new type of two-guard walk. In this paper we present a sim-ple O(n log n) algorithm that determines all sequentialtriangulations (or equivalently all sequential two-guard walks) of a simple n vertex input polygon. The previousbest algorithm uses the polygon's visibility graph and hence runs in worse case O(n2) time [1].