Abstract.
Let P be a polyhedral subdivision in R 3 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 \(2^{- \lceil \log_2 n + 2 \rceil}\) . 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 4 ) vertices in the worst case, and can be computed in the same time.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Additional information
Received September 3, 1997, and in revised form March 29, 1999.
Rights and permissions
About this article
Cite this article
Fortune, S. Vertex-Rounding a Three-Dimensional Polyhedral Subdivision. Discrete Comput Geom 22, 593–618 (1999). https://doi.org/10.1007/PL00009480
Issue Date:
DOI: https://doi.org/10.1007/PL00009480