Computing A Minimum Weight Triangulation Of A Spare Point Set

Abstract

Investigating the minimum weight triangulation of a point set with constraint is an important approach for seeking the ultimate solution of the minimum weight triangulation problem. In this paper, we consider the minimum weight triangulation of a spare point set, and present an O(n4) algorithm to computing a triangulation of such a set . The property of spare point set can be converted into a new sufficient condition for finding subgraphs of minimum weight triangulation. Special point set is exhibited to show that our new subgraph of minimum weight triangulation cannot be found by any currently known methods.