The region approach for computing relative neighbourhood graphs in the \(L_ p\) metric (Q1093374)

The following geometrical proximity concepts are discussed: relative closeness and geographic closeness. Consider a set \(V=\{v_ 1,v_ 2,...,v_ n\}\) of distinct points in a two-dimensional space. The point \(v_ j\) is said to be a relative neighbour of \(v_ i\) if \[ d_ p(v_ i,v_ j)\leq \max \{d_ p(v_ i,v_ k),d_ p(v_ j,v_ k)\}\quad for\quad all\quad v_ k\in V, \] where \(d_ p\) denotes the distance in the \(L_ p\) metric, \(1\leq p\leq \infty\). After dividing the space around the point \(v_ i\) into eight sectors (regions) of equal size, a closest point to \(v_ i\) in some region is called an octant (region, or geographic) neighbour of \(v_ i\). For any \(L_ p\) metric, a relative neighbour of \(v_ i\) is always an octant neighbour in some region at \(v_ i\). This gives a direct method for computing all relative neighbours, i.e. for establishing the relative neighbourhood graph of V. For every point \(v_ i\) of V, first search for the octant neighbours of \(v_ i\) in each region, and then for each octant neighbor \(v_ j\) found ckeck whether the point \(v_ j\) is also relative neighbour of \(v_ i\). In the \(L_ p\) metric, \(1<p<\infty\), the total number of octant neighbours is shown to be \(\theta\) (n) for any set of n points; hence, even a straightforward implementation of the above method runs in \(\theta (n^ 2)\) time. In the \(L_ 1\) and \(L_{\infty}\) metrics the method can be refined to a \(\theta\) (n log n\(+m)\) algorithm, where m is the number of relative neighbours in the output, n-1\(\leq m\leq n(n-1)\). The \(L_ 1\) \((L_{\infty})\) algorithm is optimal within a constant factor.