Geometric applications of posets

We show the power of posets in computational geometry by solving several pr oblems posed on a set S of n points in the plane: (1) find the n - k - 1 re ctilinear farthest neighbors (or, equivalently, k nearest neighbors) to eve ry point of S (extendable to higher dimensions), (2) enumerate the k larges t (smallest) rectilinear distances ill decreasing (increasing) order among the points of S, (3) given a distance delta > 0, report all the pairs of po ints that belong to S and are of rectilinear distance delta or more (less), covering k greater than or equal to n/2 points of S by rectilinear (4) and circular (5) concentric rings, and (6) given a number k greater than or eq ual to n/2 decide whether a query rectangle contains k points or less. (C) 1998 Elsevier Science B.V. All rights reserved.