Вычисления с плавающей точкой и неравенство треугольника

Question

Я использую VPTree для оптимизации некоторых алгоритмов K-ближайших соседей.

VPTree требует, чтобы функция расстояния удовлетворяла неравенству треугольника.

Неравенство треугольника утверждает, что должно быть верно следующее:

distance(x,z) <= distance(x,y) + distance(y,z)

Одной из функций, используемых в нашей функции расстояния, является географическое расстояние в метрах, которое рассчитывается с помощью арифметики с плавающей запятой. Я обнаружил, что эта функция нарушает неравенство треугольника из-за неточных вычислений с плавающей запятой.

Например:

x = -90,-180
y = -90,-162
z = -81,-144
distance(x,z) = 1005162.6564502382
distance(x,y) = 1.2219041408558764E-10
distance(y,z) = 1005162.656450238
distance(x,y) + distance(y,z) = 1005162.6564502381

Очевидно, что неравенство треугольника в этом случае провалилось.

Я возился и обнаружил, что если я округлю расстояние в метрах ВНИЗ до следующего целого числа, то есть Math.floor() в java, а затем добавлю 5, результат, похоже, неожиданно удовлетворит неравенство треугольника во всех случаях. проверил.

Я проверил каждую комбинацию широта / долгота, которая кратна 10, то есть 20^6 комбинаций.

После этого изменения мы получаем следующие результаты для примера выше:

x = -90,-180
y = -90,-162
z = -81,-144
distance(x,z) = 1005167
distance(x,y) = 5
distance(y,z) = 1005167
distance(x,y) + distance(y,z) = 1005172

Очевидно, что в этом случае неравенство треугольника больше не нарушается.

Это кажется идеальным, поскольку 5 метров в нашем случае не имеют значения.

Я просто "заставляю" это работать, и все еще нарушаю какое-то требование неравенства треугольника или некоторое требование VPTrees? Это то, что является известным свойством поплавков?

Обратите внимание, что простое округление ВНИЗ без добавления 5 не работает.

Например:

x = -90,-180
y = -81,-180
z = -72,-180
distance(x,z) = 2009836.0
distance(x,y) = 1005162.0
distance(y,z) = 1004673.0
distance(x,y) + distance(y,z) = 2009835.0

И добавив 5:

x = -90,-180
y = -81,-180
z = -72,-180
distance(x,z) = 2009841.0
distance(x,y) = 1005167.0
distance(y,z) = 1004678.0
distance(x,y) + distance(y,z) = 2009845.0

Также обратите внимание, что я обнаружил, что это работает для любого вида арифметики с плавающей запятой, а не только для географического расстояния. Например, функция расстояния, которая вычисляет процент от некоторого максимального значения с помощью одной операции деления, при условии, что вы всегда округляете до определенного числа цифр и добавляете 5 к последней цифре.

Answer 1

Старая ветка, но не могу удержаться от ответа.

Ваш метод округления в меньшую сторону и добавления пяти может удовлетворять неравенству треугольника, но при этом расстояние между точкой и самой собой будет больше нуля. Что означает, что:

Расстояние (x, x) == 5

ИМО, это, вероятно, так же проблематично для VPTree, чем отказ от свойства неравенства треугольника.