Encoding a triangulation as a permutation of its point set.

Markus Denny, Christian Sohler

1997 · 55 citations · 0 references

Concepts

Abstract

We present algorithms that given a straight edge triangulation of n points in the plane encode a triangulation as a permutation of the points. A first algorithm, of rather theoretical interest, realizes the encoding and decoding in O(n) time. We also present a more practical algorithm consuming O(n log n) time. As a byproduct of this work we get a new upper bound on the number of triangulations of planar point sets of at most 2 8:2n+O(log n) .