Get this book -> Problems on Array: For Interviews and Competitive Programming

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:

- Get the coordinates of all line segments.
- 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.
- Sort them as individual points in ascending order along with the variable assigned to them and store them in an array.
- Suppose we encounter same coordinate values, say we (5,f) and (5,t); variable 'f' holds more weightage i.e (5,f) > (5,t).
- Traverse the length of the array and keep track of overlapping segments using a variable
*counter*. - Compute the difference between present and previous points.
- If counter is greater than zero, add the computed difference into result.
- If the variable assigned to present point is 't', decrement counter by 1 else increase counter by 1.
- If count is zero, the value in result is as it is and no changes are made in that iteration.
- 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[ ].