Higher Dimensions
There are no known general point location data structures with linear space and logarithmic query time for dimensions greater than 2. Therefore, we need to sacrifice either query time, or storage space, or restrict ourselves to some less general type of subdivision.
In three-dimensional space, it is possible to answer point location queries in O(log² n) using O(n log n) space. The general idea is to maintain several planar point location data structures, corresponding to the intersection of the subdivision with n parallel planes that contain each subdivision vertex. A naive use of this idea would increase the storage space to O(n²). In the same fashion as in the slab decomposition, the similarity between consecutive data structures can be exploited in order to reduce the storage space to O(n log n), but the query time increases to O(log² n).
In d-dimensional space, point location can be solved by recursively projecting the faces into a (d-1)-dimensional space. While the query time is O(log n), the storage space can be as high as . The high complexity of the d-dimensional data structures led to the study of special types of subdivision.
One important example is the case of arrangements of hyperplanes. An arrangement of n hyperplanes defines O(nd) cells, but point location can be performed in O(log n) time with O(nd) space by using Chazelle's hierarchical cuttings.
Another special type of subdivision is called rectilinear (or orthogonal) subdivision. In a rectilinear subdivision, all edges are parallel to one of the d orthogonal axis. In this case, point location can be answered in O(logd-1 n) time with O(n) space.
Read more about this topic: Point Location
Famous quotes containing the words higher and/or dimensions:
“Slavery can only be abolished by raising the character of the people who compose the nation; and that can be done only by showing them a higher one.”
—Maria Weston Chapman (1806–1885)
“It seems to me that we do not know nearly enough about ourselves; that we do not often enough wonder if our lives, or some events and times in our lives, may not be analogues or metaphors or echoes of evolvements and happenings going on in other people?—or animals?—even forests or oceans or rocks?—in this world of ours or, even, in worlds or dimensions elsewhere.”
—Doris Lessing (b. 1919)