Math @ Duke

Publications [#235455] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Aronov, B; Koltun, V, Efficient Algorithms for Bichromatic Separability,
Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms, vol. 15
(2004),
pp. 675683
(last updated on 2018/03/22)
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 nearlinear algorithm for deciding whether two sets of n points in 3space can be separated by a prism, nearquadratic algorithms for separating by a slab or a wedge, and a nearcubic algorithm for separating by a doublewedge. 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.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

