Relative Neighborhood Graphs and Their Relatives

Jerzy W. Jaromczyk, Godfried T. Toussaint

Research output: Contribution to journalArticlepeer-review


This is a survey of results on neighborhood graphs. The paper discusses properties, bounds on the size, algorithms, and variants of the neighborhood graphs. Numerous applications including computational morphology, spatial analysis, pattern classification, and data bases for computer vision are described. A rich bibliography of the subject concludes the paper.

Original languageEnglish (US)
Pages (from-to)1502-1517
Number of pages16
JournalProceedings of the IEEE
Issue number9
StatePublished - 1992


  • Computational geometry
  • computational morphology
  • geometric graphs
  • neighborhood graphs
  • spatial analysis

ASJC Scopus subject areas

  • General Computer Science
  • Electrical and Electronic Engineering


Dive into the research topics of 'Relative Neighborhood Graphs and Their Relatives'. Together they form a unique fingerprint.

Cite this