I'm working on an algorithm for which I would like to cover an $n$-dimensional unit cube by a set of $n$-cuboids (i.e., $n$-dimensional rectangles). The size and orientation of these cuboids is determined solely by the position of their centrepoint -- so given a point in the cube, one has a set of coordinate axies based at that point, a set $a_1,\ldots,a_n$ of positive numbers, and the cuboid for that point is $-a_1 \leq x_1 \leq a_1,\ldots,-a_n \leq x_n \leq a_n$ with respect to these coordinate axes. The cuboids may overlap, but I'd like the overlap to be small if possible (for reasons off efficiency). The unit cube must be contained in the union of the cuboids. The dimenison $n$ is small and odd, say $n=3,5,\ldots,11$. Any idea about how one could construct such a covering? Computational cost is a minor issue here, a solution needing serious resources is acceptable (probably inevitable).

Motivation: This problem comes from a subdivide-and-reject method for a global optimisation problem with a non-convex objective. I have a bound on a quantity of interest whose domain of validity is an $n$-ellipsoid at each point, but the shape and orientation of the ellipsoid varies over the cube. The idea would be to put a cuboid inside the ellipsoid (so the bound is valid across it), this cube might then be rejected or subdivided uniformly, the subdivided cuboids would then have an a smaller covering ellipsoid, an improved bound, and so on. This is the reason that the cuboids must cover the cube, so that the union of these bounds covers the entire cube.

A key point is that the anisotropy is "localy almost constant", once we get to a small enough size, the ellipsoids covering the cuboids are practically the same shape as the ones covering the subdivided cuboids. One could express this in terms of a bound away from zero of the Jacobian of the anisotropy tensor or such-like, suffice it to say that the anisotropy is "well behaved".

  • $\begingroup$ Is this a one-time construction, or will you need to continually refine/modify it? Also, is there any constraint on how the cuboids meet at their edges/vertices (does the whole thing have to be rectangular grid (separable into 1D partitions), or can it be arbitrary)? $\endgroup$ – Victor Liu Jun 4 '12 at 4:03
  • $\begingroup$ @Victor Liu - This is one-time, or rather, I will need exactly $n$ of these for each $n$. No requirement on edge/vertices, overlap of cuboids is fine but I'd like it small if possible since it corresponds to re-searching the same part of the search space. $\endgroup$ – n00b Jun 4 '12 at 8:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.