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 language||English (US)|
|Number of pages||19|
|Journal||ACM Transactions on Algorithms|
|State||Published - 2006|
- Geometric algorithms
ASJC Scopus subject areas
- Mathematics (miscellaneous)