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)?

Answer 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.

Answer 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?

Answer 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);
}

Answer 4

Seems like Mihail has it right.

Answer 5

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

• Paddy.