1993 | OriginalPaper | Buchkapitel
A Data Structure for Representing and Efficient Querying Large Scenes of Geometric Objects: MB* Trees
verfasst von : Prof. Dr. H. Noltemeier, K. Verbarg, C. Zirkelbach
Erschienen in: Geometric Modelling
Verlag: Springer Vienna
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We are concerned with the problem of partitioning complex scenes of geometric objects in order to support the solutions of proximity problems in general metric spaces with an efficiently computable distance function. We present a data structure called Monotone Bisector* Tree (MB* Tree), which can be regarded as a divisive hierarchical approach of centralized clustering methods (compare [3] and [10]). We analyze some structural properties showing that MB* Trees are a proper tool for a general representation of proximity information in complex scenes of geometric objects.Given a scene of n objects in d-dimensional space and some Minkowski-metric. We additionally demand a general position of the objects and that the distance between a point and an object of the scene can be computed in constant time. We show that a MB* Tree with logarithmic height can be constructed in optimal O(n log n) time using O(n) space. This statement still holds if we demand that the cluster radii, which appear on a path from the root down to a leaf, should generate a geometrically decreasing sequence.We report on extensive experimental results which show that MB* Trees support a large variety of proximity queries by a single data structure efficiently.