Fast computation of spatial queries in location-based services

A method comprising:

• forming a representation of locations of a plurality of geographical regions disaggregated into atomic components;
• preparing a response to a spatial query involving determination of whether a point location intersects one of said geographical regions;
• and
• preparing a response to said spatial query involving determination of whether any of said geographical regions intersect.

An apparatus comprising:

• means for preparing a representation of a region in anticipation of a query related to a metric space, said representation being used in forming a response to said query;
• means for obtaining a mathematical format of a region within said metric space;
• means for disaggregating said region into a set of atomic shapes;
• and
• means for forming the representation of said region by preprocessing and storing at least one property for at least one of said atomic shapes.