An Incremental Randomized Algorithm
We are going to use an incremental
algorithm. It will take one segment at time and after every addition it will
update the trapezoidal map and the search structure. This means that after
every loop we have valid trapezoidal map and search structure for it.
This means that after every loop we have valid trapezoidal map and search structure for it.
Key features of the algorithm:
-Incremental: Every time we insert a segment, we have a complete trapezoidal map and a complete data structure for the segments inserted before.
-It uses randomness, so there are no bad inputs.
Finding Intersected Trapezoids
How to add a new segment si?
Let D0, D1, ..., Dk be the trapezoids intersected by si, ordered from left to right.
D0 is the trapezoid containing the left endpoint p of si. To find it, perform a query on D (the data structure corresponding to the segments inserted so far) with p. We have to be careful if p was already present as an endpoint (assume the new point is slightly to the right).
Dj+1 must be a right neighbor of Dj, and it is easy to determine which one: If rightp(Dj) lies above si, then Dj+1 is the lower right neighbor of Dj, otherwise it is its upper right neighbor, Figure.
Algorithm FollowSegment(T, S, si)
1. Let p and q be the left and
right endpoint of si.
2. Search with p and q in the search structure D to find D0.
3. j ß0;
4. while q lies to the right of rightp(Dj)
5. do if rightp(Dj) lies above si
6. then Let Dj+1 be the lower right neighbor of Dj lies.
7. else Let Dj+1 be the upper right neighbor of Dj lies.
8. j ßj + 1
9. return D0, D1, ..., Dj
Incrementing T and D - Simple Case
How are T and D updated?
Simple case: si is completely contained in one trapezoid D (Figure 3.1)
- In T, D
is replaced by 4 trapezoids and update also their neighbors records.
- In D, the leaf corresponding to D is replaced by a small tree with 2 point nodes, 1 segment node, and 4 leaves, note that if one or both endpoints equal to leftp(D) or rightp(D) then there would be only two or three new trapezoids.
Notify that all the needed information is available in constant time from the segment si and from the information stored in D.
Figure 1.1 The new segment lies completely in trapezoid D.
Incrementing T and D - General Case
General case: si intersects D0, D1, ..., Dk
Figure 1.2 Segment si intersects four trapezoids.
To update T:
- Draw vertical extensions through the endpoints of si that were not present, partitioning D0 and Dk
- Shorten the vertical extensions that now abut on si, merging the appropriate trapezoids. This leads to merging trapezoids along the segment si, (Figure 1.2). Use the information stored to D0, D1,...,Dk to determine all the needed data. This step can be done in linear time.
To update D:
Remove the leaves for D0, D1,...,Dk
Create leaves for the new trapezoids
- If D0 has the left endpoint p of si in its interior, replace the leaf for D0 with a point node for p and a segment node for si (similarly with Dk)
- Replace the leaves of the other trapezoids with single segment nodes for si
- Make the outgoing edges of the inner nodes point to the correct leaves. Notify that many inner nodes could be pointing to the same leaf.