0

Given an array of 3D integers, what is the algorithmic complexity of determining which of those integers exist within a cube? I'm assuming the points can be represented in a number of concurrent data structures, each sorted in one or more dimensions.

My intuition tells me given a sorted array of points in 1D one can determine the subset of points between some lower and upper bound in something like O(log(n), but I would be very grateful for any insights others can offer on this notion (and any help others can offer generalizing to the multidimensional case!).

duhaime
  • 25,611
  • 17
  • 169
  • 224
  • when you mean 3d ints, im guessing you mean "Given an array of points in 3D space" ? But i guess really, the complexity would be whatever complexity YOU solved it for. You could be horribly ineffecient. Lets start with you writing your algorithm and we can move to improve it from there and go over complexities. Though given this is 3d space, it is as easy to figure out as a calculus formula. – Fallenreaper Dec 01 '17 at 03:51
  • Yes, exactly! I'm after the "maximally efficient" solution of course, not some Rube Goldberg. Do you have a reference I could consult for help with the calculus? – duhaime Dec 01 '17 at 03:53
  • Do you have the 8 points to define a cube and an array of 3d points to test against? – Fallenreaper Dec 01 '17 at 03:55
  • This question is rather vague. In your 1-D case, you can find the indices of the least and greatest within-bounds points in O(log n) time, but I'm not sure in what sense that actually gives you the subset in that range of indices, *per se*. You obviously couldn't (say) print it out in O(log n) time, unless you restrict the problem to the case that the subset has O(log n) size. – ruakh Dec 01 '17 at 03:57
  • See kd-trees or octrees – c2huc2hu Dec 01 '17 at 03:57
  • @Fallenreaper Yes, but I'm after a general solution, my data isn't interesting, so one can assume random distribution in the 3d and a random cube that contains a subset of the points. – duhaime Dec 01 '17 at 03:58
  • @ruakh I'm only trying to compute the complexity of determining the set of points in the cube, not of doing anything with the points thereafter. – duhaime Dec 01 '17 at 03:59
  • Well, If you calculate the planes which exist (6) from your cube, and then test against them. That being said, the complexity of a point being inside an arbituary cube would be the sum of calculating the point being on side A or B of each plane. I dont want to give you the answer, ideally you should think on it. I dont see any work showing an attempt at solving it yourself, so i am making an asusmption that this may just be a homework answer. That being said, i am trying to guide ya. :) – Fallenreaper Dec 01 '17 at 04:00
  • @Fallenreaper, that's what I thought, so 3 * O(log(n))? Is there no trick to do better? – duhaime Dec 01 '17 at 04:01
  • Step 1: Find the complexity of 6 tangent lines. Step 3: given 3 sets of parrallel lines, find whether `xmin<=x<=xmax && ymin<=y<=ymax && zmin<=z<=zmax` Step 4: realize there is no 2. Step 4: 6*(complex of finding tangent lines given a plane created by 3 points) + 3. Step 5: With complexities, K is removed, right? Therefore, you need to find 2 vectors to determine the normalized vector, those are 2 and then cross multiple. According to matrix multiplication on wikipedia, its complexity is n^2.373 - n^3. Id just walk through it piece by piece though. – Fallenreaper Dec 01 '17 at 04:24

1 Answers1

1

If you're unfamiliar with the math involved, I recommend doing this problem in two dimensions first, with a rectangle. That way, you can get familiar with the math, which is really just a bit of basic trigonometry. After that, stepping up to three dimensions isn't very difficult.

The problem is much simpler if the cube (or rectangle) is axis aligned, so you probably should do that first. For an example of determining the rotation you need, see How to calculate rotation angle from rectangle points?.

Once you've determined the rotation angle, you can translate the rectangle to the origin and rotate it by doing the first two steps in the accepted answer here: Drawing a Rotated Rectangle.

You now have an axis-aligned rectangle that's centered at the origin.

Finally, for each of your points:

  1. Apply the same translation and rotation that you applied to the rectangle.
  2. Test to see if the x and y coordinates in the resulting point are within the rectangle. This is a matter of, at most, four bounds checks.
  3. If the point is in the rectangle, save it.

Once you've done this in two dimensions, you should be able to apply those concepts to three dimensions.

The algorithm is O(n), where n is the number of points.

Jim Mischel
  • 131,090
  • 20
  • 188
  • 351
  • Thanks very much @JimMischel, this is very helpful. As fate would have it, our discussion in [this thread](https://stackoverflow.com/questions/17883793/finding-the-number-of-elements-between-i-and-j-in-an-integer-array-in-o1/17887042?noredirect=1#comment82130780_17887042) led me to hypothesize an approximate solution can satisfy in ~constant time... – duhaime Dec 01 '17 at 12:35
  • I can quantize my dimensions, sort my points in each dimension, and for each unit of the quantized {x,y,z} dimension, store the index position of the first item in the sorted array with that value +/- known error (or a reference to the last filled unit in the given axis). Then after 6 bounds checks and a set intersection I believe I can approximate the result. Have I overlooked something? – duhaime Dec 01 '17 at 12:35
  • @duhaime All the pre-processing you described takes quite a lot of time. The technique I describe above is O(n), and gives you the set of points that are in the cube. The thread you link is building a data structure that allows determining an answer for any `i` and `j`. Are you trying to build something that allows you to quickly determine the number of points in any given cube? – Jim Mischel Dec 01 '17 at 14:14
  • yes, that's the goal. I have a three.js scene and wish to use the frustum (which gives the cube boundaries so to speak) to identify the set of points in the 3D subset of the space. I'd like to do as much pre-processing as possible because I plan to run this calculation whenever the camera moves (ideally with minimal debouncing) – duhaime Dec 01 '17 at 14:34