Math @ Duke

Publications [#235485] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Aronov, B; Koltun, V, Efficient algorithms for bichromatic separability,
Acm Transactions on Algorithms, vol. 2 no. 2
(2006),
pp. 209227, ISSN 15496325 [doi]
(last updated on 2018/10/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 ℝ 3 can be separated by a prism, nearquadratic algorithms for separating by a slab or a wedge, and a nearcubic 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.


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

