• Computers & Technology
  • Home Computing
  • Business & Culture
  • Programming
  • Software
  • Web Development
  • Certification
  • Networking
  • Security & Encryption
  • Computer Science
  • Operating Systems
  • Microsoft
  • Hardware
  • Databases
  • Graphic Design
  • Apple
  • Digital Music
  • Digital Photography & Video
  • Games & Strategy Guides
  • Project Management
  • Mobile & Wireless Computing
• Education & Reference
  • Encyclopedias
  • Test Preparation
  • Studying & Workbooks
  • Schools & Teaching
  • Writing, Research & Publishing Guides
  • Foreign Language Study & Reference
  • Atlases & Maps
  • Dictionaries & Thesauruses
  • Words, Language & Grammar
  • College & University
  • Trivia & Fun Facts
  • Consumer Guides
• Business & Investing
  • Industries & Professions
  • Management & Leadership
  • Organizational Behavior
  • Personal Finance
  • Small Business & Entrepreneurship
  • Popular Economics
  • Marketing & Sales
  • Finance
  • Skills
  • Business Life
  • Economics
  • Job Hunting & Careers
  • Biography & History
  • Reference
  • International
  • Real Estate
  • Investing
  • Women & Business
• Science & Math
  • Mathematics
  • Technology
  • Reference
  • Earth Sciences
  • Physics
  • Biological Sciences
  • Behavioral Sciences
  • Nature & Ecology
  • Astronomy & Space Science
  • History & Philosophy
  • Experiments, Instruments & Measurement
  • Agricultural Sciences

8.2. Static Segment Tree

This is a quick recap, so if you are familiar with this classic data structure, you can proceed to the next section.

Given a set S ={ s ₁ , , s _n } of intervals s _i = [ a _i , b _i ] , and a query point q ˆˆ , we are looking for the subset S ={ s ˆˆ S q ˆˆ s }. This is often called a stabbing query and can be extended trivially to ^d .

Before describing the data structure, we define an elementary interval (EI). Let X = { a, b a ˆˆ s ˆˆ S, b ˆˆ s ˆˆ S } = { x _i } denote the set of endpoints , sorted by increasing value in a list. Then the interval [ x _i , x _{i +1} ) is called an EI. For convenience, we also include the intervals ( ˆ ˆ , x ) and [ x _{2 n} , ˆ ).

The segment tree is a balanced binary tree over the set of EIs, X . Each leaf _i stores one EI Int( _i ) := [ x _i , x _{i +1} ). We define the interval of an inner node as Int( ) := Int( ₁ ) ˆ Int( ₂ ), where _{1 , 2} are the two children of . Each node stores the so-called canonical subset S ( ) := { s ˆˆ S Int( ) s, Int(parent( )) s} (in other words, each interval s ˆˆ S is stored with several nodes _k in the tree, such that _k Int( _k ) = s , and such that s is stored as high up as possible). An example is shown in Figure 8.1.

Figure 8.1: Example of a segment tree.

Algorithm 8.2: Simple algorithm for answering a stabbing query.

query(






, q




)


output

S

(




)

if





is inner node

then


if


q



Int(





1

)

then

query(





1


, q

)

else

query(





2


, q

)

end if


end if

 

The construction of a segment tree is very easy: generate and sort X ; construct a skeleton binary tree over 2 n + 1 nodes; compute Int( ) for all nodes in the tree; and sift each segment s top-down through the tree.

The algorithm for answering a stabbing query is quite simple, as shown in Algorithm 8.2.

It is easy to see that such a segment tree needs O ( n log n ) space and O ( n log n ) construction time, and that a query can be answered in time O (log n + k ), where k is the size of the output.

8.3. Kinetic Segment Tree

By turning the static segment tree into a kinetic one, we are moving one step closer to our final goal of a kinetic BSP [de Berg et al. 01].

Now segments (i.e., intervals on ) can move freely they can swap positions , they can shorten or lengthen, etc. Observe, however, that the situation is not as difficult as it might seem, because of the following:

1. During the construction of the static segment tree, we never really needed to know the exact values of the endpoints of the intervals; it was completely sufficient to know their position in the sorted list of all endpoints;

2. For each segment s , there is a certain amount > 0 by which we can move s without invalidating the segment tree;

3. Whatever the position of a certain number segments, the skeleton of the segment tree is always the same. The only thing that changes is the labeling of the nodes with segment IDs.

These observations give rise to the following modifications of the original segment tree data structure:

• Segments are defined as s _i := ( a _i , b _i ) , a _i ,B _i ˆˆ , 1 ‰ a _i , b _i ‰ 2 n . a _i , b _i are called the rank of the endpoints;

• An array R [1 , , 2 n ] stores the current values of the endpoints (so the interval for s _i is given by , ). This array is kept sorted by value;

• With each segment s , we maintain a fragment list ( s ) := { s ˆˆ S ( )}. is kept sorted from left to right;

• For each elementary interval [ i, i + 1], we store a pointer to its associated leaf _i .

The certificates in this KDS are Z _i := R _i < R _{i +1} , i = 1 , , 2 n ˆ 1. The proof remains valid until two endpoints swap position in array R . In that case, exactly two certificates are affected. The ranks of all other interval endpoints remain the same, so they are associated with the same nodes in the tree (in other words, their fragment lists remain the same).

Let s be one of the two intervals affected by an endpoint swap. ^[1] There are four possible cases for which endpoints have swapped and how. Consider the one where before s = [ i, j ] and after the swap s = [ i, j + 1] (and analogously for the other segment).

The nave update algorithm would just delete both segments from all nodes (with the help of array ), and then sift them top-down through the tree. This would yield an O (log n ) complexity.

But we can do better. The idea is to augment the segment s = [ i, j ] by just the EI [ j, j + 1], and then just update the tree starting with _j , which is the leaf for [ j, j + 1], and which is now covered by s , too. The pseudocode shown in Algorithm 8.3 gives more details.

Algorithm 8.3: Updating a kinetic segment tree.

1:












j


{leaf of [

j, j

+ 1]}
2:

repeat

3:






sibling of




4:

if


s




S

(




)

then

5:                    delete

s

from

S

(




)
6:






parent(




)
7:

end if

8:

until


s





S

(




)
9: insert

s

into

S

(




)

Analogously, we can traverse the segment tree bottom-up in order to augment the other segment by an EI. Note that the test in Step 4 is necessarily false if is a left child.

The running time of Algorithm 8.3 is O ( h ), where h is the height of the node that gets s attached, i.e., [ j, j + 1] ˆˆ Int( ) and s ˆˆ S ( ) (after the update). This is made possible by the array , which allows us to perform Step 4 in Algorithm 8.3 in time O (1). When starting with the leaf of the EI, we just need to inspect the front/back of , and then we work our way through .

Lemma 8.1. Let S be a set of n moving segments on the real line . There is a kinetic segment tree with O ( n log n ) space, which can be updated in expected time O (1) when an event occurs (i.e., two endpoints swap position). The worst-case time is still O (log n ) . The KDS is local and efficient.

Locality and efficiency are given, since any segment participates in at most four certificates, and there are no internal events. The O (1) time bound can be proven fairly easily by showing that the average height in a balanced tree is O (1).

Figure 8.2 shows an example how the labeling changes as a result of an event.

Figure 8.2: An example of a segment tree over four segments. The dashed segments show the segments 4 and 2, respectively, after two of their endpoints have swapped position. The changes in the tree are highlighted with dashed boxes.

^[1] We omit the case where both endpoints belong to the same interval, as this is fairly easy to deal with.