Finding sets covering point with application to mesh-free galerkin methods

For a collection of sets in R-d we consider the task of finding all sets in the collection that cover or contain a given point. The algorithms introduced in this paper are based on quadtrees and their generalizations to R-d. The advantages of our new splitting algorithm to nd the covering sets of a point over the basic algorithm are detailed by means of hit rates and the expected depth traversed in the quadtree search, numerically and theoretically. This solves a difficult problem faced by mesh-free discretizations of partial differential equations.