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

Taxicab geometry

Геометрия такси в сравнении с евклидовым расстоянием: в геометрии такси красный, желтый и синий пути имеют одинаковую длину кратчайшего пути, равную 12. В евклидовой геометрии зеленая линия имеет длину.

{ displaystyle 6 { sqrt {2}} приблизительно 8,49}

и это единственный кратчайший путь.

А геометрия такси это форма геометрия в котором обычная функция расстояния или метрика из Евклидова геометрия заменяется новой метрикой, в которой расстояние между двумя точками - это сумма абсолютные различия от их Декартовы координаты. В метрика такси также известен как прямолинейное расстояние, L₁ расстояние, L¹ расстояние или ${ displaystyle ell _ {1}}$ норма (увидеть L^п Космос), змея расстояние, расстояние до городского квартала, Манхэттенское расстояние или Манхэттенская длина, с соответствующими вариациями в названии геометрии.^[1] Последние имена ссылаются на сетка большинства улиц на острове Манхэттен, который определяет кратчайший путь, по которому машина может пройти между двумя перекрестками в район иметь длину, равную расстоянию перекрестков в геометрии такси.

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

Формальное определение

Расстояние такси, ${ displaystyle d_ {1}}$ , между двумя векторами ${ Displaystyle mathbf {p}, mathbf {q}}$ в п-размерный настоящий векторное пространство с фиксированной Декартова система координат, - сумма длин выступов отрезок между точками на оси координат. Более формально

{ Displaystyle d_ {1} ( mathbf {p}, mathbf {q}) = | mathbf {p} - mathbf {q} | _ {1} = sum _ {i = 1} ^ {n} | p_ {i} -q_ {i} |,}

где ${ Displaystyle ( mathbf {p}, mathbf {q})}$ находятся векторов

{ displaystyle mathbf {p} = (p_ {1}, p_ {2}, dots, p_ {n}) { text {and}} mathbf {q} = (q_ {1}, q_ {2 }, точки, q_ {n}) ,}

Например, в самолет, расстояние такси между ${ displaystyle (p_ {1}, p_ {2})}$ и ${ displaystyle (q_ {1}, q_ {2})}$ является ${ displaystyle | p_ {1} -q_ {1} | + | p_ {2} -q_ {2} |.}$

Свойства

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

Круги

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

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

{ Displaystyle г = { гидроразрыва {1} {| грех тета | + | соз тета |}}}

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

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

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

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

Приложения

Меры дистанций в шахматах

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

Сжатое зондирование

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

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

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

История

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

Смотрите также

Заметки

^ Блэк, Пол Э. "Манхэттенское расстояние". Словарь алгоритмов и структур данных. Получено 6 октября, 2019.
^ Донохо, Дэвид Л. (23 марта 2006 г.). "Для большинства больших недоопределенных систем линейных уравнений минимальный ${ displaystyle ell _ {1}}$ -нормальное решение также является самым редким решением ". Сообщения по чистой и прикладной математике. 59 (6): 797–829. Дои:10.1002 / cpa.20132.
^ Лим, Киан Хуат; Феррарис, Лучиана; Filloux, Madeleine E .; Рафаэль, Бенджамин Дж .; Fairbrother, Уильям Г. (5 июля 2011 г.). «Использование позиционного распределения для идентификации элементов сплайсинга и прогнозирования дефектов процессинга пре-мРНК в генах человека». Труды Национальной академии наук Соединенных Штатов Америки. 108 (27): 11093–11098. Bibcode:2011PNAS..10811093H. Дои:10.1073 / pnas.1101135108. ЧВК 3131313. PMID 21685335.
^ Стиглер, Стивен М. (1986). История статистики: измерение неопределенности до 1900 г.. Издательство Гарвардского университета. ISBN 9780674403406. Получено 6 октября, 2019.

использованная литература

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

внешние ссылки

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

[1] Блэк, Пол Э. "Манхэттенское расстояние". Словарь алгоритмов и структур данных. Получено 6 октября, 2019.

[2] Донохо, Дэвид Л. (23 марта 2006 г.). "Для большинства больших недоопределенных систем линейных уравнений минимальный ${ displaystyle ell _ {1}}$ -нормальное решение также является самым редким решением ". Сообщения по чистой и прикладной математике. 59 (6): 797–829. Дои:10.1002 / cpa.20132.

[lim-3] Лим, Киан Хуат; Феррарис, Лучиана; Filloux, Madeleine E .; Рафаэль, Бенджамин Дж .; Fairbrother, Уильям Г. (5 июля 2011 г.). «Использование позиционного распределения для идентификации элементов сплайсинга и прогнозирования дефектов процессинга пре-мРНК в генах человека». Труды Национальной академии наук Соединенных Штатов Америки. 108 (27): 11093–11098. Bibcode:2011PNAS..10811093H. Дои:10.1073 / pnas.1101135108. ЧВК 3131313. PMID 21685335.

[Stigler1986-4] Стиглер, Стивен М. (1986). История статистики: измерение неопределенности до 1900 г.. Издательство Гарвардского университета. ISBN 9780674403406. Получено 6 октября, 2019.

[1]

[2]

[3]

[4]

Navigation