Vertical ray shooting data structure for non intersecting segments in two dimensions.

[make-github-pseudonymous-again]

Linear space and logarithmic query time using a persistent search tree.

Construction

Begin with two persistent empty search trees<X, attr('key', increasing)> and <Y, ?>.
Insert {"key": -Infinity, "value": <Y, (s,t) => increasing(ycoord(x,s), ycoord(x,t))} in X.
Sweep left to right in x coordinate:

• At endpoint (x,y) of s:
  • if left endpoint: Insert s in Y.
  • if right endpoint: Remove s in Y.
  • Insert {"key": x, "value": <Y, (s,t) => increasing(ycoord(x,s), ycoord(x,t))>} in X.

Updating the comparison predicate for Y is valid since the total order on Y \ { s } has not changed between the last value of x and the new one.