Approximating minimum-weight triangulations in three dimensions

B. Aronov, S. Fortune

    Research output: Contribution to journalArticlepeer-review


    Let S be a set of noncrossing triangular obstacles in ℝ3 with convex hull H. A triangulation Script T sign of H is compatible with S if every triangle of S is the union of a subset of the faces of Script T sign. The weight of Script T sign is the sum of the areas of the triangles of Script T sign. We give a polynomial-time algorithm that computes a triangulation compatible with S whose weight is at most a constant times the weight of any compatible triangulation. One motivation for studying minimum-weight triangulations is a connection with ray shooting. A particularly simple way to answer a ray-shooting query ("Report the first obstacle hit by a query ray") is to walk through a triangulation along the ray, stopping at the first obstacle. Under a reasonably natural distribution of query rays, the average cost of a ray-shooting query is proportional to triangulation weight. A similar connection exists for line-stabbing queries ("Report all obstacles hit by a query line").

    Original languageEnglish (US)
    Pages (from-to)527-549
    Number of pages23
    JournalDiscrete and Computational Geometry
    Issue number4
    StatePublished - Jun 1999

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Geometry and Topology
    • Discrete Mathematics and Combinatorics
    • Computational Theory and Mathematics


    Dive into the research topics of 'Approximating minimum-weight triangulations in three dimensions'. Together they form a unique fingerprint.

    Cite this