There are a number of ways to generate the sectors concept ranging from really simple to fairly complex. As LJ mentions, using a simplified concept such as a quad/octree can give you benefits in this area. Say with a quad tree you are simply looking for elements completely contained in a quad area (no overlap with other areas), interactions between one and another quad are completely ignored since there is no overlap. So, say you have 4 objects in quad 1, 4 objects in quad 2 and 4 objects straddling the division. Normally you have (n-1)*n interactions possible without the quad tree, i.e. (12-1)*12=132. With 4 objects in quad one, they have to consider themselves and the straddlers, but we leave the straddlers to check interactions between themselves so the equation is (n-1)*(n-s) where s is the straddler count, n is in quad 1 and the straddlers, or in this case: 7*4=28. The same for the second quad. And finally check the straddlers against each other for (4-1)*4=12. So, the total checks needed is down to 2*28+12=68 checks.

Not a bad reduction for a simple method of regrouping the data. (NOTE: May have messed up the general descriptions, but it should be fairly close to correct I believe.)

More complicated solutions exist and can get better gains. But, as said, they are more complicated. I did a system which sat on top of my sweep and prune implementation which did a very nice job (used for something not directly related to reducing interactions since I already had that in the sweep and prune). But it was a considerable bugger to write and debug. You probably want to stick to the simple suggestions.