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

Boris Aronov, John Iacono, Özgür Özkan, Mark Yagnatinsky

    Research output: Contribution to conferencePaperpeer-review

    Abstract

    A V-shape is an infinite polygonal region bounded by two pairs of parallel rays emanating from two vertices (see Figure 1). We describe a randomized algorithm that, given n points and an integer k ≥ 0, finds the minimum-width V-shape enclosing all but k of the points with probability 1 - 1/nc for any c > 0, with expected running time O(cn2(k + 1)4 log n(log n log log n + k)).

    Original languageEnglish (US)
    Pages211-215
    Number of pages5
    StatePublished - 2013
    Event25th Canadian Conference on Computational Geometry, CCCG 2013 - Waterloo, Canada
    Duration: Aug 8 2013Aug 10 2013

    Other

    Other25th Canadian Conference on Computational Geometry, CCCG 2013
    CountryCanada
    CityWaterloo
    Period8/8/138/10/13

    ASJC Scopus subject areas

    • Geometry and Topology
    • Computational Mathematics

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

    Cite this