On the location of geometrical medians of triangles

Full Text

1. ВВЕДЕНИЕ

Геометрическая (пространственная) медиана и некоторые ее обобщения широко используются в экономической теории, начиная с работ Вильгельма Лаунхардта и Альфреда Вебера по теории размещения производства (Murray, 2020, vol. 8, p. 237–243). Теория размещения со временем стала необходимым инструментом в экономической географии, региональной экономике и в экономике города. Например, геометрическая медиана успешно используется для отыскания оптимального расположения культурных центров, школ, медицинских центров или аварийно-спасательных служб на городской территории (Панов, 2017; Yao, Zhang, Murray, 2019).

Важнейшее свойство медианы числовой выборки заключается в том, что эта медиана минимизирует суммарное расстояние до всех элементов выборки. Именно это свойство минимальности положено в основу определения геометрической медианы для конечных наборов точек на плоскости. Далее это определение легко переносится на любое метрическое пространство, в том числе и на Евклидово пространство ${ℝ}^n$. А с помощью интегрирования оно распространяется и на ограниченные подмногообразия любой размерности в ${ℝ}^n$ (Fekete, Mitchell, Beurer, 2005).

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

Существует три различных взгляда на треугольник. Можно считать, что это: трехточечное подмножество плоскости; замкнутая трехзвенная ломаная на плоскости; треугольная область на плоскости. В соответствии с этим имеются три рода геометрических медиан $m_0,m_1,m_2,$ связанных с треугольником:

$m_0=\underset{X\in {ℝ}^2}{\arg \min }\left(\left|A-X\right|+\left|B-X\right|+\left|C-X\right|\right);$

$m_1=\underset{X\in {ℝ}^2}{\arg \min }\left({\int }_{P\in a}^{}\left|P-X\right|dP+{\int }_{P\in b}^{}\left|P-X\right|dP+{\int }_{P\in c}^{}\left|P-X\right|dP\right);$ (1)

$m_2=\underset{X\in {ℝ}^2}{\arg \min }{\int }_{P\in abc}^{}\left|P-X\right|dP.$ (2)

Здесь $A,B,C$ — вершины треугольника; $a,b,c$ — его стороны и $abc$ — треугольная область, ограниченная сторонами $a,b,c$. Геометрическая медиана $m_0$ — это точка Ферма–Торричелли треугольника $ABC$, формулы для вычисления которой хорошо известны¹, — поэтому она исключается из обсуждения. Но для точек $m_1,m_2$ точные формулы отсутствуют. Однако удалось получить точные оценки аффинного типа для возможного расположения геометрических медиан $m_1$ периметров треугольников и для расположения геометрических медиан $m_2$ треугольных областей.

2. ОСНОВНОЙ РЕЗУЛЬТАТ

Теорема 1. Пусть задан произвольный треугольник $\delta$, и пусть $\delta \text{'}$ — его образ при гомотетии с коэффициентом 1/4 с центром, расположенным в центроиде треугольника $\delta$, а $\delta \text{'}\text{'}$ — криволинейный треугольник, составленный из дуг трех гипербол. При этом вершины $\delta \text{'}$ совпадают с вершинами $\delta \text{'}\text{'}$, а каждая из трех гипербол имеет асимптотами две стороны треугольника $\delta$ и касается двух его медиан (рис. 1). Тогда:

