Ludwig-Maximilians-Universität München, Institut für Informatik
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.
Bei Problemen, Vorschlägen schicken Sie bitte eine eMail an
wwwmaster@informatik.uni-muenchen.de.
For problems and suggestions send an email message to
wwwmaster@informatik.uni-muenchen.de.
Robert Stabl (13.03.1995)