Re: Point location in a grid.

On Thursday 15 February 2007 23:51, Amit Bhatia wrote:
... I have a square grid composed
of hyper cubes, in d dimensions. I would like to find to which particular
hypercube does a general point belong to.
I can use hierarchical data structure like quad tree and that would give
me
the answer in (l*2^d) time: where l is the resolution (depth) at which I
am looking at, and d is the dimension of the space.

But I am wondering if there is a faster way: something that gives quick
answer most of the time, or gives correct answer quickly most of the
time..

A great survey of deterministic methods is
Volker Gaede and Oliver Günther, Multidimensional Access Methods, ACM
Computing Surveys, 30(2):170-231, June 1998.

-paul-
--
Paul E. Black (p.black@xxxxxxx)
.