| In GIS systems, the overlay operation takes two map layers as input, and locates all the intersecting pairs of objects. This is typically done as a prelude to some computation carried out on each pair. For example, one map layer might show regions defined by crime rates. Another might show regions defined by income level. An overlay of these two layers could be used to see the correlation of crime rates with income level. If one layer contains N objects and the other contains M objects, then the brute-force algorithm would have to consider all M x N pairs. After creating Geophile indexes, the overlay would take O(M + N) time, (and efficient searches on each layer would also be possible). While overlay is most commonly applied in 2-dimensional spaces, the Geophile algorithm is general, and can be applied to spaces of any dimensionality. |