Вопрос о типе ближайшей точки решетки

Question

Я не могу найти решение этой проблемы.Пусть Z ^ 2 будет целочисленной решеткой в ​​R ^ 2.Учитывая рациональный луч (имеется в виду вектор с рациональным наклоном), существует ли быстрый метод для вычисления ближайшей точки решетки к этому вектору в терминах ортогонального расстояния?Можно ли этот метод обобщить на гиперплоскость в R ^ n?

Answer 1

Ваш вопрос не выглядит четко определенным.Как вы определяете расстояние до вектора?Если вы запрашиваете самое близкое расстояние от решетки до линии, направление которой является рациональным вектором (как предполагает ваше обобщение), тогда ответ равен нулю благодаря рациональности: ваше направление D = (n1 / d1, n2/ d2).Тогда точка (d2 * n1, d1 * n2) находится на прямой.

Для наименьшего ненулевого расстояния:

Можно считать, что d1 =d2 = d: D = (n1 / d, n2 / d) (который вы можете получить, установив, например, d = d1 * d2).Теперь возможные расстояния от решетки единичной сетки до линии имеют вид (Z * n1 + Z * n2) / d = (Z * gcd (n1, n2)) / d, где Z - множество целых чисел.(Это является следствием теоремы Безу).Таким образом, минимальное ненулевое расстояние равно gcd (n1, n2) / d, где gcd (.,.) Дает наибольший общий делитель двух целых чисел.