In computational geometry, polygon triangulation is the partition of a simple polygon into a set of triangles, meaning a set of triangles with pairwise non-intersecting interiors whose union is the original polygon. Triangulations can be viewed as special cases of planar straight-line graphs, and when there are no holes or added points they form maximal outerplanar graphs.
Facts
Time Complexity
Time Complexity (category)Linearithmic Time -- O(n log n) 1 Classification
Design Technique Connections
Sources
1. Polygon triangulation (Wikipedia)
Wikipedia article body, read for Browse By backfill (w-bbfill-computing6-0927)
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.