Towards modeling the query processing relevant shape complexity of 2D polygonal spatial objects

The shape complexity of two-dimensional (2D) polygonal spatial objects has implications for how the object can be best represented in a spatial databa se, and for the query-processing performance of that object. Nevertheless f ew useful definitions of query-processing relevant spatial complexity are a vailable, A query-processing oriented shape complexity measure is likely to be different from a fractal measure of shape complexity that focused on co mpression/decompression or a shape complexity measure that would be used fu r pattern recognition, and should give better performance for the analysis of query processing. It could be used to classify spatial objects, cluster spatial objects in multiprocessor database systems. In a recent paper Brink hoff et al. (T. Brinkhoff, H-P. Kriegel, R. Shneider, A. Braun, Measuring t he complexity of spatial objects, Proceedings of the 3rd ACM International Workshop on Advances in Geographic Information Systems, Baltimore, MD, 1995 , pp. 109-117) demonstrated the usefulness of a spatial complexity measure. They did not however, offer much theoretical justification for their choic e of parameters nor for the functional form that they used. In this paper w e present a conceptual framework for discussing the query processing orient ed shape complexity measures for spatial objects. It is hoped that this wil l lead to the development of improved measures of spatial complexity. (C) 2 000 Elsevier Science B.V. All rights reserved.