data structure for storing angle intervals

Question

I want to create a data structure that can store angle intervals, for example (a,b) where both a and b represent the polar angle of the the end points of a segment A,B against a point Q

This data structure must support two operations. Insert new intervals and also tell me if the entire view point of point Q has been covered, in other words if the union of all viewpoints created by the segments is 360 degrees.

I tried implementing a very simple interval tree where the insertion procedure is as follows.

1. Let (a,b) the interval that you want to insert.
2. Start from the root node, see if (a,b) is covered entirely by the interval stored in the root node, if that is the case, return and do nothing.
3. Otherwise, there maybe some part covered by the root node and some part not completely covered. At most two parts can not be covered and depending on each case, recurse to the left or/and to the right subtree.

I am not using augmented data structures so in the worst case to insert an interval you will have to do O(n) operations, giving you a complexity of O(n^2) for inserting n intervals.

Here is the problem though. When you are working with angles, you have to deal with cycles, which polar angle is a and which polar angle is b. So given a segment AB you find the polar angles of the end points against Q, but then how do you find out the interval that you will store in your tree?

One might say, okay, your interval can be (min(angleAQ, angleBQ), max(angleAQ, angleBQ)).

This however will not work in the following case:

The interval would be defined by the blue angle and the green angle, which is much larger than the actual view point which is defined by the red angle.

Due to this cycle property, it's much more difficult to manage such angle intervals.

My question is whether such an interval tree can exist and if so can someone give me some hints to overcome these difficulties?

thank you in advance

Answer 1

The circularity of angles is not a major obstacle: to instead an interval like [270, 45) that wraps around, instead insert two intervals [270, 360), [0, 45).

To implement insertion without wraparound, we can use a binary search tree. This tree tracks the uncovered intervals by mapping each endpoint of an uncovered interval to whether it's a left or right endpoint. For example, if we have covered intervals [0, 45), [0, 60), [90, 120), [150, 180), [180, 270), then the mapping is

60: left
90: right
120: left
150: right
270: left
360: right .

Initialize the mapping with

0: left
360: right

To insert an interval [a, b) with a < b, we do the following. Find the predecessor x of a in the mapping (greatest key not greater than a). If x exists and is a left endpoint, then insert a as a right endpoint (after x). Find the successor y of b in the mapping (least key not less than b). If y exists and is a right endpoint, then insert b as a left endpoint (before y). Delete all keys not just inserted between a and b inclusive. The initial interval is covered completely if and only if the mapping is empty.