1997 · 55 citations · 0 references
ComputingComputer ScienceMathematicsComputational GeometryGeometric ModelingGeometryDelaunay TriangulationsGeometry ProcessingMesh GenerationShape RepresentationTriangulation AlgorithmsTriangulation Data StructuresTriangulations
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) .