Dot Pattern Processing Using Voronoi Neighborhoods

Research output: Contribution to journalArticlepeer-review


A sound notion of the neighborhood of a point is essential for analyzing dot patterns. The past work in this direction has concentrated on identifying pairs of points that are neighbors. Examples of such methods include those based on a fixed radius, k-nearest neighbors, minimal spanning tree, relative neighborhood graph, and the Gabriel graph. This correspondence considers the use of the region enclosed by a point's Voronoi polygon as its neighborhood. It is argued that the Voronoi polygons possess intuitively appealing characteristics, as would be expected from the neighborhood of a point. Geometrical characteristics of the Voronoi neighborhood are used as features in dot pattern processing. Procedures for segmentation, matching, and perceptual border extraction using the Voronoi neighborhood are outlined. Extensions of the Voronoi definition to other domains are discussed.

Original languageEnglish (US)
Pages (from-to)336-343
Number of pages8
JournalIEEE transactions on pattern analysis and machine intelligence
Issue number3
StatePublished - May 1982


  • Clustering
  • Gabriel graph
  • Voronoi tessellation
  • computational complexity
  • dot patterns
  • k-nearest neighbors
  • matching
  • minimal spanning tree
  • neighborhood
  • neighbors
  • perceptual boundary extraction
  • relative neighborhood graph

ASJC Scopus subject areas

  • Software
  • Computer Vision and Pattern Recognition
  • Computational Theory and Mathematics
  • Artificial Intelligence
  • Applied Mathematics


Dive into the research topics of 'Dot Pattern Processing Using Voronoi Neighborhoods'. Together they form a unique fingerprint.

Cite this