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 language | English (US) |
|---|---|
| Title of host publication | Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms |
| Pages | 675-683 |
| Number of pages | 9 |
| Volume | 15 |
| State | Published - 2004 |
| Event | Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms - New Orleans, LA., United States Duration: Jan 11 2004 → Jan 13 2004 |
Other
| Other | Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms |
|---|---|
| Country/Territory | United States |
| City | New Orleans, LA. |
| Period | 1/11/04 → 1/13/04 |
ASJC Scopus subject areas
- Software
- Discrete Mathematics and Combinatorics
- Safety, Risk, Reliability and Quality
- Chemical Health and Safety