Given a d-dimensional set of n points, the number of combinatorially different minimum spanning trees that can be formed by adding one more point is within a polylogarithmic factor of nd.
We use quadtrees to handle point location queries in an amount of time that depends on the distance of the query point to the nearest region boundary.
Co-authors – Publications – David Eppstein – Theory Group – Inf. & Comp. Sci. – UC Irvine
Semi-automatically filtered from a common source file.