In this article, we will dive deep into Klee's algorithm and understand it better. Klee's algorithm is used to find the union of overlapping line segments when projected on a line.

Table of contents

• Introduction
• Algorithm
• Example
• Implementation
• Complexity analysis
  
  

Introduction

Let us start with a question. Say that we have a collection of intervals on the real line. How quickly can the length of their union be found?

In the above image, we find three line segments whose starting and ending coordinates are given. These can be moved only in the vertical axis and not in the horizontal axis. In that case, what will be the maximum length of the resulting line segment when we join them together by moving the orange line segment upward as denoted?

As an attempt at finding the answer for this question, Klee's algorithm was born.This algorithm was given by an American mathematician named Victor Klee in the year 1977. This algorithm was proved to be asympotically optimal and it was also found that a better solution than this algorithm for the above mentioned problem can be found. Later on many of them came to ponder on this question considering various multidimensional shapes. This is christened as the famous Klee's measure problem in computational geometry.

Algorithm

The steps followed in the execution of this algorithm are as follows:

1. Get the coordinates of all line segments.
2. Among the set of coordinates, assign 't' for ending points and 'f' for starting points where we consider 't' and 'f' to be True and False.
3. Sort them as individual points in ascending order along with the variable assigned to them and store them in an array.
4. Suppose we encounter same coordinate values, say we (5,f) and (5,t); variable 'f' holds more weightage i.e (5,f) > (5,t).
5. Traverse the length of the array and keep track of overlapping segments using a variable counter.
6. Compute the difference between present and previous points.
7. If counter is greater than zero, add the computed difference into result.
8. If the variable assigned to present point is 't', decrement counter by 1 else increase counter by 1.
9. If count is zero, the value in result is as it is and no changes are made in that iteration.
10. The final result gives the maximum length of the union of the given segments.
    
    

Example

Let us see an example of how Klee's algorithm works.

Input coordinates: (1,6) , (5,9) , (10,15)

Segment 1: (1,6)
Segment 2: (5,9)
Segment 3: (10,15)

points=[] //to store the coordinates
n=3 //the number of segments
result=0
counter=0

for i=0, points[0]={1,f}
points[1]={6,t}
for i=1, points[2]={5,f}
points[3]={9,t}
for i=2, points[4]={10,f}
points[5]={15,t}

points= [{1,f} {6,t} {5,f} {9,t} {10,f} {15,t}]

//After sorting
points= [{1,f} {5,f} {6,t} {9,t} {10,f} {15,t}]

//traversing the length of points[] to compute result
for i=0 , result=0
counter=1 // variable='t'
for i=1 , result=4 //difference: 5-1=4 , result: 0+4=4
counter=2 // variable='t'
for i=2 , result=5 //difference: 6-5=1 , result: 4+1=5
counter=1 // variable='f'
for i=3 , result=8 //difference: 9-6=3 , result: 5+3=8
counter=0 // variable='f'
for i=4 , result=8 //result is not updated since counter was 0
counter=1 // variable='f'
for i=5 , result=13 //difference: 10-15=5 , result: 5+8=13
counter=0 // variable='f'

final result = 13

Implementation

Let us now see the implementation of Klee's algorithm in various coding languages.

Python implementation

• Function to execute the algorithm

def segmentUnionLength(segments):
    n = len(segments)
     
    # Initialing list to store the points
    points = [None] * (n * 2)
     
    # Vector to store starting and ending points
    for i in range(n):
        points[i * 2] = (segments[i][0], False)
        points[i * 2 + 1] = (segments[i][1], True)
         
    # Sorting the points
    points = sorted(points, key=lambda x: x[0])
     
    # Initialiing result and counter variables
    result = 0
    counter = 0
     
    # Traversing through the points[]
    for i in range(0, n * 2):
       
        # Adding the difference between previous and current point.
        if (i > 0) & (points[i][0] > points[i - 1][0]) &  (counter > 0):
            result += (points[i][0] - points[i - 1][0])
             
        # If this is an ending point decrement counter by 1
        if points[i][1]:
            counter -= 1
        # If this is a starting point increment counter by 1
        else:
            counter += 1
    return result

This function takes in the list of coordinates as inputs and performs all the steps stated above and returns the final result after executing Klee's algorithm.

• Driver code

if __name__ == '__main__':
    segments = [(1, 6), (5, 9), (10, 15)]
    print(" The maximum length of union of the segments is: ")
    print(segmentUnionLength(segments))

This is the driver code where the list or coordinates are specified and the result of segmentUnionLength( ) function is printed.

• Output

The maximum length of union of the segments is:
13

C++ implementation

Similar to the python implementation, In C++ too, we define a function to execute the algorithm.

• Function to find the length after taking union of all segments

int find_union(vector<pair<int,int>> vect) 
{ 
  int size = vect.size(); 
  // Vectors to store starting and ending points
  vector <pair <int, bool> > endpoints(size * 2); 
  for (int i = 0; i < size; i++) 
  { 
    endpoints[i*2]  = make_pair(vect[i].first, false); 
    endpoints[i*2 + 1] = make_pair(vect[i].second, true); 
  } 
  // Sorting all endpoints
  sort(endpoints.begin(), endpoints.end()); 
  //Initialising variables 
  int result = 0; 
  int counter = 0; 
  // Traverse through all points 
  for (int i=0; i<size*2; i++) 
  { 
    // Adding the difference between previous and current point 
    if (counter) 
      result+=(endpoints[i].first - endpoints[i-1].first); 
    // If this is an ending point decrement counter by 1
    if (endpoints[i].second)
      counter--;
    //If this is an starting point increment counter by 1
    else
      counter++; 
  } 
  return result; 
} 

• Main function

int main() 
{ 
  //Initialising vector (pairs)
  vector< pair <int,int> > vect; 
  //Inserting endpoints of line segments
  vect.push_back(make_pair(1, 6)); 
  vect.push_back(make_pair(5, 9)); 
  vect.push_back(make_pair(10, 15)); 
  //Calling find_union() function and assigning its output to a variable
  int result=find_union(vect);
  //Printing result
  cout<<"Final length after taking union of all segments = " 
      <<ans<<endl; 
  return 0; 
} 

• Output

Final length after taking union of all segments=13

Complexity analysis

Klee's algorithm has a time complexity of O(N(log(N))) where N is the size of the points[]. It has the mentioned time complexity as it uses sorting. The space complexity of this algorithm will be O(2n) where n is the number of coordinate sets since we break dowm the coordinates and store them individually or O(N) where N is the size of points[ ].