A linear time algorithm for max-min length triangulation of a convex polygon |
| |
Authors: | Shiyan Hu |
| |
Affiliation: | Department of Computer and Information Science, Polytechnic University, Brooklyn, NY 11201, USA |
| |
Abstract: | 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(nlogn) 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. |
| |
Keywords: | Computational geometry Max-min length triangulation Max-min length k-set triangulation |
本文献已被 ScienceDirect 等数据库收录! |
|