A plane-sweep algorithm for a points in triangles inclusion problem

Question

I was given the following homework assignment:

Consider a set of $p$ points and $t$ triangles in the plane. The triangles are pairwise disjoint, that is, their edges do not intersect, no triangle lies in the interior of another, and no edge/vertex is part of more than one triangle. The points are in general position with respect to the triangles, that is, no point lies on a vertex or an edge of a triangle. The triangles are given by the coordinates of their vertices, and also the points are given by their coordinates. All points and vertices have pairwise different coordinates. (See below for an example.)

The task is to determine for each of the $p$ points whether it lies inside a triangle, and if yes in which. Design an efficient algorithm for solving this task. Explain your solution in detail, show its correctness, and analyze its runtime and memory requirements.

I've coem up with the following algorithm, that closely resembles the Bentley–Ottmann algorithm for the intersection of line segments. The idea is to sweep the plane from left to right analogousely to it. The main point is the observation that a point p lies in a triangle iff $p$ lies $x$-wise between the triangle starting - and triangle endpoint as well as $y$-wise between the intersection points of the sweep line with the triangle sides. (For an illustration see below.)

SET-UP: Let $X$ be a priority in which we store the $x$-coordinates of the points of $P$ and $T$. Let further $Y$ be a Red-Black-Tree in which we store the $y$-coordinate-wise sorted list of triangle edges. At last let $T$ be the set of triangle points and $P$ be the set of the remaining points.

ALGORITHM:

1) $X := 0, Y := 0$

2) Insert the $x$-coordinates of all points of $P$ and $T$.

3) while $x \neq \emptyset$ do

• Find the minimum $m$ of $X$ and delete it from $X$.

• If $m$ is a triangle starting point then insert the incident edges into $Y$.

• If $m$ is a triangle middle point then delete the incident edge to the left of $m$ and insert the incident edge to the right of $m$ into $Y$.

• If $m$ is a triangle end point then delete both incident edges from $Y$.

• If $m$ is a point out of $P$ then do for all pairs of adjacent edges in $Y$:

  Calculate the intersection points of the sweep line L with the current pair of adjacent edges. Check wether the $y$-coordinate of $m$ lies between the $y$- coordinates of said intersection points. If it does the point $m$ is in the respective triangle. Report $m$ and said triangle.

I think that this algorithm should have $\mathcal{O}((p+t)*log(p+t))$ running time, but I don't know how to argue that in a more formal manner with the characteristic of Red-Black-Trees and so on. Could you help me with that?

Illustration 1 Illustration 2 Illustration 3

SOURCES:

http://www.ist.tugraz.at/_attach/Publish/Eaa17/assignment_06.pdf

Answer 1

Generally, you can analyze each step of the algorithm. Step 2 for constructing the tree (as insert operation can take $O(\log(n))$) is $O((p+t)\log(p+t))$. All operations in if statements take $O(\log(n))$ (finding the minimum, deleting a member, inserting a member, and so on). Also, the main while loop takes $|X|= p + 3t$. Hence time complexity of the algorithm would be $O((p+t)\log(p+t))$ as you guess.

In sum, to analyzing time complexity of an algorihtm in a formal manner, it would be enough discussed on each step of the algorithm.

For correctness, you should show that this algorithm can find a general point inside its triangle correctly.