In this paper we give an algorithm to generate all biconnected plane triangulations having exactly n vertices including exactly r vertices on the outer face. The algorithm uses O(n) space in total and generates such triangulations without duplications in O(rn) time per triangulation, while the previous best algorithm generates such triangulations in O(r2n) time per triangulation.
Swipe to navigate through the chapters of this book
- More Efficient Generation of Plane Triangulations
- Springer Berlin Heidelberg
- Sequence number
Neuer Inhalt/© ITandMEDIA