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

Math @ Duke



Publications [#235485] of Pankaj K. Agarwal

Papers Published

  1. Agarwal, PK; Aronov, B; Koltun, V, Efficient algorithms for bichromatic separability, ACM Transactions on Algorithms, vol. 2 no. 2 (2006), pp. 209-227, ISSN 1549-6325 [doi]
    (last updated on 2018/07/21)

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

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