A simple linear-time algorithm for computing the ring and MST of unimodal polygons (Q1120279)

Very simple linear-time algorithms for computing the Euclidean minimum spanning tree and the relative neighborhood graph of (the set of vertices of) unimodal polygons are presented. The algorithms are better than the corresponding known algorithms for convex polygons. They demonstrate once again, that the key factor for obtaining very efficient algorithms for many problems is not convexity, but rather unimodality.