Technical Report 94-06

TITLE:

A Measure for the Complexity of Polygonal Objects

DATE:

March 1994

AUTHORS:

Thomas Brinkhoff <brink@informatik.uni-muenchen.de>

Hans-Peter Kriegel <kriegel@informatik.uni-muenchen.de>

Ralf Schneider <ralf@dbs.informatik.uni-muenchen.de>

Alexander Braun

Institut für Informatik

Universität München

Leopoldstr. 11B

D-80802 München (Germany)

KEYWORDS:

spatial database systems, complexity of objects, fractal dimension, run-time complecity, point-in-polygon test, benchmark

ABSTRACT:

Polygonal objects are characterized by the following well-known parameters: number of vertices, area, perimeter and so on. These parameters describe the data sets that are used in benchmarks and experimental as well as analytical performance comparisons of data structures and algorithms in the area of spatial database systems. Also, a spatial query optimizer should be based on a cost model depending on these parameters. The scope of this paper is to demonstrate the importance and usefulness of or a new and more general parameter, the so called complexity parameter. Obviously, complexity is an intuitive term. Therefore, we have to ask: What does "complex" mean? Starting with a basic set of parameters describing a polygon and a set of intuitive lingual properties, we develop a complexity model consisting of three quantitative parameters. In a further step, these parameters are condensed into one measure of complexity. Using real cartographical maps, we document the suitability of our complexity parameter by three applications. 1. It distinguishes a wider range of more and less complex objects and is more intuitive than the fractal dimension. 2. The cost for answering the point-in-polygon test depends on the degree of complexity and not on the number of vertices of a polygon when the TR*-tree is used as a spatial data structure. 3. Using our complexity parameter, we detected special features in the data sets of the SEQUOIA 2000 storage benchmark.