1. геометрическая медиана $m_1=m_1\left(\delta \right)$ треугольника $\delta$ лежит внутри треугольника $\delta \text{'}$
2. геометрическая медиана $m_2=m_2\left(\delta \right)$ треугольника $\delta$ лежит внутри треугольника $\delta \text{'}\text{'}$

Рис. 1. Геометрическая медиана m1(δ) содержится внутри подобного δ маленького треугольника δ′, а геометрическая медиана m2(δ) — в маленьком криволинейном треугольнике δ″

Рис. 1 служит иллюстрацией к теореме 1. На нем изображен треугольник $\delta$ со сторонами $\mathrm{9,7,5}$, соответствующие ему треугольник $\delta \text{'}$ и криволинейный треугольник $\delta \text{'}\text{'}$, а также две точки — геометрические медианы $m_1\left(\delta \right)$ и $m_2\left(\delta \right)$.

Дополним геометрическое описание треугольников $\delta \text{'}$ и $\delta \text{'}\text{'}$, представленных в теореме 1, их аналитическим описанием.

Дополнение 1. Пусть задан треугольник $\delta =A_1{A}_2{A}_3$. Тогда стороны соответствующего ему треугольника $\delta \text{'}$ задаются следующими параметрическими уравнениями

$h_i\left(t\right)=t{A}_i+\frac{1}{4}{A}_j+\left(\frac{3}{4}-t\right)A_k,$ (3)

где $\left(i,j,k\right)$ произвольная циклическая перестановка чисел $\mathrm{1,} \mathrm{2,} 3$, а параметр $t$ меняется в пределах $1/4\le t\le 1/2.$

Дополнение 2. Для треугольника $\delta =A_1{A}_2{A}_3$ отрезки гипербол, ограничивающих соответствующий $\delta$ треугольник $\delta \text{'}\text{'}$ из теоремы 1, имеют параметрические уравнения вида

$h_i\left(t\right)=\frac{1}{2\sqrt{2}}\left(t{A}_i+t^{-1}{A}_j+\left(2\sqrt{2}-\left(t+t^{-1}\right)\right)A_k\right).$ (4)

Здесь $\left(i,j,k\right)$ — произвольная циклическая перестановка чисел $1,2,3$, а параметр $t$ на этот раз меняется в пределах $1/\sqrt{2}\le t\le \sqrt{2}.$

3. ОСНОВНЫЕ ИНСТРУМЕНТЫ

В этом разделе мы укажем основные инструменты, которые используются при доказательстве теоремы 1, а именно: барицентрические координаты, аффинные отображения, пространство треугольников, медианные отображения и вырожденные треугольники.

Барицентрические координаты (Балк, Болтянский, 1987). Пусть задан треугольник $\delta =A_1{A}_2{A}_3$. Тогда любая точка $A$ внутри этого треугольника однозначно представляется в виде

$A={\lambda }_1{A}_1+{\lambda }_2{A}_2+{\lambda }_3{A}_3,$ (5)

где числа ${\lambda }_1,{\lambda }_2,{\lambda }_3$ положительны и ${\lambda }_1+{\lambda }_2+{\lambda }_3=1.$

Набор из этих трех чисел (${\lambda }_1,{\lambda }_2,{\lambda }_3$) называется барицентрическими координатами точки $A$ относительно треугольника $\delta$.

Теперь, если вернуться к формулам (3) и (4) из дополнений 1 и 2, то эти формулы задают барицентрические координаты границ треугольников $\delta \text{'}$ и $\delta \text{'}\text{'}$, соответствующих треугольнику $\delta =A_1{A}_2{A}_3$.

Для нас существенно, что для подобных треугольников ${\delta }_1$ и ${\delta }_2$ барицентрические координаты геометрических медиан $m_1\left({\delta }_1\right)$ и $m_1\left({\delta }_2\right)$ равны между собой, аналогично — и для $m_2\left({\delta }_1\right)$ и $m_2\left({\delta }_2\right)$. В этом смысле можно сказать, что в подобных треугольниках геометрические медианы расположены одинаковым образом. Это свойство геометрических медиан называют их эквивариантностью относительно преобразования подобия.

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

Существует много способов объединения треугольников единичного периметра в единое пространство (Behrend, 2014; Панов, 2021). Для наших целей выберем самый простой из них (Stewart, 2017). А именно каждому треугольнику единичного периметра с упорядоченным набором сторон $a,b,c$ сопоставим точку $\left(a,b,c\right)\in {ℝ}^3$. Эти точки заполнят в ${ℝ}^3$ целый треугольник с вершинами (1/2, 1/2, 0), (1/2, 0, 1/2), (0, 1/2, 1/2) лежащий в плоскости $x+y+z=1$. Обозначим его $\nabla$. Каждая точка, принадлежащая $\nabla$, отвечает некоторому треугольнику, поэтому $\nabla$ называется пространством треугольников.

Вырожденные треугольники. Обратим внимание на граничные точки пространства $\nabla$. Для координат $\left(a,b,c\right)$ внутренних точек $\nabla$ выполняется неравенство треугольника, т. е. бóльшее из чисел $a,b,c$ меньше суммы двух других, но для граничных точек $\nabla$ бóльшая из координат будет равна сумме двух других.

Треугольники, у которых одна сторона равна сумме двух других, называются вырожденными.

В случае когда именно $a=b+c$, вырожденный треугольник можно представлять как отрезок $CB$ с отмеченной на нем точкой $A$ (рис. 2). Таким образом, можно считать, что граница $\partial \nabla$ пространства $\nabla$ соответствует вырожденным треугольникам с единичным периметром.

Рис. 2. Вырожденный треугольник, a = b + c

Медианные отображения. Введем в рассмотрение еще один правильный треугольник $∆$ с вершинами $\left(\mathrm{1,0,0}\right), \left(\mathrm{0,1,0}\right), \left(\mathrm{0,0,1}\right)$, лежащий в плоскости $x+y+z=1$, и определим два медианных отображения ${\mathcal{M}}_i, i=\mathrm{1,}2$: ${\mathcal{M}}_i :\nabla \to \Delta$ из пространства треугольников $\nabla$ в правильный треугольник $∆$.

Пусть задана точка $\left(a,b,c\right)\in \nabla$, соответствующая некоторому треугольнику $\delta$ с упорядоченным набором сторон $a,b,c$. Пусть также $m_i$ — геометрическая медиана этого треугольника $\delta$, а ${\lambda }_1^i,{\lambda }_2^i,{\lambda }_3^i$ — ее барицентрические координаты относительно $\delta$, тогда ${\lambda }_1^i+{\lambda }_2^i+{\lambda }_3^i=1$. Поэтому $({\lambda }_1^i,{\lambda }_2^i,{\lambda }_3^i)\in \Delta$ и по определению отображение ${\mathcal{M}}_i$ устроено следующим образом:

${\mathcal{M}}_i :\left(a,b,c\right)\mapsto \left({\lambda }_1^i,{\lambda }_2^i,{\lambda }_3^i\right).$ (5)

Образ отображения ${\mathcal{M}}_1$ обозначим $∆\text{'}$, образ отображения ${\mathcal{M}}_2$ обозначим $∆\text{'}\text{'}$.

Как мы собрали все треугольники в единое пространство $\nabla$, так и медианное отображение ${\mathcal{M}}_1$ собирает геометрические медианы $m_1$ всех треугольников в единое пространство ${\Delta }^{\text{'}}\subset \Delta$, а медианное отображение ${\mathcal{M}}_2$ собирает геометрические медианы $m_2$ всех треугольников в ${\Delta }^{\text{'}\text{'}}\subset \Delta$.

Используя понятие аффинного отображения, можно дать альтернативное определение медианных отображений ${\mathcal{M}}_1$ и ${\mathcal{M}}_2$. Напомним, что для любой пары треугольников с заданным порядком вершин существует единственное аффинное отображение, переводящее вершины первого из них в вершины второго в указанном порядке. При этом отображении точка, имеющая барицентрические координаты ${\lambda }_1,{\lambda }_2,{\lambda }_3$ относительно первого треугольника, переходит в точку, имеющую те же самые барицентрические координаты относительно второго треугольника.

Пусть теперь $\delta =abc$ — треугольник единичного периметра со сторонами $a,b,c$ и геометрическими медианами $m_1\left(\delta \right)$ и $m_2\left(\delta \right)$. Пусть также ${\mathcal{A}}_{\delta }$ — аффинное отображение треугольника $\delta$ в треугольник $∆$: ${\mathcal{A}}_{\delta }\text{:} \delta \to \Delta .$ Тогда медианное отображение ${\mathcal{M}}_i$ из формулы (5) можно определить формулой

${\mathcal{M}}_i :\left(a,b,c\right)\mapsto {\mathcal{A}}_{\delta }\left(m_i\left(\delta \right)\right).$ (6)

Это следует из того, что для точек, лежащих в плоскости $x+y+z=1$, их барицентрические координаты относительно $∆$ и их декартовы координаты совпадают.

Компьютерная визуализация. На рис. 3 представлена компьютерная визуализация медианного отображения ${\mathcal{M}}_1\text{:}\nabla \to \Delta$. Для его построения была использована репрезентативная выборка точек из пространства $\nabla$, образы которых достаточно плотно заполняют $∆\text{'}$. Используя это изображение, а также подвижную визуализацию отображения ${\mathcal{M}}_1$², можно сделать вывод, что граница пространства треугольников $\partial \nabla$, соответствующая вырожденным треугольникам, при отображении ${\mathcal{M}}_1$ переходит в границу области $∆\text{'}$, которую мы обозначим $\partial {\Delta }^{\text{'}}$.

Рис. 3. Слева в треугольнике $∆$ находится образ отображения ${\mathcal{M}}_1$ — область $∆\text{'}$, справа — увеличенная копия $∆\text{'}$

То же самое, что было отмечено выше в отношении отображения ${\mathcal{M}}_1$, можно отнести и к медианному отображению ${\mathcal{M}}_2$ (рис. 4). И здесь граница пространства треугольников $\partial \nabla$, соответствующая вырожденным треугольникам, при отображении ${\mathcal{M}}_2$ тоже переходит в границу образа этого отображения, т. е. в $\partial ∆\text{'}\text{'}$. Описанные здесь свойства медианных отображений ${\mathcal{M}}_1$ и ${\mathcal{M}}_2$ позволяют наметить основные шаги для доказательства теоремы 1.

Рис. 4. Треугольник $∆$ (слева — область $∆\text{'}\text{'}$ — образ отображения ${\mathcal{M}}_2$, справа — увеличенная копия $∆\text{'}\text{'}$)

ОСНОВНЫЕ ИДЕИ ДОКАЗАТЕЛЬСТВА

Главный шаг в доказательстве основного результата — вычисление уравнений границ образов медианных отображений ${\mathcal{M}}_1$ и ${\mathcal{M}}_2$, т. е. границ множеств $∆\text{'}$ и $∆\text{'}\text{'}$ на рис. 3–4. Как было указано в предыдущем разделе, для этого нужно уметь вычислять местоположение геометрических медиан $m_1$ и $m_2$ вырожденных треугольников, а именно барицентрические координаты этих медиан. Это вычисление осуществляется с помощью предельного перехода и с помощью соответствующего этому переходу асимптотического анализа градиентных систем для решения минимизационных задач (1) и (2) (Панов, 2021). Вот формулировка нужного нам результата.

Предложение 1. Пусть $\delta =abc$ — вырожденный треугольник и $a\ge b\ge c$, и пусть $a_n{b}_n{c}_n$ — последовательность сходящихся к нему обычных треугольников, т. е. обычных треугольников, для которых $a_n\to a,b_n\to b,c_n\to c$. Тогда:

1. геометрическая медиана $m_1$ треугольника $a_n{b}_n{c}_n$ удалена от общей вершины сторон $a_n$ и $b_n$ на расстояние, близкое к $a/2$, а отношение расстояний от нее до сторон $a_n$ и $b_n$ близко к 1;
2. геометрическая медиана $m_2$ треугольника $a_n{b}_n{c}_n$ удалена от общей вершины сторон $a_n$ и $b_n$ на расстояние, близкое к $\sqrt{ab/2}$, и отношение расстояний от нее до сторон $a_n$ и $b_n$ близко к $1$

На менее формальном и более выразительном языке можно сказать, что геометрические медианы $m_1$ и $m_2$ вырожденного треугольника $\delta =abc$, $a\ge b\ge c$ лежат на биссектрисе его меньшего угла на расстояниях $a/2$ и $\sqrt{ab/2}$ от вершины этого угла.

Следующее утверждение является прямым переводом предложения 1 на язык барицентрических координат.

Предложение 2. Пусть $\delta =abc$ — вырожденный треугольник, в котором $a\ge b\ge c.$ Тогда геометрическая медиана его периметра, точка $m_1$ имеет барицентрические координаты

${\lambda }_a=\frac{a}{4b}, {\lambda }_b=\frac{1}{4}, {\lambda }_c=\frac{3}{4}-\frac{a}{4b},$ (7)

а геометрическая медиана его внутренности, точка $m_2$, имеет барицентрические координаты

${\lambda }_a={\left(2\sqrt{2}\right)}^{-1}\sqrt{a/b}, {\lambda }_b={\left(2\sqrt{2}\right)}^{-1}\sqrt{b/a}, {\lambda }_c=1-{\left(2\sqrt{2}\right)}^{-1}\left(\sqrt{a/b}+\sqrt{b/a}\right).$ (8)

И теперь уже можно утверждать, что теорема 1 является прямым следствием предложения 2. Действительно, пусть задан произвольный треугольник $\delta$ и пусть $\delta \text{'}$ и $\delta \text{'}\text{'}$ — соответствующие ему треугольники из теоремы 1. Тогда сравнение формул (7) и (3), а также (8) и (4) показывает, что

${\delta }^{\text{'}}={\mathcal{A}}_{\delta }^{-1}\left({\Delta }^{\text{'}}\right)$ и ${\delta }^{\text{'}\text{'}}={\mathcal{A}}_{\delta }^{-1}\left({\Delta }^{\text{'}\text{'}}\right),$ (9)

где ${\mathcal{A}}_{\delta }^{-1}$ — аффинное отображение треугольника $∆$ в треугольник $\delta$, обратное аффинному отображению ${\mathcal{A}}_{\delta }$. В свою очередь, соотношение (6) свидетельствует о том, что

${\mathcal{A}}_{\delta }\left(m_1\left(\delta \right)\right)\in {\Delta }^{\text{'}}$ и ${\mathcal{A}}_{\delta }\left(m_2\left(\delta \right)\right)\in {\Delta }^{\text{'}\text{'}}\text{,}$ (10)

а (10) и (9) дают $m_1\left(\delta \right)\in {\delta }^{\text{'}}$ и $m_2\left(\delta \right)\in {\delta }^{\text{'}\text{'}},$ как и записано в теореме 1.

Некоторые дополнительные подробности изложены в (Панов, 2021).

ЗАКЛЮЧЕНИЕ

Хотя существуют эффективные численные методы нахождения геометрической медианы, но нет аналитических формул для её вычисления. Поэтому нужны хорошие универсальные оценки для местоположения геометрических медиан. Имеется два типа таких оценок. Первая — достаточно очевидна и заключается в том, что для любого подмножества пространства ${ℝ}^n$ геометрическая медиана, если она существует, принадлежит выпуклой оболочке этого множества. Вторая — универсальная оценка (Mallows, 1991; Piché, 2012) — основана на вероятностных соображениях и применима к подмножествам ${ℝ}^n$. Однако обе эти оценки для треугольника, расположенного на плоскости, сильно уступают тем, что предъявлены в теореме 1.

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

¹ Точка X(13) из “Encyclopedia of triangle centers» (https://faculty.evansville.edu/ck6/encyclopedia/ETC.html).

² https://commons.wikimedia.org/wiki/File: Animation_M_1.gif

About the authors

P. A. Panov

Author for correspondence.
Email: ppanov@hse.ru
Russian Federation, Moscow

References