The Minimum Weight Triangulation Problem with Few Inner Points

摘要: We propose to look at the computational complexity of 2-dimensional geometric optimization problems on a finite point set with respect number inner points (that is, in interior convex hull). As case study, we consider minimum weight triangulation problem. Finding for n plane is not known be NP-hard nor solvable polynomial time, but when are position, problem can solved O(n 3) time by dynamic programming. extend programming approach general and describe an exact algorithm which runs O(6 k 5log n) where total input points. If taken as parameter, this fixed-parameter algorithm. It also shows that if k=O(log n). In fact, works only polygons, simple polygons