Dual look-up on keys?

[castironpi at gmail.com]

> Actually, there's another data structure I was working on (a year ago
> now) that's tangentially related, so if you guys want me to hold off
> on that one til you or I is satisfied on the company-product map, I
> will!  Otherwise, I'll just post it here and leave it to you.
> (Knowing myself, something tells me I'll try to formulate it later on
> today regardless.  Heh heh heh.  If that's not the most virtuous way
> to ask for help, then I might have inherited from TroubleMaker at some
> point up the line.)

My other question still open, the idea was a collision detector.  But
it's been done.

Ideally, subdivide space varying with objects' positions up to a
tolerance.  On motion, redivide.  Each tile, hexes, triangles, or
squares, can access the other objects in itself-- and only detect
collisions among those.  Objects can span multiple tiles.  For large
object sets, zero detections made per cycle best case, but still all
of them worst.  It amounts to a tree structure in which child nodes
are keyed geometrically-- grid.NWcorner.NEcorner gets you the second
column, first row in a 4x4 grid.  grid.NWcorner.NEcorner.SWcorner gets
you the third column, second row, in an 8x8 grid, and by that point,
there are 63 tiles other objects might be in that you know aren't in
yours.  A tile is a leaf if there are no objects in it.

Question is, how rare/common is the subset of object configurations in
which the optimizations weigh out?