Vertex-Rounding a Three-Dimensional Polyhedral Subdivision

Let P be a polyhedral subdivision in R ³ with a total of n faces. We show that there is an embedding σ of the vertices, edges, and facets of P into a subdivision Q , where every vertex coordinate of Q is an integral multiple of . For each face f of P , the Hausdorff distance in the L _∈fty metric between f and σ(f) is at most 3/2 . The embedding σ preserves or collapses vertical order on faces of P . The subdivision Q has O(n ⁴ ) vertices in the worst case, and can be computed in the same time. Received September 3, 1997, and in revised form March 29, 1999.