![Sample our Computer Science journals, sign in here to start your access, latest two full volumes FREE to you for 14 days]({"type":"image" , "src" : "/sda/5928/TOC-Subject-Sample-2021-Computer-Science.jpg"})
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.