0
$\begingroup$

I have a sequence of points over time, and a grid of X by Y cells to which I need to calculate the cells in which the points fall, as depicted in the diagram below

enter image description here

Another point now arrives (as depicted by the red dot to the right), the grid is stretched to fit the new data, and the containing cells recalculated

enter image description here

Known aspects of the problem

  • The number of X and Y cells is decided up front and does not change over time
  • Time between points is irregular
  • When a new point arrives it may have a higher or lower Y value than the current grid range, and here the grid Y will stretch to accommodate, just as it does in the X direction.
  • The first and last point on the X axis form the X range of the grid
  • The maximum and minimum point Y values form the Y range of the grid
  • The maximum number of points is unbounded and an get large

I have thought in depth about this problem and I cannot see if it is possible to recalculate the yellow cells upon the arrival of a new point, without needing to repeatedly iterate through the sequence of points and performing the math to identify the cell it is bounded by. Given the number of points is unbounded the computation time will grow to be inefficient.

Is there another way to solve the problem, but which does not grow in computational time as points are added ?

$\endgroup$
7
  • 1
    $\begingroup$ What operations do you want to perform on this data structure? Right now the only thing you do is update the data, but you haven't mentioned any queries. We need to know a list of all operations you want to perform, to be able to suggest a data structure. $\endgroup$
    – D.W.
    Commented Oct 28, 2023 at 6:13
  • $\begingroup$ Not sure what you mean here by "list of all operations you want to perform,". The problem is about how to recalculate the yellow cells upon receipt of a new point without increasing the computational time. The result of this recalculation is the list of yellow cells. What they are user for afterwards is not relevant to the problem $\endgroup$ Commented Oct 28, 2023 at 8:36
  • $\begingroup$ The new point can arrive to the left of the grid as well, right? In that case, if one point arrives to the right and next one to the left, alternatingly, then, in the worst case, all the yellow cells will change on every new insertion. In the worst case, you must spend constant time on each point on every insertion that occurs outside of the grid. $\endgroup$ Commented Oct 28, 2023 at 10:50
  • $\begingroup$ No the points represent a timeseries. Points only arrive on one side of the grid $\endgroup$ Commented Oct 28, 2023 at 22:49
  • 1
    $\begingroup$ Please don't put clarifications in the comments. Instead, edit your post so it is clear what you are asking. $\endgroup$
    – D.W.
    Commented Oct 30, 2023 at 18:48

2 Answers 2

1
$\begingroup$

I'm assuming you want a data structure storing a set of points where you can:

  • Insert a new point
  • Get the list of all cells which contain at least one point (this is your query).

You can do this by storing the points in a 2D range tree. These allow you, for any given orthogonal range, to test if they contain at least one point in $O(\log^2 n)$ time (where $n$ is the total number of stored points). You can also make them dynamic (i.e. allow for insertions and deletions of points) by standard dynamization methods. (In short: insert and delete stuff without worrying about your trees becoming unbalanced, and after every $O(n)$ updates rebuild the whole structure)

Now you can simply do the following: keep track of the maximum and minimum x/y coordinates. Each time a point is inserted, insert it into the 2D range tree and update the min/max coordinates as needed. To perform a query, loop through your cells (which you can compute knowing the min/max coordinates) and for each cell test if there is a point inside in $O(\log^2 n)$ time.

This will give you $O(\log n)$ amortized update time and $O(XY\log^2 n)$ query time. You could even make this worst-case instead of amortized with a bit more work, and use more sophisticated data structures to replace the $\log^2 n$ with $\log n$.

$\endgroup$
3
  • $\begingroup$ What do you mean by "list of cells containing a point"? Each point is in only a single cell. Do you mean "get the cell containing a point", i.e., given a point $P$, find the cell containing it? (If so, you don't need any data structure, you just need to know the min/max coordinates, but you don't need any range tree.) Do you mean "get the list of points contained in a cell", i.e., given a cell $C$, output all points that are in $C$? $\endgroup$
    – D.W.
    Commented Oct 30, 2023 at 18:46
  • $\begingroup$ Incidentally, this is why we need the question to specify the operations, not for us to guess what they might be. $\endgroup$
    – D.W.
    Commented Oct 30, 2023 at 18:46
  • $\begingroup$ @D.W. I mean, "get the list of all cells containing at least one point". I.e. if a cell contains at least one point then it is included in the list, otherwise not. I'll try to make this clearer $\endgroup$
    – Tassle
    Commented Oct 31, 2023 at 8:27
0
$\begingroup$

Based on your clarification to the question, it appears the task is as follows: you are given a list of all points; the algorithm should process this list and then output the list of all cells that contain at least one point.

If that is right, it is not possible to do better than linear time. Why? Because in the worst case each point can land in its own cell, so the output has linear size, so it takes at least linear time to generate that much output. Therefore the worst-case running time of any correct algorithm will be at least linear in the number of points.

If that is not right, please edit your question to state the problem to be solved more clearly.

$\endgroup$
2
  • $\begingroup$ The question does states that the number of cells is constant (see 1st bullet point). So one point per cell would be $O(1)$ and therefore not linear in the number of points. $\endgroup$
    – DirkT
    Commented Oct 31, 2023 at 11:47
  • $\begingroup$ @DirkT, based on my reading of the problem, the number of cells is an input to the algorithm, hence not a constant. It doesn't change as new points arrive, so constant in that sense, but not constant in the sense of $O(1)$ (as a function of length of the input to the algorithm). But I guess this is ambiguous and it's another reason we need a more precise statement of the problem in the question. $\endgroup$
    – D.W.
    Commented Oct 31, 2023 at 22:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.