1

Given an input set S of k-dimensional axis aligned rectangles, I would like to find all the k-dimensional intervals on which at least 2 k-dimensional rectangles overlap. If more than 2 k-dimensional rectangles overlap, I would like to find the count of how many were overlapping on each of such regions.

Edit: I have done this in 1D and 2D using Klee's Measure and the Line Sweep Algorithm. I am confused about how to get it beyond 2 dimensions.

gohar94
  • 138
  • 1
  • 3
  • 11
  • And I want a puppy:) So what have you done so far? Maybe first try to do this for the 1D/2D/3D, that should not be to hard. Than try work out a general case, for higher dimensions. – Gijs Den Hollander Feb 28 '17 at 11:13
  • This post http://mathoverflow.net/questions/138635/hyperrectangle-partition-of-set-of-overlapping-hyperrectangles should get you started – Gijs Den Hollander Feb 28 '17 at 11:17
  • Gijs, I have edited my question. Hope it makes it clear. – gohar94 Feb 28 '17 at 18:42
  • http://stackoverflow.com/questions/6008206/detect-overlapping-of-rectangular-prisms Maybe look at this one for 3D case. And i think you should look into the link I already posted. Thats is about the k-dimensional case...duplicate? – Gijs Den Hollander Feb 28 '17 at 19:23
  • What are your time complexity requirements? The brute force solution seems pretty easy. – samgak Feb 28 '17 at 21:01

0 Answers0