This paper consider the problem: Given two points u and v in a simple polygon P, divide P into three parts, locus of points closer to u, that closer to v, and that equidistant from u and v. An O(n2)-time algorithm is presented where n is the number of vertices of the simple polygon.
Tetsuo ASANO Takao ASANO Yoshikazu OHSUGA
We present a simple approximation algorithm for a problem of partitioning a polygonal region into a minimum number of triangles. The objective is to show that the absolute performance ratio of the algorithm is bounded by some constant for any polygonal region.