Segment Tree - Generalization For Higher Dimensions

Generalization For Higher Dimensions

The segment tree can be generalized to higher dimension spaces, in the form of multi-level segment trees. In higher dimension versions, the segment tree stores a collection of axis-parallel (hyper-)rectangles, and can retrieve the rectangles that contain a given query point. The structure uses O(nlogd-1n) storage, and answers queries in O(logdn).

The use of fractional cascading lowers the query time bound by a logarithmic factor. The use of the interval tree on the deepest level of associated structures lowers the storage bound with a logarithmic factor.

Read more about this topic:  Segment Tree

Famous quotes containing the words higher and/or dimensions:

    The world stands out on either side
    No wider than the heart is wide;
    Above the world is stretched the sky,—
    No higher than the soul is high.
    Edna St. Vincent Millay (1892–1950)

    I was surprised by Joe’s asking me how far it was to the Moosehorn. He was pretty well acquainted with this stream, but he had noticed that I was curious about distances, and had several maps. He and Indians generally, with whom I have talked, are not able to describe dimensions or distances in our measures with any accuracy. He could tell, perhaps, at what time we should arrive, but not how far it was.
    Henry David Thoreau (1817–1862)