Pseudo Triangulation of Point Set Using Polygon Construction

Minimum weight pseudo triangulation is one of the computational geometry problems that has not found distinct algorithm and this is an open problem in computationalgeometry. Recently only one approximation algorithm was presented that its results are close to optimal results. In this paper we propose another algorithm based on construction ofsimple polygons. After running both algorithms, we consider results of each algorithm in various samples, and comparison of both results show efficiency of our algorithm.

کلیدواژه ها:

computational geometry ، minimum weight pseudo triangulation ، polygon