3

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

Curd
  • 12,169
  • 3
  • 35
  • 49
  • What is v[i] - an integer? An ordered pair [start_degree, end_degree]? – mbeckish Jul 10 '09 at 20:18
  • v[i] is one measured value (integer or real doesn't matter). Lets suppose all values are stored in an array v. – Curd Jul 10 '09 at 20:25
  • What's the purpose? Maybe http://stackoverflow.com/questions/491738/how-do-you-calculate-the-average-of-a-set-of-angles/491769 is relevant? – starblue Jul 11 '09 at 06:30

4 Answers4

5

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.

Mikhail Churbanov
  • 4,436
  • 1
  • 28
  • 36
  • Ok, slowly I think I get it. Maybe you could have described step 3 better: "find neigborung pair...". That's why you sorted in step 2. Then, yes, it actually becomes obvious. – Curd Jul 10 '09 at 20:55
  • Sorry, I not good enough to express my thought in english freely :) However -- some bottlenecks -- i lied you can't using Tom Ritter's dist in this algorithm. (1) You need always subtract (next - previous) (2) the last pair should be (last; first + N) – Mikhail Churbanov Jul 10 '09 at 21:16
  • I believe that if you had this set: { 1, 3, 359 }, your algorithm would return [1, 359] as the smallest interval, where it should be [359, 3]. – Seth Jul 10 '09 at 21:19
  • Why? We have cycling through zero -- thus [359; 3] - is 4 degrees, and [1; 359] - only two - it's smaller. There will be no challenge without cycling :) – Mikhail Churbanov Jul 10 '09 at 21:24
  • But [1, 359] doesn't include 3 :) – Seth Jul 10 '09 at 21:27
  • My algo returns [359, 3], i've checked it :) – Mikhail Churbanov Jul 10 '09 at 21:35
  • I understood -- statment about dist confused you, however in comments i said that you should use other way... so I'll edit answer better. – Mikhail Churbanov Jul 10 '09 at 21:37
  • +1, This is a very elegant solution, and "find the biggest part of the pie and eat it" is an excellent description. :-) – ShreevatsaR Jul 10 '09 at 22:42
0

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?

Curd
  • 12,169
  • 3
  • 35
  • 49
0

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);
}
Seth
  • 45,033
  • 10
  • 85
  • 120
  • No. My distance function is fine and it works perfectly (also close to 0 and 360). What I am looking for is a good (ideally O(n)) algorithm to find c and d. – Curd Jul 10 '09 at 22:19
  • Guess you mean "compute the distance between each _pair_ of elements". Ok. This is about what Mihail proposed. This, however, takes O(n*(n-1)) (if n is the number of values). – Curd Jul 10 '09 at 22:23
0
angle = max(v) - min(v)
return angle if angle <=180 else 360 - angle # to get the smallest absolute value
H.Muster
  • 9,297
  • 1
  • 35
  • 46
Paddy3118
  • 4,704
  • 27
  • 38