2.2. Segment Trees

A segment tree is constructed for answering the following 2D (line segment/line) stabbing query efficiently :

Input: a set S of segments in the plane;
Query: a vertical ^[1] line l ;
Output: all segments s ˆˆ S crossed by l .

Let S = { s ₁ , s ₂ , , s _n } be the set of segments and let E be the sorted set of x -coordinates of the endpoints. We assume general position; that is, E = { e ₁ , e ₂ , , e ₂ _n } with e _i < e _j for i < j (Section 9.5). For the construction of the tree, we can split E into 2 n + 1 atomic intervals

which represent the leaves of the segment tree.

The segment tree is a balanced binary tree. Each internal node v represents an elementary interval I , which is split into intervals I _l and I _r for the two children of v . The intervals are split with respect to the endpoints of the segments; see Figure 2.2. In the first place, the segment tree is a one-dimensional search tree for the x -coordinates of the endpoints of the segments. The one-dimensional search tree contains search keys in every node; the data points are represented in the leaves of the tree. Every node v additionally represents an interval I _v so that all points in the (sub)tree represented by root node v are in I _v . In Section 2.5, we generalize the one-dimensional search tree to arbitrary dimension d . An example of a one-dimensional search tree is given in Figure 2.7.

Figure 2.2: A segment tree for a set of segments. The segment s is minimally covered by the nodes v ₁ , v ₂ , v ₃ , and v ₄ .

The following is the one-dimensional search tree sketch (see also Algorithm 2.3):

Input: given a sorted list S of n elements x ₁ , x ₂ , , x _n ;
Output: the root node of a one-dimensional search tree for S ;
If S = 0, then set v := Nil and return v ;
Otherwise, if S ‰ 1 then

Algorithm 2.3: Construction of a simple balanced one-dimensional search tree.

SearchTree( S ) ( S is a sorted list { x ₁ , , x _n })

  if   S  =     then   v  := Nil  else   v  := new node  n  :=  S       (  L, R  ) :=  S.  Split(  m  )  v.  Key :=  S.  Get(  m  )  v.I  := [  S.  First  , S.  Last])          /* Alternatively:  v.I  := [  x  ₁  ,   , x  _n ]*/  v.  LeftChild := SearchTree(  L  )  v.  RightChild := SearchTree(  R  )  end if   return   v

Allocate a node v with two children for the root of the tree;
Choose the element x _m of S with and insert the branch key x _m at v . Insert the interval I = [ x ₁ , x _n ] at v . If necessary, I also contains the data points of the interval;
Compute a one-dimensional search tree v _l for x ₁ , , x _m and compute a one-dimensional search tree v _r for x _m ₊₁ , , x _n ;
Insert v _r as the right child of v and v _l as the left child of v ;
Finally, return the node v .

Obviously, the corresponding one-dimensional tree has height O (log n ). We can find an element x _i in logarithmic time by starting from the root and branching towards x _i using the keys in the nodes. The sketch and the pseudocode of this simple query procedure are omitted.

So far, we have constructed a tree that represents the information of the end-points of the segments plus the dummy nodes ˆ and ˆ ˆ . Obviously, this is not sufficient for answering a stabbing query. Additionally, we have to incorporate the information of the segments into the tree. Therefore, let us consider a single segment s represented by the x -coordinates ( e _j , e _k ) of its endpoints. The segment s can be represented by a consecutive set of elementary intervals. We choose a minimal set of elementary intervals (or the corresponding nodes) in the one-dimensional search tree so that s is fully covered. Due to Algorithm 2.3, every node represents an elementary interval v.I and, if necessary, its data points. Minimal means that the nodes are chosen as close as possible to the root of the tree; see Figure 2.2. We store s in each of the associated nodes. More precisely, let v .pred be the predecessor of v in the interval tree. A segment s = ( e _j , e _k ) represented by the x -coordinates of the endpoints is stored in a list v. L at v iff v.I [ e _j , e _k ] and ( v. pred) . I [ e _j , e _k ]. Thus, each node represents an elementary interval v.I and a list of segments v.L ; for an example, see Figure 2.3.

Figure 2.3: The query procedure for a segment tree and a query line l. The shaded intervals indicate the query path from the root to the leaf. All segments stored at the corresponding nodes are reported .

The one-dimensional search tree with intervals v.I is built up in O ( n log n ) time, as was shown previously. However, we need to show how the segment partitions are inserted into the tree. This is done by the following recursive insert procedure, which has to run for every segment s = ( e _j , e _k ).

The following is the sketch of the segment insertion in the one-dimensional search tree:

Input: given a line segment s = ( e _j , e _k ) and the root v of the segment tree;
If the interval v.I is already a subset of the interval [ e _j , e _k ], then insert s into the segment set v.L and stop;
Otherwise, let v. LeftChild and v. RightChild be the children of v . This means that the interval v.I equals ( v. LeftChild) .I ˆ ( v. RightChild) .I ;
- If the interval [ e _j , e _k ] and the set ( v. LeftChild) .I overlap, then run the insert procedure recursively with s and the segment tree v. LeftChild;
- If the interval [ e _j , e _k ] and the set ( v. RightChild) .I overlap, then run the insert procedure recursively with s and the segment tree v. RightChild.

