Efficient algorithms for bichromatic separability


Journal Article

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. © 2006 ACM.

Full Text

Duke Authors

Cited Authors

  • Agarwal, PK; Aronov, B; Koltun, V

Published Date

  • August 29, 2006

Published In

Volume / Issue

  • 2 / 2

Start / End Page

  • 209 - 227

Electronic International Standard Serial Number (EISSN)

  • 1549-6333

International Standard Serial Number (ISSN)

  • 1549-6325

Digital Object Identifier (DOI)

  • 10.1145/1150334.1150338

Citation Source

  • Scopus