Как найти наименьший интервал, содержащий множество значений по модулю N?

Question

Первое практическое применение, которое привело меня к проблеме:

Учитывая набор угловых измерений v[i] в диапазоне [0,360) градусов, какой самый маленький интервал, содержащий все v[i]?

Примечание: интервал может быть с обеих сторон, близко к 0.

Абстрактное описание проблемы:

Для данного набора значений v[i], каковы значения c и d, такие что

• для всех i: dist(v[i],c) <= d и
• d как можно меньше и
• dist(x,y) = abs(((x-y + N/2 + N) mod N) - N/2)?

Это тривиально в открытом (бесконечном) масштабе, где dist(x,y) = abs(x-y):

calculate max and min of all v[i]
c = (max + min)/2;
d = (max - min)/2;

Но как лучше всего найти c и d для конечного масштаба (по модулю N) и определение расстояния, как указано выше?

Может быть, есть способ сделать это O (n) (если n - число значений)?

Answer 1

Хм, как насчет следующего:

1. нормализовать все углы до [0, N)
2. углы сортировки (сначала минимум)
3. найти пару соседей с максимальным расстоянием:
   3.1 Вам нужно всегда вычитать (следующий - предыдущий)
   3.2 Последняя пара должна быть (последняя; первая + N)
4. думаю, что вам нужна пара - используйте только противоположный угол, который вы нашли в шаге 3.

Я не прав? Другими словами, мое решение очевидно - вы просто найдете большую часть пирога и съедите его :) все, что осталось - это то, что вам нужно.

Answer 2

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

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

У меня есть собственное решение, однако я не совсем доволен им, так как предполагается, что 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?