A simple linear-time algorithm for computing the ring and MST of unimodal polygons (Q1120279)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: A simple linear-time algorithm for computing the ring and MST of unimodal polygons |
scientific article; zbMATH DE number 4100606
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A simple linear-time algorithm for computing the ring and MST of unimodal polygons |
scientific article; zbMATH DE number 4100606 |
Statements
A simple linear-time algorithm for computing the ring and MST of unimodal polygons (English)
0 references
1989
0 references
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.
0 references
computational geometry
0 references
algorithms
0 references
unimodal polygons
0 references
