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.
Algorithm TrapezoidalMap(S)
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 s_{i}?
Let
D_{0}, D_{1}, ..., D_{k} be the trapezoids intersected by s_{i},
ordered from left to right.
D_{0} is the trapezoid containing the left endpoint p of s_{i}.
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).
D_{j}_{+1} must be a right neighbor of D_{j}, and it is easy to determine which one:
If rightp(D_{j}) lies above s_{i}, then D_{j}_{+1} is the lower right neighbor of D_{j}, otherwise it is its upper right
neighbor, Figure.
Algorithm FollowSegment(T, S, s_{i})
1. Let p and q be the left and
right endpoint of s_{i}.
2. Search with p and q in the
search structure D to find D_{0}.
3. j ß0;
4.
while q lies to the right of rightp(D_{j})
5.
do if rightp(D_{j}) lies above s_{i}
6.
then Let D_{j+1} be the lower right neighbor of D_{j} lies.
7.
else Let D_{j+1} be the upper right neighbor of D_{j} lies.
8.
j ßj + 1
9.
return D_{0}, D_{1}, ..., D_{j}
Incrementing
T and D  Simple Case
How are T and D
updated?
Simple case: s_{i} 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 s_{i}
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: s_{i} intersects D_{0}, D_{1}, ..., D_{k}_{}
Figure 1.2 Segment s_{i}
intersects four trapezoids.
To update T:
 Draw vertical extensions through the endpoints of s_{i} that were not present, partitioning D_{0} and D_{k}
 Shorten the vertical extensions that now abut on s_{i}, merging the appropriate trapezoids. This leads to merging trapezoids along the segment s_{i}, (Figure 1.2). Use the information stored to D_{0}, D_{1},...,D_{k} to determine all the needed data. This step can be done in linear time.
To update D:
Remove
the leaves for D_{0}, D_{1},...,D_{k}

Create leaves for the new trapezoids
 If D_{0} has the left endpoint p of s_{i}
in its interior, replace the leaf for D_{0} with a point node for p and a
segment node for s_{i} (similarly with D_{k})
 Replace the leaves of the other trapezoids with single segment nodes for s_{i
} 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.