This thesis addresses the problem of triangulating simple polygons, one of the fundamental problems in computational geometry. First, the basic concepts are introduced, providing the theoretical foundation for understanding the topic. A review of triangulation algorithms then follows, ranging from the slowest to the practically fastest methods: the naive algorithm, the ear-clipping method, monotone triangulation by sweeping, the Kirkpatrick–Klawe–Tarjan algorithm, and Seidel’s algorithm. The main chapter is devoted to summarizing Chazelle’s algorithm, which is theoretically optimal and represents an important milestone in the study of efficient polygon triangulation.
|
