Efficient Algorithms for Bichromatic Separability

Published

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-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.

Duke Authors

Cited Authors

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

Published Date

  • April 15, 2004

Published In

  • Proceedings of the Annual Acm Siam Symposium on Discrete Algorithms

Volume / Issue

  • 15 /

Start / End Page

  • 675 - 683

Citation Source

  • Scopus