A note on relative neighborhood graphs

Jerzy W. Jaromczyk, Miroslaw Kowaluk

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

36 Scopus citations

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 O{n α(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<p<∞, metric space in time O(n2) 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).

Original languageEnglish
Title of host publicationProceedings of the 3rd Annual Symposium on Computational Geometry, SCG 1987
EditorsD. Soule
Pages233-241
Number of pages9
ISBN (Electronic)0897912314, 9780897912310
DOIs
StatePublished - Oct 1 1987
Event3rd Annual Symposium on Computational Geometry, SCG 1987 - Waterloo, Canada
Duration: Jun 8 1987Jun 10 1987

Publication series

NameProceedings of the 3rd Annual Symposium on Computational Geometry, SCG 1987

Conference

Conference3rd Annual Symposium on Computational Geometry, SCG 1987
Country/TerritoryCanada
CityWaterloo
Period6/8/876/10/87

Bibliographical note

Publisher Copyright:
© 1987 ACM.

ASJC Scopus subject areas

  • Geometry and Topology
  • Computational Mathematics

Fingerprint

Dive into the research topics of 'A note on relative neighborhood graphs'. Together they form a unique fingerprint.

Cite this