How to find the smallest interval containing a set of values ​​modulo N?

Question

The first 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 all containsv[i]?

Note: the interval can be on both sides, about 0.

Abstract problem description:

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

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

This is trivial in 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 is the best way to find c and d for a finite scale (modulo N) and the distance definition above?

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

Answer 1

Hm, :

• [0, N)
• ( )
• neigborung :
  3.1. ( - )
  3.2 (, ​​ + N)
• , - , - , 3.

? , - :) , - , .

Answer 2

, , , d , 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;
}

, , , d > N/4?

Answer 3

.

v, , .

- :

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

Answer 4

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