By inserting every segment into the one-dimensional search tree of the line segments endpoints, we will finally obtain the segment tree. Altogether, Algorithm 2.4 constructs the segment tree by using Algorithm 2.5 as a subroutine. Note that S _x . Extend extends S _x by the dummy elements ˆ and ˆ ˆ .

Lemma 2.4. The segment tree for n segments can be built in O ( n log n ) and uses O ( n log n ) space.

Proof: The binary tree has depth O ( logn ) and O ( n ) nodes. At each level of the segment tree T , a segment s = ( e _j , e _k ) is stored at most twice. To prove this fact, let us assume that three nodes u _l , u _m , and u _r of the same level in T contain the segment s . The intervals of their parents do not overlap. This is because they can overlap only if a pair of u _l , u _m , and u _r has a common predecessor. In this case, the segment has to be inserted for the predecessor. If the intervals of the parents of u _l , u _m , and u _r do not overlap, the intermediate node of u _l , u _m , and u _r must have a parent whose interval fully contains [ e _j , e _k ]; therefore, s is not inserted at u _m which gives a contradiction. Summing up over all segments and levels, the segment tree has space O ( n log n ).

Algorithm 2.4: Building a segment tree.

SegmentTree( S ) ( S is a set of line segments given by endpoints)

  S  _x :=  S.  SortX  S  _x :=  S  _x  .  Extend  v  := SearchTree(  S  _x )  while   s        do   s  :=  S.  First           SegmentInsertion(  v, s  )  S.  DeleteFirst  end while

With a similar argument, one can prove that, during the insertion operation, only four nodes on every level could be visited. Thus a single segment is inserted in O (log n ) time, which gives the overall time bound.

For a stabbing query with a vertical line l , we will proceed as follows . We start with the x -coordinate l _x of the vertical line l and the root node v of a segment tree.

Algorithm 2.5: Insertion of a segment s in the segment tree.

SegmentInsertion( v, s ) ( v is one-dimensional search tree of the x -coordinates of the endpoints of segment set S , s ˆˆ S .)

  e  _j :=  s.  LeftXCoord  e  _k :=  s.  RightXCoord  if   v.I    [  e  _j  , e  _k ]  then  (  v.L  )  .  ListAdd(  s  )  else   if  (  v.  LeftChild)  .I    [  e  _j  , e  _k ]       then  SegmentInsertion(  v.  LeftChild  , s  )  end if   if  (  v.  RightChild)  .I    [  e  _j  , e  _k ]       then  SegmentInsertion(  v.  RightChild  , s  )  end if   end if

Algorithm 2.6: The stabbing query for a segment tree.

StabbingQuery( v, q ) ( v is the root node of a segment tree and l a vertical line segment)

  L  := Nil  if   v    Nil and  l  _x    v.I   then   L  :=  v.L   L  _l := StabbingQuery(  v.  LeftChild  , l  )  L  _r := StabbingQuery(  v.  RightChild  , l  )  L.  ListAdd(  L  _r )  L.  ListAdd(  L  _l )  end if   return   L

The following is the sketch of the stabbing query with a segment tree:

Input: given the x -coordinate l _x of the vertical line l and the root node v of a segment tree;
If l _x is inside the interval v.I , then report all segments in v.L ;
If v is not a leaf, then for the children v. LeftChild and v. RightChild of v , we know that the interval v.I equals ( v. LeftChild) .I ˆ ( v. RightChild) .I and we proceed as follows:
- If l _x lies inside ( v. LeftChild) .I , then start a query with segment tree v. LeftChild and l _x ;
- Else we have l _x ˆˆ ( v. RightChild) .I , and we start a query with segment tree v. RightChild and l _x .

Figure 2.3 shows an example for a segment query. The shaded intervals indicate the query path from the root to the leaf.

Lemma 2.5. A vertical line stabbing query for n segments in the plane can be answered by a segment tree in time O ( k + log n ) , where k stands for the number of reported segments.

Proof: Obviously, the tree is traversed with O (log n ) steps. The running time O ( k + log n ) stems from the cardinality k of the corresponding sets v.L .

The segment tree was first considered in [Bentley 77] and extended to higher dimensions by several authors; see, for example, [Edelsbrunner and Maurer 81] and [Vaishnavi and Wood 82].

A WeakDelete operation can be performed in O (log n ) time (see Chapter 10). We have to mark a segment s in every list v.L with s ˆˆ v.L . By construction, a segment s is stored at most twice in every level of the segment tree and occurs at most O (log n ) times. We proceed as if we would like to insert the segment s , which can be done in O (log n ) time; see also the proof of Lemma 2.4.

Lemma 2.6. A WeakDelete operation for a segment tree of n segments in the plane can be performed in time O (log n ) .

^[1] Arbitrary query lines l can be handled by application of a transformation matrix; see Section 9.5.3.