This paper describes a new method for triangulating a simple n-sided polygon.The algorithm runs in time O(n log s), with s _< n.The quantity s measures the sinuosity of the polygon, that is, the number of times the boundary alternates between complete spirals of opposite orientation.The value of s is in practice a very small constant, even for extremely winding polygons.Our algorithm is the first method whose performance is linear in the number of vertices, up to within a factor that depends only on the shape-complexity of the polygon.Informally, this notion of shape-complexity measures how entangled a polygon is, and is thus highly independent of the number of vertices.A practical advantage of the algorithm is that it does not require sorting or the use of any balanced tree structure.Aside from the notion of sinuosity, we are also able to characterize a large class of polygons for which the algorithm can be proven to run in O(n log log n) time.The algorithm has been implemented, tested, and empirical evidence has confirmed its theoretical claim to efficiency.

The running time of Shellsort, with the number of passes restricted to O(log N), was thought for some time to be Θ(N3/2), due to general results of Pratt. Sedgewick recently gave an O(N4/3) bound, but extensions of his method to provide better bounds seem to require new results on a classical problem in number theory. In this paper, we use a different approach to achieve O(N1+4/√2lgN).