1987/01/01 by Jerzy W. Jaromczyk, Mirosław Kowaluk · 1 citation
Computer Science · Engineering · Mathematics · #Computational Geometry and Mesh Generation #Computer science #Data Management and Algorithms #Mathematics #Robotics and Sensor-Based Localization
paper · doi:10.1145/41958.41983
openalex publication_date 1987/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
Two new algorithms finding relative neighborhood graph RNG(V) for a set V of n points are presented. The first algorithm solves this problem for input points in (R2,Lp) metric space in time O(n a(n,n)) if the Delaunay triangulation DT(V) is given. This time performance is achieved due to attractive and natural application of FIND-UNION data structure to represent so-called elimination forest of edges in DT(V). The second algorithm solves the relative neighborhood graph problem in (Rd,Lp), 1