Proximity structures in the fixed orientation metrics
Christian Wulff‐Nilsen · 2006
We present algorithms computing two types of proximity structures in the plane with a fixed orientation metric. Proximity structures have proven useful for Steiner tree heuristics in the Euclidean plane and may play a similar role for the fixed orientation metrics where Steiner trees are important in the area of VLSI design. We show how to find an all nearest neighbour graph NNG(Z) of a set Z of n points in O(anlogn) time using O(n) space where a is the number of fixed orientations. The algorithm does not use the Voronoi diagram of Z. We present an algorithm that computes the Gabriel graph GG(Z) of Z in O(anlogn) time using O(an) space under the assumption that no three points of Z are on a line parallel to one of the