0

I have a question similar to this one ( Find the largest rectangular block satisfying some condition without iterating explicitly). but in my case I have a multidimensional (up to 6 dimensions) binary array and I want to find the largest hyperrectangle (by volume, i.e. product of dimensions) that contains only 1's.

For example, in 3D, the data would look like:

data = Table[If[i - j - k <= -1, 1, 0]
   , {i, 11}
   , {j, 11}
   , {k, 11}
   ];

https://i.stack.imgur.com/2tbfZ.jpg

enter image description here

Note that I'm looking for an algorithm, and it doesn't have to be written in mathematica.

Community
  • 1
  • 1
Mhmd
  • 1
  • 1
    This question belongs on the [mathematica](http://mathematica.stackexchange.com/) stackexchange. – simonzack Nov 19 '14 at 13:38
  • 1
    No, not really. I'm looking for an algorithm, and it doesn't have to be written in mathematica. – Mhmd Nov 19 '14 at 13:45
  • can you include your definition of "hyperrectangular area" in the question? – agentp Nov 19 '14 at 21:28
  • I doubt there is an algorithm that can do this quickly for all cases. Can you tell us more about your specific needs? (e.g. how big is your original array, how close to optimal do you want, is there any pattern to the binary array, etc.) – arghbleargh Nov 19 '14 at 23:37
  • @arghbleargh : I'm not looking for an optimum algorithm. I just need an algorithm that does the job without caring about the time needed. As I mentioned in my question: I have 6 dimensions, with up to 15 points in each dimension. – Mhmd Nov 20 '14 at 13:02
  • I suspect brute force would be sufficient for your purposes, as long as you do some basic optimizations (e.g. if some hyperrectangle doesn't work, no hyperrectangle containing it can work either). If you use C++, you can probably get it to solve typical test cases in under an hour. – arghbleargh Nov 20 '14 at 22:18

0 Answers0