Vertical decompositions for triangles in 3-space

M. Berg, de, L.J. Guibas, D. Halperin

    Research output: Contribution to journalArticleAcademicpeer-review

    35 Citations (Scopus)


    We prove that, for any constant ¿>0, the complexity of the vertical decomposition of a set ofn triangles in three-dimensional space isO(n 2+¿ +K), whereK is the complexity of the arrangement of the triangles. For a single cell the complexity of the vertical decomposition is shown to beO(n 2+¿ ). These bounds are almost tight in the worst case. We also give a deterministic output-sensitive algorithm for computing the vertical decomposition that runs inO(n 2 logn+V logn) time, whereV is the complexity of the decomposition. The algorithm is reasonably simple (in particular, it tries to perform as much of the computation in two-dimensional spaces as possible) and thus is a good candidate for efficient implementations. The algorithm is extended to compute the vertical decomposition of arrangements ofn algebraic surface patches of constant maximum degree in three-dimensional space in timeO(n¿ q (n) logn +V logn), whereV is the combinatorial complexity of the vertical decomposition, ¿ q (n) is a near-linear function related to Davenport-Schinzel sequences, andq is a constant that depends on the degree of the surface patches and their boundaries. We also present an algorithm with improved running time for the case of triangles which is, however, more complicated than the first algorithm.
    Original languageEnglish
    Pages (from-to)35-61
    Number of pages27
    JournalDiscrete and Computational Geometry
    Issue number1
    Publication statusPublished - 1996


    Dive into the research topics of 'Vertical decompositions for triangles in 3-space'. Together they form a unique fingerprint.

    Cite this