Abstract: "We present a simple and efficient 0(Nlog2N) time divide-and-conquer algorithm for solving the all pairs angle restricted neighbors problem for a set of N sites in the plane under any L[subscript p] metric, 1 [less than or equal to] p [less than or equal to] [infinity]. Our method also leads to an 0(Nlog[superscript d-1]N) expected time algorithm for the d-dimensional all pairs angle restricted neighbors problem, for d [greater than or equal to] 2."

This algorithm can also be extended to obtain a rectilinear minimum spanning tree for a set of non-intersecting simple polygons."

In this paper, we provide an O(n log n log p) time algorithm for computing the Symmetric angle restricted nearest neighbors (SARNN) in the traditional RAM model of computation. This algorithm is then used to compute a minimum spanning tree in L[subscript p] metric in O(n log n log p) time. Since [Omega](n log n) is a lower bound in the algebraic computation model, this algorithm is optimal (within a muliplicative constant) for any constant p [greater than or equal to] 1. Also, since it does not compute any Voronoi diagram, it seems relatively simple to implement."

Abstract: "In this paper, we explore properties of the geographic nearest neighbors and the Delaunay triangulation, and design an asymptotically optimal O(logn) time O(n) processor parallel algorithm on a CREW-PRAM for constructing the Delaunay triangulation (thus the Voronoi diagram) under the L1 metric."

Abstract: "In this paper, we discuss the relations among some proximity problems that hold upon generalizations of the underlying metrics. Our main result here is an O(N log N) time divide-and-conquer algorithm for computing the Voronoi diagram of a set of N sites in the plane with angle restricted distance functions. This provides an O(N log N) time algorithm for computing the planar geographic nearest neighbor problem with any convex distance functions. Since [Omega](N log N) is a lower bound on time for the geographic nearest neighbor problem, our algorithm is optimal within a multiplicative constant."