Exact and approximation algorithms for minimum-width cylindrical shells

P. K. Agarwal, B. Aronov, M. Sharir

    Research output: Contribution to journalArticlepeer-review

    Abstract

    Let S be a set of n points in ℝ3. Let ω* be the width (i.e., thickness) of a minimum-width infinite cylindrical shell (the region between two co-axial cylinders) containing S. We first present an O(n5)-time algorithm for computing ω*, which as far as we know is the first nontrivial algorithm for this problem. We then present an O(n2+δ)-time algorithm, for any δ > 0, that computes a cylindrical shell of width at most 56ω* containing S.

    Original languageEnglish (US)
    Pages (from-to)307-320
    Number of pages14
    JournalDiscrete and Computational Geometry
    Volume26
    Issue number3
    DOIs
    StatePublished - Oct 2001

    ASJC Scopus subject areas

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

    Fingerprint Dive into the research topics of 'Exact and approximation algorithms for minimum-width cylindrical shells'. Together they form a unique fingerprint.

    Cite this