Triangles in space or building (and analyzing) castles in the air

B. Aronov, M. Sharir

    Research output: Contribution to journalArticle

    Abstract

    We show that the total combinatorial complexity of all non-convex cells in an arrangement of n (possibly intersecting) triangles in 3-space is O(n7/3 log n) and that this bound is almost tight in the worst case. Our bound significantly improves a previous nearly cubic bound of Pach and Sharir. We also present a (nearly) worst-case optimal randomized algorithm for calculating a single cell of the arrangement and an alternative less efficient, but still subcubic algorithm for calculating all non-convex cells, analyze some special cases of the problem where improved bounds (and faster algorithms) can be obtained, and describe applications of our results to translational motion planning for polyhedra in 3-space.

    Original languageEnglish (US)
    Pages (from-to)137-173
    Number of pages37
    JournalCombinatorica
    Volume10
    Issue number2
    DOIs
    StatePublished - Jun 1990

    Keywords

    • AMS subject classification (1980): 51-04, 52A37, 68R05

    ASJC Scopus subject areas

    • Discrete Mathematics and Combinatorics
    • Computational Mathematics

    Fingerprint Dive into the research topics of 'Triangles in space or building (and analyzing) castles in the air'. Together they form a unique fingerprint.

  • Cite this