Quick links

An O(n log log n)-Time Algorithm for Triangulating Simple Polygons

Report ID:
TR-052-86
Date:
June 1986
Pages:
63
Download Formats:
[PDF]

Abstract:

Given a simple n-vertex polygon, the triangulation problem is to partition the interior of the polygon into n - 2 triangles by adding n - 3 nonintersecting diagonals. We propose an O(n log log n)-time algorithm for this problem, improving on the previously best bound of O(n log n) and showing that triangulation is not as hard as sorting. Improved algorithms for several other computational geometry problems follow from our result.

Follow us: Facebook Twitter Linkedin