A linear time algorithm for max-min length triangulation of a convex polygon

摘要

We consider the following planar max-min length triangulation problem: given a set of n points in the Euclidean plane, find a triangulation such that the length of the shortest edge in the triangulation is maximized. In this paper, a linear time algorithm is proposed for computing the max-min length triangulation of a set of points in convex position. In addition, an O(n log n) time algorithm is proposed for computing the max-min length k-set triangulation of a set of points in convex position, where we are to compute a set of k vertices such that the max-min length triangulation on them is minimized over all possible k-set. We further show that the graph version of max-min length triangulation is NP-complete, and some common heuristics such as greedy algorithm are in general not able to give a bounded-ratio approximation to the max-min length triangulation.