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

В геометрии такси длины красного, синего, зеленого и желтого путей равны 12 , то есть расстоянию такси между противоположными углами, и все четыре пути являются кратчайшими. Вместо этого в евклидовой геометрии красный, синий и желтый пути по-прежнему имеют длину 12 , но зеленый путь — это уникальный кратчайший путь, длина которого равна евклидову расстоянию между противоположными углами, 6√2 ≈ 8,49 .

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

Расстояние такси также иногда называют прямолинейным расстоянием или L. ¹ расстояние (см . L ^п космос ). Эта геометрия используется в регрессионном анализе с 18 века и часто называется LASSO . Его геометрическая интерпретация восходит к неевклидовой геометрии XIX века и принадлежит Герману Минковскому .

В двумерном реальном координатном пространстве $\mathbb {R} ^{2},$ расстояние такси между двумя точками $(x_{1},y_{1})$ и $(x_{2},y_{2})$ является $\left|x_{1}-x_{2}\right|+\left|y_{1}-y_{2}\right|$. То есть это сумма абсолютных значений разностей по обеим координатам.

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

Расстояние такси, $d_{\text{T}}$, между двумя точками $\mathbf {p} =(p_{1},p_{2},\dots ,p_{n}){\text{ and }}\mathbf {q} =(q_{1},q_{2},\dots ,q_{n})$ в n -мерном вещественном координатном пространстве с фиксированной декартовой системой координат есть сумма длин проекций отрезка между точками на оси координат . Более формально, $$d_{\text{T}}(\mathbf {p} ,\mathbf {q} )=\left\|\mathbf {p} -\mathbf {q} \right\|_{\text{T}}=\sum _{i=1}^{n}\left|p_{i}-q_{i}\right|$$Например, в $\mathbb {R} ^{2}$, расстояние такси между $\mathbf {p} =(p_{1},p_{2})$ и $\mathbf {q} =(q_{1},q_{2})$ является $\left|p_{1}-q_{1}\right|+\left|p_{2}-q_{2}\right|.$

История

Л ​ ¹ Метрика была использована в регрессионном анализе как мера согласия в 1757 году Роджером Джозефом Босковичем . Интерпретация его как расстояния между точками в геометрическом пространстве относится к концу 19 века и развитию неевклидовой геометрии . Примечательно, что он появился в 1910 году в работах Фригеса Риса и Германа Минковского . Формализация L ^п Пространства , которые включают в себя геометрию такси как особый случай, принадлежат Риссу. Развивая геометрию чисел , Герман Минковский установил неравенство Минковского , утверждая, что эти пространства определяют нормированные векторные пространства .

Название «геометрия такси» было введено Карлом Менгером в буклете 1952 года « Вам понравится геометрия» , сопровождавшем выставку геометрии, предназначенную для широкой публики в Музее науки и промышленности в Чикаго.

Характеристики

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

Сферы

Точки сетки на круге в геометрии такси, поскольку сетка становится более мелкой.

В любом метрическом пространстве сфера представляет собой набор точек, находящихся на фиксированном расстоянии ( радиусе ) от определенной центральной точки. В то время как евклидова сфера круглая и вращательно-симметричная, на расстоянии такси форма сферы представляет собой перекрестный многогранник , n -мерное обобщение правильного октаэдра , точки которого $\mathbf {p}$ удовлетворить уравнение:

$d_{\text{T}}(\mathbf {p} ,\mathbf {c} )=\sum _{i=1}^{n}|p_{i}-c_{i}|=r,$

где $\mathbf {c}$ — центр, а r — радиус. Очки $\mathbf {p}$ на единичной сфере , сфере радиуса 1 с центром в начале координат , удовлетворяют уравнению ${\textstyle d_{\text{T}}(\mathbf {p} ,\mathbf {0} )=\sum _{i=1}^{n}|p_{i}|=1.}$

В двумерной геометрии такси сфера (называемая кругом ) представляет собой квадрат, ориентированный по диагонали к осям координат. На изображении справа красным цветом показан набор всех точек квадратной сетки с фиксированным расстоянием от синего центра. По мере того, как сетка становится более мелкой, красных точек становится больше и в пределе они стремятся к сплошному наклоненному квадрату. Таксиевая длина каждой стороны равна 2 р , поэтому длина окружности равна 8 р . Таким образом, в геометрии такси значение аналога постоянной окружности π — отношения длины окружности к диаметру — равно 4.

Замкнутый шар (или закрытый диск в двумерном случае) представляет собой заполненную сферу, набор точек, находящихся на расстоянии меньшем или равном радиусу от определенного центра. Для клеточных автоматов на квадратной сетке диск такси - это окрестность фон Неймана диапазона r его центра.

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

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

Длина дуги

Позволять $y=f(x)$ быть непрерывно дифференцируемой функцией. Позволять $s$ такси длиной дуги на графике быть $f$ на некотором интервале $[a,b]$. Разобьем интервал на равные бесконечно малые подинтервалы и пусть $\Delta s_{i}$ быть длиной такси $i^{\text{th}}$ субдуга. Затем

