Efficient Algorithms for Bichromatic Separability

Pankaj K. Agarwal, Boris Aronov, Vladlen Koltun

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Abstract

    A closed solid body separates one point set from another if it contains the former and the closure of its complement contains the latter. We present a near-linear algorithm for deciding whether two sets of n points in 3-space can be separated by a prism, near-quadratic algorithms for separating by a slab or a wedge, and a near-cubic algorithm for separating by a double-wedge. The latter three algorithms improve the previous best known results by an order of magnitude, while the prism separability algorithm constitutes an improvement of two orders of magnitude.

    Original languageEnglish (US)
    Title of host publicationProceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms
    Pages675-683
    Number of pages9
    Volume15
    StatePublished - 2004
    EventProceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms - New Orleans, LA., United States
    Duration: Jan 11 2004Jan 13 2004

    Other

    OtherProceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms
    CountryUnited States
    CityNew Orleans, LA.
    Period1/11/041/13/04

    ASJC Scopus subject areas

    • Software
    • Discrete Mathematics and Combinatorics
    • Safety, Risk, Reliability and Quality
    • Chemical Health and Safety

    Fingerprint Dive into the research topics of 'Efficient Algorithms for Bichromatic Separability'. Together they form a unique fingerprint.

    Cite this