Creating exhaustive spatial region in design space

I am working with high-dimensional input data of the order of 20, and having nearly 4000 sample points. The response dimension is 1. I want to create spatial regions in my domain space but it should be exhaustive and non-overlapping. Delaunay triangulations look like a perfect solution but its just not possible to construct them in high-dimensions due to storage issues. I thought of constructing large grids too but again, even if I have 2 bins per dimension, I end up with 2^20 grids for 20-dimensional data. Is there any alternative to address this curse of dimensionality so that I can obtain regions computationally efficiently. In the worst case, I may even consider overlapping geometries, and/or non-exhaustive design.

By exhaustive, I mean each sample point is part of some geometrical region.