Computing the relative neighborhood graph in the L1 and L∞ metrics |
| |
| Authors: | Joseph O&#x Rourke |
| |
| Affiliation: | Electrical Engineering Department, The Johns Hopkins University, Baltimore, MD 21218, U.S.A. |
| |
| Abstract: | The Relative Neighborhood Graph (RNG) of a set of nk-dimensional points connects “relatively close” neighbors: two points are connected by an edge if they are at least as close to each other as to any other point. Toussaint recently investigated the properties of the RNG in the Euclidean metric and proposed algorithms for its computation. This note examines one of the open problems listed by Toussaint: the extension of the analysis to non-Euclidean metrics. It is shown that Bentley's range query data structures may be used to improve the speed of the best known RNG algorithm in the L∞ (for k ? 2) and L1 (for k = 2) metrics. |
| |
| Keywords: | Relative neighborhood graph Delaunay triangulation Computational geometry |
| 本文献已被 ScienceDirect 等数据库收录！ |
