A new asymmetric inclusion region for minimum weight triangulation

摘要

As a global optimization problem, planar minimum weight triangulation problem has attracted extensive research attention. In this paper, a new asymmetric graph called one-sided β-skeleton is introduced. We show that the one-sided circle-disconnected (2~(1/2)β)-skeleton is a subgraph of a minimum weight triangulation. An algorithm for identifying subgraph of minimum weight triangulation using the one-sided (2~(1/2)β)-skeleton is proposed and it runs in O(n~(4/3+e) + min{K logn, n~2 log n}) time, where k is the number of intersected segmented between the complete graph and the greedy triangulation of the point set.