Linear and Almost Linear Triangulation Algorithms for Simple Polygons

摘要

Asymptotically linear and almost linear (in terms of computational complexity) triangulation algorithms for simple polygons, simple polygon generation techniques, and computational problems arising in the implementation of algorithms are considered. Software implementations of some algorithms are compared and recommendations for their application are given.