more adaptive spatial binning

Thank you for the responses. After some more research, I have come to conclude that quadtrees or "Centroidal Voronoi Tessellations" (CVT) would be most appropriate for my problem of adaptive spatial binning. Does anyone know about software implementation of either one of those; an R package would be heaven sent of course.

Thanks again,
Markus