5

One can think about skip quadtree as a skip-list implementation of a data-structure storing the points according to their z-order. It is (arguably) at least conceptually simpler... See chapter 2 here: http://goo.gl/pLiEO . And yes, assuming you can perform some basic z-order operations in constant time, you can definitely do ANN in logarithmic time. The ...


2

This can be reduced to rectangular RMQ in $O(n^2)$ time and space. Create a new array $H$ where $H[i][i+j] := G[i][j]$, padding entries $H[i][k]$ with $k < i$ or $k \ge i + n$ with $\infty$. Run $RMQ(a, b, c, d)$ on $H$ whenever you would run $RMQ_P(a, b, c, d)$ on $G$. Now run your favorite 2D-RMQ algorithm such as this. Perhaps you want to be very ...


2

In some of these bounds, the $\varepsilon$ doesn't come from an approximation, but rather from the degree to which you recurse in a partition tree. Roughly speaking, the idea goes like this. Find a small sample of the input objects that form an arrangement so that the remaining objects are "spread out nicely". In particular, each cell of the arrangement is ...


Only top voted, non community-wiki answers of a minimum length are eligible