###

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:

- normalize all angles to [0, N)
- sort angles (minimum first)
- find neigborung pair with maximum distance:

3.1 You need always subtract (next - previous)

3.2 The last pair should be (last; first + N) - 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**

EmoticonEmoticon