A method for evaluating a spatial query comprises receiving a spatial query defining a query window including a void, identifying an interior circle for the query window, wherein the interior circle includes a void, and processing the spatial query by either (1) modifying the at least one interior circle to exclude the void, and using the modified interior circle to evaluate the spatial query by checking whether a data MBR is inside the modified interior circle and when it does, including the data item in the query result set, or (2) by checking whether a data MBR is inside the interior circle and when it does, checking whether the data MBR intersects the MBRs of any of the voids, and including the data item in the query result set when there is no intersection.