I was remembering my previous research wrong.
It's quad-trees and related Z-order based curves that give log(n) search and inserts.
With those, "everything" become log^n.
- Given that, my previous argument concerning log time for triangle/polygon search should stand.
http://en.wikipedia.org/wiki/Quadtree http://en.wikipedia.org/wiki/Z-order_curve