Voronoi diagrams, Delaunay triangulations, and vertical decompositions in the plane are structures that are canonically defined for a set of n points or line segments. Construction requires O(n log n) time in the worst case. We show that an order exists in each case such that construction takes only linear time. The order can be determined in linear time from the Voronoi diagram, Delaunay triangulation, or vertical decomposition. This result has applications in compression and decompression of data, and as a consequence transmission overhead can be reduced. The method is simple and our implementation can be seen at http: /liruu. cs .ubc. ca/spiderlsnoey ink/terrain/Demo .html