Proximity Cluster Trees

Elena Jakubiak Hutchinson and Sarah Frisken
Tufts University Department of Computer Science

Ronald Perry
Mitsubishi Electric Research Laboratories

This paper appears in issue Volume 13, Number 1.
An electronic version of this article is available.

Abstract

Hierarchical spatial data structures provide a means for organizing data for efficient processing. Most spatial data structures are optimized for performing queries, such as intersection and containment testing, on large data sets. Set-up time and complexity of these structures can limit their value for small data sets, an often overlooked yet important category in geometric processing. We present a new hierarchical spatial data structure, dubbed a proximity cluster tree, which is particularly effective on small data sets. Proximity cluster trees are simple to implement, require minimal construction overhead, and are structured for fast distance-based queries. Proximity cluster trees were tested on randomly generated sets of 2D Bézier curves and on a text-rendering application requiring minimum-distance queries to 2D glyph outlines. Although proximity cluster trees were tailored for small data sets, empirical tests show that they also perform well on large data sets.

Author Information

Elena Jakubiak Hutchinson, Tufts University Department of Computer Science, 161 College Avenue, Medford, MA 02155 jakubiak@cs.tufts.edu

Sarah Frisken, Tufts University Department of Computer Science, 161 College Avenue, Medford, MA 02155 frisken@cs.tufts.edu

Ronald Perry, Mitsubishi Electric Research Laboratories, 201 Broadway, Cambridge, MA 02139 perry@merl.com

BibTeX Entry

@article{HutchinsonEtAl08,
  author = "Elena Jakubiak Hutchinson and Sarah Frisken and Ronald Perry",
  title = "Proximity Cluster Trees",
  journal = "journal of graphics, gpu, and game tools",
  volume = "13",
  number = "1",
  pages = "57-69",
  year = "2008",
}