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

Math @ Duke



Publications [#235567] of Pankaj K. Agarwal

Papers Published

  1. Agarwal, PK; Matoušek, J, Relative neighborhood graphs in three dimensions, Computational Geometry, vol. 2 no. 1 (1992), pp. 1-14, ISSN 0925-7721
    (last updated on 2018/12/16)

    The relative neighborhood graph (RNG) of a set S of n points in Rd is a graph (S, E), where (p, q)∈E if and only if there is no point z∈S such that max{d(p, z), d(q, z)}<d(p, q). We show that in R3, RNG(S) has O(n 4 3) edges. We present a randomized algorithm that constructs RNG(S) in expected time O(n 3 2+ε) assuming that the points of S are in general position. If the points of S are arbitrary, the expected running time is O(n 7 4+ε). These algorithms can be made deterministic without affecting their asymptotic running time. © 1992.
ph: 919.660.2800
fax: 919.660.2821

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