Efficient algorithms for bichromatic separability

Pankaj K. Agarwal, Boris Aronov, Vladlen Koltun

    Research output: Contribution to journalArticlepeer-review


    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 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)
    Pages (from-to)209-227
    Number of pages19
    JournalACM Transactions on Algorithms
    Issue number2
    StatePublished - 2006


    • Arrangements
    • Geometric algorithms
    • Separability

    ASJC Scopus subject areas

    • Mathematics (miscellaneous)


    Dive into the research topics of 'Efficient algorithms for bichromatic separability'. Together they form a unique fingerprint.

    Cite this