Antoni Moore, Department of Information Science

Title: "The Use of the Circle Tree for the Efficient Storage of Polygons"

The circle tree has been proposed as a novel hierarchical spatial data structure, promising optimised storage, access, and multiscale representation. The theory behind the circle tree draws from the fields of 3D computer graphics, spatial database indexing and cartography. The testing of the storage aspects will be reported on in this paper. The theory behind the circle tree is that the conventional storage of polygonal data in terms of a series of xy points can be efficiently replaced by an array of variably-sized circles, alternatively filling the polygon in a recursive manner to near-maximal effect, or being used in a non-space filling sense to approximate to the polygon boundary. The latter case is considered in this paper.

The major question is: can a set of circles capture the outline of a polygon to an acceptable accuracy level and still form a smaller dataset than the original polygon data? Two sub-issues are discussed and can be summarised by the following questions: Should overlapping circles be allowed and if so what degree of overlap produces the best results? Does the introduction of external circles result in significant storage savings? It was found that with a medial axis approach there was a payoff between overlap and accuracy (less overlap meant less accuracy though efficient storage), and external circles were also found to optimise the polygon line. However, the accurate reconstruction of the polygon from circles was an issue, alleviated to some extent by introducing a subset of zero-radius circles, "important" points derived from applying the Douglas-Peucker line reduction algorithm to the polygon.