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:
“Three factors—the belief that child care is female work, the failure of ex-husbands to support their children, and higher male wages at work—have taken the economic rug from under that half of married women who divorce.”
—Arlie Hochschild (20th century)
“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)