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

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

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

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

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

Формальное определение [ править ]

Расстояние такси между двумя векторами в n- мерном реальном векторном пространстве с фиксированной декартовой системой координат является суммой длин проекций отрезка прямой между точками на оси координат . Более формально ${\ 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})}$

\mathbf {p} =(p_{1},p_{2},\dots ,p_{n}){\text{ and }}\mathbf {q} =(q_{1},q_{2},\dots ,q_{n})\,

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

Свойства [ править ]

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

Круги [ править ]

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

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

r={\frac {1}{|\sin \theta |+|\cos \theta |}}

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

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

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

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

Приложения [ править ]

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

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

Сжатое зондирование [ править ]

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

Различия в частотном распределении [ править ]

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

История [ править ]

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

См. Также [ править ]

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

Заметки [ править ]

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

Ссылки [ править ]

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

Внешние ссылки [ править ]

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

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

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

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

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

[1]