Tutorial :How to find the smallest interval containing a set of values modulo N? Question:

First the practical application that led me to the problem:

Given a set of angle measurements `v[i]` in the range of [0,360) degrees, what is the smallest interval containing all `v[i]?`

Note: the interval may be on both sides, close around 0.

Abstract description of the problem:

For a given set of values `v[i]`, what are the values `c` and `d`, such that

• for all `i`: `dist(v[i],c) <= d` and
• `d` is as small as possible and
• `dist(x,y) = abs(((x-y + N/2 + N) mod N) - N/2)` ?

This is trivial on an open (infinite) scale, where `dist(x,y) = abs(x-y)`:

``calculate max and min of all v[i]  c = (max + min)/2;  d = (max - min)/2;  ``

But what's the best way to find c and d for a finite scale (modulo N) and a distance defintion as given above?

Is there maybe a way to do it O(n) (if n is the number of values)?

Solution:1

1. normalize all angles to [0, N)
2. sort angles (minimum first)
3. find neigborung pair with maximum distance:
3.1 You need always subtract (next - previous)
3.2 The last pair should be (last; first + N)
4. think that pair is what you need - only use opposite angle to that you found in step 3.

Am I wrong? In other words my solution is obvious -- you just find the biggest part of the pie and eat it :) all that left - is what you need.

Solution:2

I have an own solution, however, I am not quite satisfied with it as it assumes that d will never be larger than N/4:

``if(v>=N/4 && v<(3*N)/4)  {    calculate min and max of all v[i]    c = (max + min)/2;       d = (max - min)/2;  }  else  {    calculate min and max of all (v[i] + N/2) % N    c = ((max + min)/2 - N/2;     d = ((max - min)/2 - N/2;  }  ``

Any better solution, especially one that would work also if d turns out to be > N/4?

Solution:3

Your problem seems equivalent to finding the maximum distance between two of your angles.

You should just be able to iterate through your v set, compute the distance between each element, then find the largest distance.

You might try something like this for your distance function:

``void dist_mod_360(int a, int b)  {      const int n = 360;       return min((a - b) % n, (b - a) % n);  }  ``

Solution:4

``angle = max(v) - min(v)  return angle if angle <=180 else 360 - angle # to get the smallest absolute value  ``

Note:If u also have question or solution just comment us below or mail us on toontricks1994@gmail.com
Previous
Next Post »