Геометрия такси

Тип геометрии с использованием метрики Manhattan или L1 Taxicab геометрия в сравнении с евклидовым расстоянием: в геометрии такси красный, желтый и синий пути имеют одинаковую длину кратчайшего пути, равную 12. В евклидовой геометрии зеленая линия имеет длину $6\; 2\; \approx \; 8,49\; \{\backslash \; displaystyle\; 6\; \{\backslash \; sqrt\; \{2\}\}\; \backslash \; приблизительно\; 8,49\}$и является уникальным кратчайшим путем.

A геометрия такси - это форма геометрии, в которой обычная функция расстояния или метрика из евклидовой геометрии заменяется новой метрикой, в которой расстояние между двумя точками является суммой абсолютных разностей их Декартовы координаты. Показатель такси также известен как прямолинейное расстояние, L1расстояние, L расстояние или $\ell \; 1\; \{\backslash \; displaystyle\; \backslash \; ell\; \_\; \{\; 1\}\}$norm (см. L пробел ), snake distance, городской квартал, Манхэттенское расстояние или Манхэттенская длина, с соответствующими вариациями названия геометрии. Последние названия ссылаются на сетку большинства улиц на острове Манхэттен, которая определяет кратчайший путь, по которому машина может проехать между двумя перекрестками в районе иметь длину, равную расстоянию перекрестков в геометрии такси.

Геометрия использовалась в регрессионном анализе с 18 века, и сегодня ее часто называют LASSO. Геометрическая интерпретация относится к неевклидовой геометрии 19 века и принадлежит Герману Минковскому.

• 1 Формальное определение
• 2 Свойства
  • 2.1 Круги
• 3 Приложения
  • 3.1 Измерение расстояний в шахматах
  • 3.2 Сжатое зондирование
  • 3.3 Различия в частотных распределениях
• 4 История
• 5 См. Также
• 6 Примечания
• 7 Ссылки
• 8 Внешние ссылки

Расстояние такси, $d\; 1\; \{\backslash \; displaystyle\; d\_\; \{1\}\}$, между двумя векторами $p,\; q\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{p\},\; \backslash \; mathbf\; \{q\}\}$в n-мерном вещественном векторном пространстве с фиксированной декартовой системой координат, - это сумма длин проекций отрезка отрезка между точками на оси координат . Более формально

$d\; 1\; (p,\; q)\; =\; \Vert \; p\; -\; q\; \Vert \; 1\; =\; \sum \; i\; =\; 1\; n\; |\; p\; i\; -\; q\; i\; |,\; \{\backslash \; displaystyle\; d\_\; \{1\}\; (\backslash \; mathbf\; \{p\},\; \backslash \; mathbf\; \{q\})\; =\; \backslash \; |\; \backslash \; mathbf\; \{p\}\; -\; \backslash \; mathbf\; \{q\}\; \backslash \; |\; \_\; \{1\}\; =\; \backslash \; sum\; \_\; \{i\; =\; 1\}\; ^\; \{n\}\; |\; p\_\; \{i\}\; -q\_\; \{i\}\; |,\}$

где $(p,\; q)\; \{\backslash \; displaystyle\; (\backslash \; mathbf\; \{p\},\; \backslash \; mathbf\; \{q\})\}$- это векторы

$p\; =\; (p\; 1,\; p\; 2,\dots ,\; pn)\; и\; q\; =\; (q\; 1,\; q\; 2,\dots ,\; qn)\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{p\}\; =\; (p\_\; \{1\; \},\; p\_\; \{2\},\; \backslash \; dots,\; p\_\; \{n\})\; \{\backslash \; text\; \{and\}\}\; \backslash \; mathbf\; \{q\}\; =\; (q\_\; \{1\},\; q\_\; \{2\},\; \backslash \; dots,\; q\_\; \{n\})\; \backslash ,\}$

Например, в плоскости расстояние такси между $(p\; 1,\; p\; 2)\; \{\backslash \; displaystyle\; (p\_\; \{1\},\; p\_\; \{2\})\}$и $(q\; 1,\; q\; 2)\; \{\backslash \; displaystyle\; (q\_\; \{1\},\; q\_\; \{2\})\}$равно $|\; p\; 1\; -\; q\; 1\; |\; +\; |\; p\; 2\; -\; q\; 2\; |.\; \{\backslash \; displaystyle\; |\; p\_\; \{1\}\; -q\_\; \{1\}\; |\; +\; |\; p\_\; \{2\}\; -q\_\; \{2\}\; |.\}$

Расстояние такси зависит от поворота системы координат, но не зависит от его отражения относительно координатной оси или его смещения. Геометрия такси удовлетворяет всем аксиомам Гильберта (формализация евклидовой геометрии ) за исключением аксиомы стороны-угла-стороны, как два треугольника с одинаковой «длиной» две стороны и одинаковый угол между ними обычно не конгруэнтны, если только упомянутые стороны не параллельны.

Круги

Круги в дискретной и непрерывной геометрии такси

