Progress on maximum weight triangulation

In this paper, we investigate various properties and problems associated with the maximum weight triangulation of a point set in the plane. We prove that the weight of a maximum weight triangulation of any planar point set with diameter D is bounded above by , where ɛ is any constant and n is the number of points in the set. If we use the so-called spoke-scan algorithm to find a triangulation of the point set, we obtain an approximation ratio of 4.238. Furthermore, if the point set forms a semi-circled convex polygon, then its maximum weight triangulation can be found in O(n2) time.