1992 | ReviewPaper | Buchkapitel
Monotonous Bisector* Trees — a tool for efficient partitioning of complex scenes of geometric objects
verfasst von : H. Noltemeier, K. Verbarg, C. Zirkelbach
Erschienen in: Data structures and efficient algorithms
Verlag: Springer Berlin Heidelberg
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 Monotonous Bisector Tree, which can be regarded as a divisive hierarchical approach of centralized clustering methods (compare [3] and [12]). We analyze some structural properties showing that Monotonous Bisector 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 Monotonous Bisector Tree with logarithmic height can be constructed in optimal 0(n log n) time using 0(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 Monotonous Bisector Trees support a large variety of proximity queries by a single data structure efficiently.