How to cover a point set with a V-shape of minimum width

Boris Aronov, Muriel Dulieu

    Research output: Contribution to journalArticlepeer-review


    A balanced V-shape is a polygonal region in the plane contained in the union of two crossing equal-width strips. It is delimited by two pairs of parallel rays that emanate from two points x, y, are contained in the strip boundaries, and are mirror-symmetric with respect to the line xy. The width of a balanced V-shape is the width of the strips. We first present an O( n2logn) time algorithm to compute, given a set of n points P, a minimum-width balanced V-shape covering P. We then describe a PTAS for computing a (1+ε)-approximation of this V-shape in time O((n/ε)logn+(n/ ε3 /2) log2(1/ε)). A much simpler constant-factor approximation algorithm is also described.

    Original languageEnglish (US)
    Pages (from-to)298-309
    Number of pages12
    JournalComputational Geometry: Theory and Applications
    Issue number3
    StatePublished - Apr 2013


    • Approximation algorithm
    • Computational metrology
    • Curve reconstruction
    • Fitting
    • Geometric optimization

    ASJC Scopus subject areas

    • Computer Science Applications
    • Geometry and Topology
    • Control and Optimization
    • Computational Theory and Mathematics
    • Computational Mathematics


    Dive into the research topics of 'How to cover a point set with a V-shape of minimum width'. Together they form a unique fingerprint.

    Cite this