language: en

On Hamiltonian Triangulations in Simple Polygons

Giri NARASIMHAN 1
e-mail: giri@next1.msci.memphis.edu
Dept. of Mathematical Sciences The University of Memphis
Memphis TN 38152

Abstract A simple polygon P is said to have a Hamilitonian Triangulation if it has a triangulation whose dual graph contains a Hamiltonian path. Such triangulations are useful in fast rendering engines in Computer Graphics. Arkin et al. [AHMS] observed that a polygon has a Hamiltonian triangulation if and only if it is Discretely Straight Walkable, a concept that is a discrete version of Straight Walkability concept as introduced by Icking and Klein [IK]. Using this characterization, Arkin et al. also showed an algorithm to recognize such polygons in time that is linear in the size of the visibility polygon of the given polygon P . The size of the visbility polygon of P could be quadratic in the size of P and hence their algorithm could be very inefficient even for nearly convex polygons. We give a new characterization of polygons with Hamiltonian triangulations. We use this characterization to present the following algorithms: * An O(n log n)-time algorithm to recognize polygons with a Hamiltonian triangulation. * An O(n log n)-time algorithm to construct such a triangulation. * Given vertices p and q on a simple polygon, an O(n)-time algorithm to determine whether the polygon is discretely straight walkable with respect to the two vertices. * An O(n log n)-time algorithm to list out all pairs of points on a simple polygon with respect to which the polygon is discretely straight walkable.

[References [IK] C. Icking and R. Klein, "The two guards problem," Proc. 7th Annual ACM Symp. on Computational Geometry, 1991, pp. 166-175.]

[[AHMS] E.M. Arkin, M. Held, J.S.B. Mitchell, S.S. Skienna, "Hamiltonian Triangulations for Fast Rendering," Proc. of the 2nd ESA, 1994.]

[1 Supported in part by NSF Grant CCR-940-9752]