A круг - это набор точек с фиксированным расстоянием, называемым радиусом, от точки, называемой центром. В геометрии такси расстояние определяется другой метрикой, чем в евклидовой геометрии, и форма кругов также изменяется. Круги такси - это квадраты со сторонами, ориентированными под углом 45 ° к осям координат. На изображении справа показано, почему это так, красным цветом показаны все точки с фиксированным расстоянием от центра, показанные синим цветом. По мере уменьшения размеров городских кварталов количество точек становится больше и они превращаются в повернутый квадрат в непрерывной геометрии такси. Каждая сторона будет иметь длину $2\; r\; \{\backslash \; displaystyle\; \{\backslash \; sqrt\; \{2\}\}\; r\}$с использованием евклидовой метрики, где r - радиус круга, его длина в геометрия такси 2кг. Таким образом, длина окружности равна 8р. Таким образом, значение геометрического аналога $\pi \; \{\backslash \; displaystyle\; \backslash \; pi\}$ равно 4 в этой геометрии. Формула единичного круга в геометрии такси: $|\; х\; |\; +\; |\; y\; |\; =\; 1\; \{\backslash \; displaystyle\; |\; x\; |\; +\; |\; y\; |\; =\; 1\}$в декартовых координатах и

$r\; =\; 1\; |\; грех\; \; \theta \; |\; +\; |\; cos\; \; \theta \; |\; \{\backslash \; displaystyle\; r\; =\; \{\backslash \; frac\; \{1\}\; \{|\; \backslash \; sin\; \backslash \; theta\; |\; +\; |\; \backslash \; cos\; \backslash \; theta\; |\}\}\}$

в полярных координатах.

круг радиуса 1 (с использованием этого расстояния) это окрестность фон Неймана его центра.

Окружность радиуса r для расстояния Чебышева (L∞метрика ) на плоскости также является квадратом со стороной 2r, параллельной осям координат, поэтому можно увидеть плоское расстояние Чебышева как эквивалент вращением и масштабированием до планарного расстояния такси. Однако эта эквивалентность между показателями L 1 и L ∞ не распространяется на более высокие измерения.

Всякий раз, когда каждая пара в наборе этих кругов имеет непустое пересечение, существует точка пересечения для всего набора; следовательно, манхэттенское расстояние образует инъективное метрическое пространство .

Меры расстояний в шахматах

В chess расстояние между квадратами на шахматная доска для ладей измеряется расстоянием такси; короли и королевы используют расстояние Чебышева, а слоны используют расстояние такси (между квадратами одного цвета) на шахматной доске, повернутой на 45 градусов, т.е. с его диагоналями в качестве координатных осей. Чтобы добраться от одной клетки до другой, только королям требуется количество ходов, равное их соответствующему расстоянию; для ладей, ферзей и слонов требуется один или два хода (на пустой доске и при условии, что этот ход вообще возможен в случае слона).

Сжатое измерение

При решении недоопределенной системы линейных уравнений, член регуляризации для вектора параметров выражается в терминах $\ell \; 1\; \{\backslash \; displaystyle\; \backslash \; ell\; \_\; \{1\}\}$-норма (геометрия такси) вектора. Этот подход появляется в структуре восстановления сигнала под названием сжатое зондирование.

Различия частотных распределений

Геометрия такси может использоваться для оценки различий в дискретных частотных распределениях. Например, в сплайсинге РНК позиционные распределения гексамеров, которые отображают вероятность появления каждого гексамера на каждом заданном нуклеотиде рядом с сайтом сплайсинга, можно сравнить с L1-расстояние. Каждое распределение положений может быть представлено в виде вектора, где каждая запись представляет вероятность того, что гексамер начинается с определенного нуклеотида. Большое расстояние L1 между двумя векторами указывает на значительную разницу в характере распределений, в то время как небольшое расстояние означает распределения схожей формы. Это эквивалентно измерению площади между двумя кривыми распределения, поскольку площадь каждого сегмента представляет собой абсолютную разницу между вероятностями двух кривых в этой точке. При суммировании для всех сегментов он дает ту же меру, что и расстояние L1.

Метрика L использовалась в регрессионном анализе в 1757 г. Роджер Джозеф Боскович. Геометрическая интерпретация датируется концом 19 века и развитием неевклидовой геометрии, в частности, Германом Минковским и его неравенством Минковского, из которых эта геометрия является особый случай, особенно используемый в геометрии чисел, (Minkowski 1910). Формализация L пробелов приписывается (Riesz 1910).

• Нормированное векторное пространство
• Метрика
• Ортогональная выпуклая оболочка
• Расстояние Хэмминга
• Загадка пятнадцати
• Случайное блуждание
• Манхэттенская проводка

• Краузе, Юджин Ф. (1987). Геометрия такси. Дувр. ISBN 978-0-486-25202-5.
• Минковский, Герман (1910). Geometrie der Zahlen (на немецком языке). Лейпциг и Берлин: Р. Г. Тойбнер. JFM 41.0239.03. MR 0249269. Проверено 6 октября 2019 г.
• Рис, Фриджес (1910). "Untersuchungen über Systeme integrierbarer Funktionen". Mathematische Annalen (на немецком языке). 69 (4): 449–497. doi : 10.1007 / BF01457637. hdl : 10338.dmlcz / 128558.

• Вайсштейн, Эрик У. «Метрика такси». MathWorld.
• Малькевич, Джо (1 октября 2007 г.). «Такси!». Американское математическое общество. Получено 6 октября 2019 г.