Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke



Publications [#235455] of Pankaj K. Agarwal

Papers Published

  1. Agarwal, PK; Aronov, B; Koltun, V, Efficient Algorithms for Bichromatic Separability, Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, vol. 15 (2004), pp. 675-683
    (last updated on 2018/10/14)

    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.
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320