Введение
Тип метрической геометрии
Такси-геометрия, или Манхэттенская геометрия, – это геометрия, в которой привычное евклидово расстояние игнорируется, а расстояние между двумя точками определяется как сумма абсолютных значений разностей их соответствующих декартовых координат, функция расстояния (или метрика), называемая расстоянием такси, манхэттенским расстоянием или расстоянием в городских кварталах. Название отсылает к острову Манхэттен или, в общем, к любому спланированному городу с прямоугольной сеткой улиц, где такси может двигаться только по направлениям сетки. В такси-геометрии расстояние между любыми двумя точками равно длине их кратчайшего пути по сетке. Это иное определение расстояния также приводит к иному определению длины кривой: отрезок прямой между любыми двумя точками имеет ту же длину, что и путь по сетке между этими точками, а не его евклидова длина. Расстояние такси также иногда называют прямоугольным расстоянием или L¹-расстоянием (см. Lp-пространство). Эта геометрия используется в регрессионном анализе с XVIII века и часто упоминается как LASSO. Её геометрическая интерпретация восходит к неевклидовой геометрии XIX века и принадлежит Германну Минковскому. В двухмерном реальном координатном пространстве расстояние между двумя точками (x₁, y₁) и (x₂, y₂) равно |x₂ - x₁| + |y₂ - y₁|. То есть, это сумма абсолютных значений разностей по обеим координатам.
Формальное определение
Расстояние такси, , между двумя точками в n-мерном реальном координатном пространстве с фиксированной декартовой системой координат, является суммой длин проекций отрезка прямой, соединяющего эти точки, на координатные оси. Более формально, например, в , расстояние такси между точками и равно .
История
Метрика L1 была использована в регрессионном анализе как мера качества подгонки в 1757 году Роджером Джозефом Босковичем. Интерпретация этой метрики как расстояния между точками в геометрическом пространстве относится к концу XIX века и развитию неевклидовых геометрий. В 1910 году она появилась в работах Фригеша Риеша и Германна Минковского. Формализация Lp-пространств, включающих геометрию такси как частный случай, приписывается Риешу. Разрабатывая геометрию чисел, Герман Минковский установил неравенство Минковского, утверждающее, что эти пространства определяют нормированные векторные пространства. Название «геометрия такси» было введено Карлом Менгером в 1952 году в брошюре «Вам понравится геометрия», сопровождавшей выставку геометрии, предназначенную для широкой публики в Музее науки и промышленности в Чикаго.
Свойства
Рассматриваемое как дополнительная структура, наложенная на евклидово пространство, расстояние Чебышёва (или такси) зависит от ориентации системы координат и изменяется при евклидовом вращении пространства, но не изменяется при сдвиге или отражении относительно осей координат. Геометрия Чебышёва удовлетворяет всем аксиомам Гильберта (формализации евклидовой геометрии), за исключением того, что понятие конгруэнтности углов нельзя определить так, чтобы оно точно соответствовало евклидову понятию, и при разумных определениях конгруэнтных углов Чебышёва, аксиома сторона-угол-сторона не выполняется, поскольку в общем случае треугольники с двумя конгруэнтными сторонами Чебышёва и конгруэнтным углом Чебышёва между ними не являются конгруэнтными треугольниками.
Сферы
В любом метрическом пространстве сфера представляет собой множество точек, находящихся на фиксированном расстоянии, называемом радиусом, от заданной центральной точки. В то время как евклидова сфера круглая и обладает вращательной симметрией, при использовании метрики такси (манхэттенского расстояния) форма сферы представляет собой перекрестный политоп – n-мерное обобщение правильного октаэдра, точки которого удовлетворяют уравнению: где – центр, а r – радиус. Точки на единичной сфере, то есть сфере радиуса 1 с центром в начале координат, удовлетворяют уравнению.
where is the center and r is the radius. Points on the unit sphere, a sphere of radius 1 centered at the origin, satisfy the equation
In two dimensional taxicab geometry, the sphere (called a circle) is a square oriented diagonally to the coordinate axes. The image to the right shows in red the set of all points on a square grid with a fixed distance from the blue center. As the grid is made finer, the red points become more numerous, and in the limit tend to a continuous tilted square. Each side has taxicab length 2r, so the circumference is 8r. Thus, in taxicab geometry, the value of the analog of the circle constant π, the ratio of circumference to diameter, is equal to 4. A closed ball (or closed disk in the 2 dimensional case) is a filled in sphere, the set of points at distance less than or equal to the radius from a specific center. For cellular automata on a square grid, a taxicab disk is the von Neumann neighborhood of range r of its center. A circle of radius r for the Chebyshev distance (L∞ metric) on a plane is also a square with side length 2r parallel to the coordinate axes, so planar Chebyshev distance can be viewed as equivalent by rotation and scaling to planar taxicab distance. However, this equivalence between L1 and L∞ metrics does not generalize to higher dimensions. Whenever each pair in a collection of these circles has a nonempty intersection, there exists an intersection point for the whole collection; therefore, the Manhattan distance forms an injective metric space.
В двумерной геометрии такси сфера (которая называется кругом) представляет собой квадрат, ориентированный по диагонали к координатным осям. Изображение справа показывает красным цветом множество всех точек на квадратной сетке, находящихся на фиксированном расстоянии от синего центра. По мере уплотнения сетки красных точек становится больше, и в пределе они стремятся к непрерывному наклонному квадрату. Каждая сторона имеет длину такси, равную 2r, поэтому периметр равен 8r. Таким образом, в геометрии такси значение аналога числа π, то есть отношения периметра к диаметру, равно 4. Замкнутый шар (или замкнутый диск в двумерном случае) – это заполненная сфера, множество точек, находящихся на расстоянии, меньшем или равном радиусу, от заданной центральной точки. Для клеточных автоматов на квадратной сетке диск такси является окрестностью фон Неймана радиуса r от его центра. Круг радиуса r для метрики Чебышева (L∞) на плоскости также является квадратом со стороной 2r, параллельной координатным осям, поэтому расстояние Чебышева на плоскости можно рассматривать как эквивалентное расстоянию такси с помощью вращения и масштабирования. Однако эта эквивалентность между метриками L1 и L∞ не распространяется на более высокие размерности. Если каждая пара округов в некотором наборе имеет непустое пересечение, то существует точка пересечения для всего набора; следовательно, расстояние Манхэттена формирует инъективное метрическое пространство.
where is the center and r is the radius. Points on the unit sphere, a sphere of radius 1 centered at the origin, satisfy the equation
In two dimensional taxicab geometry, the sphere (called a circle) is a square oriented diagonally to the coordinate axes. The image to the right shows in red the set of all points on a square grid with a fixed distance from the blue center. As the grid is made finer, the red points become more numerous, and in the limit tend to a continuous tilted square. Each side has taxicab length 2r, so the circumference is 8r. Thus, in taxicab geometry, the value of the analog of the circle constant π, the ratio of circumference to diameter, is equal to 4. A closed ball (or closed disk in the 2 dimensional case) is a filled in sphere, the set of points at distance less than or equal to the radius from a specific center. For cellular automata on a square grid, a taxicab disk is the von Neumann neighborhood of range r of its center. A circle of radius r for the Chebyshev distance (L∞ metric) on a plane is also a square with side length 2r parallel to the coordinate axes, so planar Chebyshev distance can be viewed as equivalent by rotation and scaling to planar taxicab distance. However, this equivalence between L1 and L∞ metrics does not generalize to higher dimensions. Whenever each pair in a collection of these circles has a nonempty intersection, there exists an intersection point for the whole collection; therefore, the Manhattan distance forms an injective metric space.
Длина дуги
Пусть — непрерывно дифференцируемая функция. Пусть — длина такси-дуги графика на некотором интервале. Разделим этот интервал на равные бесконечно малые подинтервалы, и пусть — длина такси-дуги -й подинтервала. Тогда, по теореме о среднем значении, существует некоторая точка между и такая, что Тогда предыдущее уравнение можно записать как:
By the mean value theorem, there exists some point between and such that Then the previous equation can be written
Then is given as the sum of every partition of on as they get arbitrarily small. To test this, take the taxicab circle of radius centered at the origin. Its curve in the first quadrant is given by whose length is
Multiplying this value by to account for the remaining quadrants gives , which agrees with the circumference of a taxicab circle. Now take the Euclidean circle of radius centered at the origin, which is given by Its arc length in the first quadrant is given by
Accounting for the remaining quadrants gives again. Therefore, the circumference of the taxicab circle and the Euclidean circle in the taxicab metric are equal. In fact, for any function that is monotonic and differentiable with a continuous derivative over an interval , the arc length of over is .
Тогда представляется как сумма длин всех подинтервалов на при их стремлении к бесконечно малым. Чтобы проверить это, рассмотрим такси-окружность радиуса с центром в начале координат. Её кривая в первом квадранте задается выражением Её длина равна
By the mean value theorem, there exists some point between and such that Then the previous equation can be written
Then is given as the sum of every partition of on as they get arbitrarily small. To test this, take the taxicab circle of radius centered at the origin. Its curve in the first quadrant is given by whose length is
Multiplying this value by to account for the remaining quadrants gives , which agrees with the circumference of a taxicab circle. Now take the Euclidean circle of radius centered at the origin, which is given by Its arc length in the first quadrant is given by
Accounting for the remaining quadrants gives again. Therefore, the circumference of the taxicab circle and the Euclidean circle in the taxicab metric are equal. In fact, for any function that is monotonic and differentiable with a continuous derivative over an interval , the arc length of over is .
Умножив это значение на для учета остальных квадрантов, получим , что соответствует окружности такси-окружности. Теперь рассмотрим евклидову окружность радиуса с центром в начале координат, которая задается выражением Длина её дуги в первом квадранте равна
By the mean value theorem, there exists some point between and such that Then the previous equation can be written
Then is given as the sum of every partition of on as they get arbitrarily small. To test this, take the taxicab circle of radius centered at the origin. Its curve in the first quadrant is given by whose length is
Multiplying this value by to account for the remaining quadrants gives , which agrees with the circumference of a taxicab circle. Now take the Euclidean circle of radius centered at the origin, which is given by Its arc length in the first quadrant is given by
Accounting for the remaining quadrants gives again. Therefore, the circumference of the taxicab circle and the Euclidean circle in the taxicab metric are equal. In fact, for any function that is monotonic and differentiable with a continuous derivative over an interval , the arc length of over is .
Учитывая остальные квадранты, получим снова. Следовательно, окружности такси-окружности и евклидовой окружности в такси-метрике равны. Более того, для любой монотонной и дифференцируемой функции с непрерывной производной на интервале , длина дуги на равна .
By the mean value theorem, there exists some point between and such that Then the previous equation can be written
Then is given as the sum of every partition of on as they get arbitrarily small. To test this, take the taxicab circle of radius centered at the origin. Its curve in the first quadrant is given by whose length is
Multiplying this value by to account for the remaining quadrants gives , which agrees with the circumference of a taxicab circle. Now take the Euclidean circle of radius centered at the origin, which is given by Its arc length in the first quadrant is given by
Accounting for the remaining quadrants gives again. Therefore, the circumference of the taxicab circle and the Euclidean circle in the taxicab metric are equal. In fact, for any function that is monotonic and differentiable with a continuous derivative over an interval , the arc length of over is .
Треугольная конгруэнтность
Два треугольника конгруэнтны тогда и только тогда, когда три соответствующие стороны равны по длине, а три соответствующих угла равны по величине. В евклидовой геометрии существует несколько теорем, гарантирующих конгруэнтность треугольников, а именно: угол-угол-сторона (AAS), угол-сторона-угол (ASA), сторона-угол-сторона (SAS) и сторона-сторона-сторона (SSS). Однако в геометрии такси только SASAS гарантирует конгруэнтность треугольников. Например, рассмотрим два прямоугольных равнобедренных треугольника в геометрии такси, углы которых равны 45, 90 и 45 градусов. Две катета обоих треугольников имеют такси-длину 2, но гипотенузы не конгруэнтны. Этот контрпример опровергает теоремы AAS, ASA и SAS. Он также опровергает AASS, AAAS и даже ASASA. Наличие трех равных углов и двух равных сторон не гарантирует конгруэнтность треугольников в геометрии такси. Следовательно, единственной теоремой конгруэнтности треугольников в геометрии такси является SASAS, где все три соответствующие стороны должны быть конгруэнтны, и по крайней мере два соответствующих угла должны быть равны по величине. Этот результат в основном обусловлен тем, что длина отрезка линии зависит от его ориентации в геометрии такси.
Сжатый датчик
При решении недоопределённой системы линейных уравнений, регуляризационный член для вектора параметров выражается через норму L1 (геометрию такси) этого вектора. Этот подход используется в области восстановления сигналов, известной как компрессионное измерение.
Разница в частотном распределении
Геометрия такси может быть использована для оценки различий в дискретных частотных распределениях. Например, при сплайсинге РНК позиционные распределения гексамеров, представляющие собой графики вероятности появления каждого гексамера в каждой данной позиции нуклеотида вблизи сайта сплайсинга, могут быть сравнены с использованием L1-расстояния. Каждое распределение позиций можно представить в виде вектора, где каждый элемент соответствует вероятности начала гексамера с определенного нуклеотида. Большое L1-расстояние между двумя векторами указывает на существенную разницу в характере распределений, а небольшое расстояние – на схожесть их формы. Это эквивалентно измерению площади между двумя кривыми распределения, поскольку площадь каждого сегмента равна абсолютной разнице между вероятностями этих кривых в данной точке. Суммирование площадей всех сегментов дает ту же величину, что и L1-расстояние.