Inclusion of points in rectangles using a sweepline algorithm

Question

Given is a set of points $P_{1},....,P_{n}$ with $P_{i} = (x_{i},y_{i})$. No two points have the same x and y coordinates. Given is also a set of m axis-parallel rechtangles $R_{1},...,R_{m}$ in a plane, described by their bottom left corner $(l_{j},b_{j})$ and upper right corner $(r_{j},u_{j})$. No two rechtangles intersect or overlay each other and no point is on the border of a rechtangle.

We need to describe a sweepline algorithm which can output all the points which are not in a rechtangle.

I proceeded like so:

The sweepline is a vertical line going from left to right and stopping and evaluating at each event point. Out event points are the points $P$ and also the $(l,b),(r,u)$ of each rechtangle. We sort all the event points according to their x-coordinate.

We use an AVL-Tree to save the y-coordinates of the lower left corner of a rechtangle and remove it once we reach it's upper right corner. When we reach a point $p$, we will simply evaluate if p is within the borders of a currently active rechtangle by checking if $y_{p} \in [b,u]$ of active rechtangle. If so we mark it as false and proceed.

The solutions are that we are given more complicated and I don't understand them fully. I also don't know if my solution would work and why. It seems to be plausible to me.

They also save at each node of the AVL, the size of its subtrees so they can see how many points smaller than a node there are. Then while evaluating a point $p$, they search for p in the AVL tree and determine $A$ the number of keys smaller than $p$. Then it says that if $A$ is an even number, then the point is not in a rechtangle. Done.

I don't understand how this works. please help.

Thank you very much

Answer 1

I think storing in the AVL-tree only bottom $y$ coordinate is not enough. I think you should store at least both bottom and top coordinates of the active rectangle. Since your rectangles are not overlapping storing only the bottom and top coordinates is enough to solve the problem.

Basically, storing active rectangle in the AVL tree needs to decide whether a point is in a rectangle. Consider the following scenario

  y1 ----------------------------
     |                          |
     |                          |
  y2 ----------------------------
         o y6
  y3 ----------------------------
     |                          |
     |           o y7           |
  y4 ----------------------------

  y5 ----------------------------
     |                          |
     |                          |
  y6 ----------------------------

Initially your $p$ points in the AVL tree. As you sweep you add both $y$ coordinates of the active rectangles in the tree (and remove them as you rich the end of the rectangle).

If at the same time you have more than one active rectangles then by brute force method you would need to go over all rectangles and check whether $p_y \in [b,u]$. However, using AVL tree you could find the point $p_y$ in the tree and check the number of points smaller than $p_y$. If that number is even, say $2k$, then you have exactly $k$ active rectangles below $p$ meaning that $p$ is not in one of them, otherwise (if odd) it is in a rectangle. Look at the above figure, there are 4 points smaller than $y_6$ and so $y_6$ is outside, but there are 3 points smaller than $y_7$ and so $y_7$ is in a rectangle.