3
$\begingroup$

Definition 1: Point $(x,y)$ is controlling point $(x',y')$ if and only if $x < x'$ and $y < y'$.

Definition 2: Point $(x,y)$ is controlled by point $(x',y')$ if and only if $x' < x $ and $ y' < y$.

I'm trying to come up with data structure to support the following operations:

  • $\mathrm{Add}(x,y)$ - Adds a point $(x,y)$ to the system in $\mathcal{O}(\log n)$ complexity where $n$ is the number of points in the system.

  • $\mathrm{Remove}(x,y)$ - Removes a point $(x,y)$ from the system in $\mathcal{O}(\log n)$ complexity where $n$ is the number of points in the system.

  • $\mathrm{Score}(x,y)$ - Returns the number of points $(x,y)$ controls - number of points that $(x,y)$ is controlled by. Worst case complexity $\mathcal{O}(\log n)$ .


I've tried to solve it using multiple AVL trees, but could not come up with elegant enough solution.

This question appeared on my exams few days ago. The question should have relatively straightforward as it was worth $15/100$ points. I tried to solve this by several AVL trees but couldn't come up with elegant enough solution.

Hints are welcome.

$\endgroup$
  • 1
    $\begingroup$ Are you familiar with space partitioning data structures? $\endgroup$ – Raphael Feb 19 '15 at 8:37
  • $\begingroup$ No, I will try to think in that direction. $\endgroup$ – Naftaly Feb 19 '15 at 19:11
1
$\begingroup$

Solution outline:

We will maintain two AVL trees.

  • Tree_X: will hold points sorted by their X coordinate.
  • Tree_Y: will hold points sorted by their Y coordinate.

Each node within both trees will hold the following additional data:

  1. Number of leaves in left sub-tree.
  2. Number of leaves in right sub-tree.

For a point $(x,y)$ we will define regions $A$ ,$B$, $C$, $D$:

  • Point $(x',y')$ is in $A$ if $x' < x$ and $y' > y$.
  • Point $(x',y')$ is in $B$ if $x' > x$ and $y' > y$.
  • Point $(x',y')$ is in $C$ if $x' < x$ and $y' < y$.
  • Point $(x',y')$ is in $D$ if $x' > x$ and $y' < y$.

Now it is clear that Score(x,y) = |C|-|B|. However $|A|+|C|$, $|B|+|D|$, $|A|+|B|$, $|C|+|D|$ could be easily retrieved from our two AVL trees, as we will soon see. And notice that $\frac {(|A| + |C| + |C| + |D|) - (|A| + |B| + |B| + |D|)}{2} = |C|-|B|$

Implementation of required operations:

  • Add(x,y) - We will add point (x,y) to both of our AVL trees. Since the additional data we are storing is affected only on the insertion path and since the insertion occurs in (logn), the total cost of Add(x,y) is O(logn).

  • Remove(x,y) - We will remove point (x,y) from both of our AVL trees. Since the additional data we are storing is affected only on the removal path and since the removal occurs in (logn), the total cost of Remove(x,y) is O(logn).

  • Score(x,y) - I will show how to calculate $|B|+|D|$ as others done in similar way and same complexity costs. It is clear that $|B|+|D|$ is the number of points which satisfy $x' > x$. To calculate this number we will:

    1. Find x in AVL_X. Complexity O(logn).
    2. Go upwards in Tree_X until the root and on each turn right we will sum the number of elements in left sub-tree of the son. Complexity O(logn).

    Total cost of Remove(x,y) is O(logn).

$\endgroup$

Your Answer

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

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