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.

Algorithm TrapezoidalMap(S)

  1. Determine a bounding box R that contains all of the segments of S
  2. Initialize T, the trapezoidal map structure and D, the search structure:

  3.     T is just the single trapezoid corresponding to the whole box R
        D has only one node, corresponding to that trapezoid
  4. Compute a random permutation s1, s2, ..., sn of the segments of S
  5. for i 1 to n

  6.     do Find the set of trapezoids in T properly intersected by si
  7.             Remove them from T and replace them by the new trapezoids that appear because of the insertion of si
  8.          Remove the leaves of D for the old trapezoids and create leaves for the new ones. Link them to the existing inner nodes by adding some new inner nodes, as explained later

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
    3. j
while q lies to the right of rightp(Dj)
do if rightp(Dj) lies above si
                then Let Dj+1 be the lower right neighbor of Dj lies.
else Let Dj+1 be the upper right neighbor of Dj lies.
j j + 1
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.