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

Hm, how about following:

  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[0]>=N/4 && v[0]<(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 »