Geometric applications of posets |
| |
Authors: | Michael Segal Klara Kedem |
| |
Affiliation: | Department of Mathematics and Computer Science, Ben-Gurion University of the Negev, Beer-Sheva 84105, Israel |
| |
Abstract: | We show the power of posets in computational geometry by solving several problems posed on a set S of n points in the plane: (1) find the n − k − 1 rectilinear farthest neighbors (or, equivalently, k nearest neighbors) to every point of S (extendable to higher dimensions), (2) enumerate the k largest (smallest) rectilinear distances in decreasing (increasing) order among the points of S, (3) given a distance δ > 0, report all the pairs of points that belong to S and are of rectilinear distance δ or more (less), covering k ≥ n/2 points of S by rectilinear (4) and circular (5) concentric rings, and (6) given a number k ≥ n/2 decide whether a query rectangle contains k points or less. |
| |
Keywords: | Algorithms Posets Nearest neighbors Optimization Distances |
本文献已被 ScienceDirect 等数据库收录! |
|