$$\Delta s_{i}=\Delta x_{i}+\Delta y_{i}=\Delta x_{i}+|f(x_{i})-f(x_{i-1})|.$$

По теореме о среднем значении существует некоторая точка $x_{i}^{*}$ между $x_{i}$ и $x_{i-1}$ такой, что $f(x_{i})-f(x_{i-1})=f'(x_{i}^{*})dx_{i}$. Тогда предыдущее уравнение можно записать

$$\Delta s_{i}=\Delta x_{i}+|f'(x_{i}^{*})|\Delta x_{i}=\Delta x_{i}(1+|f'(x_{i}^{*})|).$$

Затем $s$ задается как сумма каждого раздела $s$ на $[a,b]$ поскольку они становятся сколь угодно малыми .

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

${\begin{aligned}s&=\lim _{n\rightarrow \infty }\sum _{i=1}^{n}\Delta x_{i}(1+|f'(x_{i}^{*})|)\\&=\int _{a}^{b}1+|f'(x)|\,dx\end{aligned}}$

Чтобы проверить это, возьмем круг такси радиусом $r$ сосредоточено в начале координат. Его кривая в первом квадранте определяется выражением $f(x)=-x+r$ чья длина

$$s=\int _{0}^{r}1+|-1|dx=2r$$

Умножив это значение на $4$ для учета остальных квадрантов дает $8r$, что соответствует длине окружности такси. Теперь возьмем евклидову окружность радиуса $r$ с центром в начале координат, что определяется выражением $f(x)={\sqrt {r^{2}-x^{2}}}$. Длина его дуги в первом квадранте определяется выражением

$${\begin{aligned}s&=\int _{0}^{r}1+|{\frac {-x}{\sqrt {r^{2}-x^{2}}}}|dx\\&=x+{\sqrt {r^{2}-x^{2}}}{\bigg |}_{0}^{r}\\&=r-(-r)\\&=2r\end{aligned}}$$

Учет остальных квадрантов дает $4\times 2r=8r$ снова. Следовательно, длина окружности такси и евклидова круга в метрике такси равны. Действительно, для любой функции $f$ монотонный и дифференцируемый с непрерывной производной на интервале $[a,b]$, длина дуги $f$ над $[a,b]$ является $(b-a)+\mid f(b)-f(a)\mid$.

Конгруэнтность треугольника

Два прямоугольных равнобедренных треугольника такси. Три угла и два катета равны, а треугольники не равны. Следовательно, ASASA не является теоремой сравнения в геометрии такси.

Два треугольника равны тогда и только тогда, когда три соответствующие стороны равны по расстоянию и три соответствующих угла равны по мере. Существует несколько теорем, гарантирующих конгруэнтность треугольников в евклидовой геометрии, а именно «Угол-Угол-Сторона» (AAS), «Угол-Сторона-Угол» (ASA), «Сторона-Угол-Сторона» (SAS) и «Сторона-Сторона-Сторона» (SSS). Однако в геометрии такси только SASAS гарантирует конгруэнтность треугольников.

Возьмем, к примеру, два прямоугольных равнобедренных треугольника такси, углы которых составляют 45-90-45. Два катета обоих треугольников имеют длину такси 2, но гипотенузы не равны. Этот контрпример исключает AAS, ASA и SAS. Он также исключает AASS, AAAS и даже ASASA. Наличие трех равных углов и двух сторон не гарантирует совпадение треугольников в геометрии такси. Следовательно, единственной теоремой о конгруэнтности треугольников в геометрии такси является SASAS, где все три соответствующие стороны должны быть конгруэнтны и как минимум два соответствующих угла должны быть конгруэнтны. Этот результат обусловлен главным образом тем, что длина отрезка зависит от его ориентации в геометрии такси.

Приложения

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

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

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

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

См. также

Сравнение чебышевского, евклидова и таксистного расстояний для гипотенузы треугольника 3-4-5 на шахматной доске

• Расстояние Чебышева
• Расстояние Хэмминга – количество битов, различающихся между двумя строками двоичных цифр.
• Расстояние Ли
• Ортогональная выпуклая оболочка - минимальное надмножество, которое пересекает каждую линию, параллельную оси, в интервале.
• Лестничный парадокс - Парадокс, заключающийся в том, что предел длин все более тонких «лестничных кривых» не стремится к длине диагонального отрезка, к которому стремятся кривые.

Дальнейшее чтение

• Гарднер, Мартин (1997). «10. Геометрия такси» . Последние развлечения . Коперник. стр. 159–176. ISBN  0-387-94929-1 .
• Краузе, Юджин Ф. (1975). Геометрия такси . Аддисон-Уэсли. ISBN  0201039346 . Перепечатано Дувром (1986), ISBN   0-486-25202-7 .

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

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