A note on relative neighborhood graphs

1 January 1987

proceedings article
Published by Association for Computing Machinery (ACM)

p. 233-241
https://doi.org/10.1145/41958.41983

Abstract

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 &Ogr;(n &agr;(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 2) when no three points in V form an isosceles triangle. The complexity analysis of this algorithm is based on some general facts pertaining to properties of equilateral triangles in the metric space (Rd,Lp).

Keywords

SET V
FIND-UNION DATA STRUCTURE
N POINT
METRIC SPACE
TIME PERFORMANCE
RELATIVE NEIGHBORHOOD GRAPH PROBLEM
V FORM
NEW ALGORITHM
DELAUNAY TRIANGULATION DT
RELATIVE NEIGHBORHOOD GRAPH
DATA STRUCTURE
DELAUNAY TRIANGULATION

This publication has 0 references indexed in Scilit: