Улучшено (?) решение Эрдёша по остроугольным треугольникам

[grizzly]

Sender в сообщении #1242316 писал(а):

Если интересно, могу потом выписать эти выражения.

Очень интересно! Нам обязательно нужно разбавить всю эту эмпирику аналитикой

Я могу добавить только одно пока: я проверил, что если вторую (и симметричную ей) точку немного прижать ближе к своему углу, то к этому ОМ легко добавляется 9-я точка. Я проверял при $L=100, \ a=10$. Понятно, что диапазон возможностей для 9-й точки сильно уже, но и он должен быть достаточным. Впрочем, это так, к слову, -- пока удобнее работать с $2^{d-1}$ точкой.

[Sender]

Догадался применить дополнительное упрощение, вид получился почти удобоваримый.

$$\left\{\begin{matrix} L> \frac{4 a}{3 a-\sqrt{a (a+20)-20}-2},3<a\leq \sqrt{10^{2/3}+5+\frac{5^{4/3}}{2^{2/3}}}; \\ L>\frac{a}{2} \left(\sqrt{a^2-4}+a\right),a>\sqrt{10^{2/3}+5+\frac{5^{4/3}}{2^{2/3}}} \end{matrix}\right.$$

[grizzly]

Sender
Вторая формула в точности соответствует эмпирике (а $L$ в ней очень хорошо приближает $a^2$).
С первой что-то не так. С ростом $a$ от 4 до 15 почему-то $L$ уменьшается.

[Sender]

grizzly в сообщении #1242394 писал(а):

С первой что-то не так. С ростом $a$ от 4 до 15 почему-то $L$ уменьшается.

Эм, это вы про $L> \frac{4 a}{3 a-\sqrt{a (a+20)-20}-2}$? Ну так она работает только при $3<a\leq \sqrt{10^{2/3}+5+\frac{5^{4/3}}{2^{2/3}}}$, т.е. при $a<4$.

[grizzly]

Sender
Точно, сорри (это я корень для $a$ прозевал).

[g______d]

У меня есть вопрос, возможно, несколько наивный (заранее извиняюсь). Проверял ли кто-нибудь, существует ли множество в $\mathbb R^d$ с указанным свойством среди малых возмущений $(d-1)$-мерного куба?

Мне кажется, что достаточным условием будет наличие для каждой вершины открытого множества направлений, при малом сдвиге на которые все углы с участием этой вершины станут острыми. И для каждой точки это будет проверкой непустоты пересечения набора полупространств, что можно сделать с помощью линейного программирования или даже аналитически достаточно быстро.

[grizzly]

g______d в сообщении #1242438 писал(а):

У меня есть вопрос, возможно, несколько наивный (заранее извиняюсь).

Добро пожаловать в наш танк

g______d в сообщении #1242438 писал(а):

Проверял ли кто-нибудь, существует ли множество в $\mathbb R^d$ с указанным свойством среди малых возмущений $(d-1)$-мерного куба?

Последние пару месяцев только этим и занимаемся -- здесь все разговоры как раз об этом. С тех пор как была выдвинута гипотеза $|S_d|=2^{d-1}+1$. Собственно, от идеи такого куба и пошла гипотеза (в частности, так строится вся эмпирика).

g______d в сообщении #1242438 писал(а):

Мне кажется, что достаточным условием будет наличие для каждой вершины открытого множества направлений, при малом сдвиге на которые все углы с участием этой вершины станут острыми.

Upd. Допустим так. Какой-то набор квази-конусов, вытянутых в направлении $d$. Идея интересная. Каждое из множеств открыто, но можно ли из этого делать вывод о существовании пересечения? После движения одной точки какие-то направления просто исчезают. Нам нужно не просто множество таких направлений, но чтобы какая-то его открытая часть была достаточно жирной. Тогда не совсем понятно, как это упрощает общую задачу.

[g______d]

grizzly в сообщении #1242446 писал(а):

Upd. Допустим так. Какой-то набор квази-конусов, вытянутых в направлении $d$. Идея интересная. Каждое из множеств открыто, но можно ли из этого делать вывод о существовании пересечения? После движения одной точки какие-то направления просто исчезают. Нам нужно не просто множество таких направлений, но чтобы какая-то его открытая часть была достаточно жирной. Тогда не совсем понятно, как это упрощает общую задачу.

Может быть, надо не "все углы", а "все треугольники с участием этой вершины". Но, возможно, это слишком сильное требование. Надо ещё подумать. Мне казалось, что задача должна линеаризовываться в окрестности куба, но я, возможно, был слишком оптимистичен.

[Sender]

g______d в сообщении #1242438 писал(а):

И для каждой точки это будет проверкой непустоты пересечения набора полупространств, что можно сделать с помощью линейного программирования или даже аналитически достаточно быстро.

Можно рассмотреть простой пример, чтобы говорить предметнее. Возьмём квадрат в 3-мерном пространстве с координатами вершин $(-1,-1,0),(-1,1,0),(1,-1,0),(1,1,0)$. Немного сместим 1-ю вершину на $x_1,x_2,x_3,$ оставив остальные на месте. Тогда координаты вершин $(x_1-1,x_2-1,x_3),(-1,1,0),(1,-1,0),(1,1,0).$ Мы хотим, чтобы все скалярные произведения векторов с участием 1-й вершины были положительными, тогда: $(x_1-1)^2+(x_2-1)^2+x_3^2>2$, $x_1>0$, $x_2>0$. Множество непусто, хотя и не содержит желаемого конуса. Возможно, это могло бы послужить подсказкой алгоритму grizzly, под каким фонарём искать.

[g______d]

Да, я могу сформулировать более конкретно. Рассмотрим все координаты всех точек как вектор в пространстве размерности $d 2^{d-1}$. Для каждой вершины каждого треугольника напишем квадратичный функционал вида $a^2+b^2-c^2$. На кубе какие-то из этих функционалов положительные, какие-то равны нулю. На положительные мы можем забить (при малых возмущениях они останутся положительными). Те, которые равны нулю, половина направлений (в большом пространстве) сделает положительными, половина направлений отрицательными (ещё будут сколько-то направлений, которые либо сохранят его значение, либо сохранят в первом порядке, т. е. касаются конуса, но мы на них забьём, т. к. это множество меньшей размерности).

Таким образом, мы получаем задачу о тривиальности/нетривиальности пересечения полупространств.

-- Вт, 22 авг 2017 13:35:35 --

Преимущество, на мой взгляд, в том, что это можно загнать в linear programming solver.

Единственная возможная проблема (опять же, на мой наивный взгляд) -- если вдруг окажется, что пересечение открытых полупространств пусто, а замкнутых непусто, тогда линеаризации недостаточно.

[Sender]

Ага, кажется, улавливаю. Для начала возьмём тот же самый квадрат из моего предыдущего примера с добавками ко всем вершинам(немного изменил порядок вершин, чтобы пронумеровать в направлении обхода): $(x_1-1,y_1-1,z_1),(x_2-1,y_2+1,z_2),(x_3+1,y_3+1,z_3),(x_4+1,y_4-1,z_4)$. Функционал для 1-й вершины $s=(x_2-x_1)(x_4-x_1+2)+(y_2-y_1+2)(y_4-y_1)+(z_2-z_1)(z_4-z_1)$. Касательная плоскость в нуле: $-x_1+x_2-y_1+y_4=0.$ Нас интересует полупространство $-x_1+x_2-y_1+y_4>0$, так? Если да, то, боюсь, этот подход не очень поможет: мы ничего не можем сказать по поводу последней координаты (z в данном случае), а оставаясь в $\mathbb R^{d-1}$, мы не получим ОМ.

[grizzly]

g______d,
Сама конфигурация вершин $d-1$-куба соответствует одной точке в рассматриваемом Вами пространстве размерности $d 2^{d-1}$. Это либо изолированная точка, либо граничная точка подходящего нам (непустого) пересечения. Мне совсем неочевидно, что анализ такого пересечения должен быть каким-то простым.

На всякий случай уточню, что если при замене $d-1$ в этом анализе на $d-k$ с любым фиксированным $k$ удастся доказать, что $2^{d-k}$ точек (чуть сдвинутых вершин $d-k$-мерного куба) в пространстве размерности $R^d$ дают в этом пространстве ОМ, то это тоже будет самое существенное продвижение в рассматриваемой задаче после работ Эрдёша с Фюреди 35 летней давности.

[g______d]

Sender в сообщении #1242497 писал(а):

Касательная плоскость в нуле: $-x_1+x_2-y_1+y_4=0.$

Надо не в нуле, а в точке

Sender в сообщении #1242460 писал(а):

$(-1,-1,0),(-1,1,0),(1,-1,0),(1,1,0)$

-- Ср, 23 авг 2017 06:42:43 --

grizzly в сообщении #1242500 писал(а):

Мне совсем неочевидно, что анализ такого пересечения должен быть каким-то простым.

Казалось бы, проверить непустоту пересечения явно заданных полупространств. Может быть, конечно, алгоритмы не такие быстрые, но это немного странно.

grizzly в сообщении #1242500 писал(а):

На всякий случай уточню, что если при замене $d-1$ в этом анализе на $d-k$ с любым фиксированным $k$ удастся доказать, что $2^{d-k}$ точек (чуть сдвинутых вершин $d-k$-мерного куба) в пространстве размерности $R^d$ дают в этом пространстве ОМ, то это тоже будет самое существенное продвижение в рассматриваемой задаче после работ Эрдёша с Фюреди 35 летней давности.

Мне скорее кажется более реалистичным, что там по какие-то причинам пересечение вырождается...

-- Ср, 23 авг 2017 06:59:30 --

А, ну, похоже, вырождается. Если, действительно, посмотреть на квадрат в $\mathbb R^3$, то понятно, что никуда, кроме как по $z$, там двигаться нельзя, т. е. пересечение имеет существенно меньшую размерность, чем нужно.

-- Ср, 23 авг 2017 07:01:53 --

Sender в сообщении #1242460 писал(а):

Множество непусто, хотя и не содержит желаемого конуса.

Да, не содержит... Ну ладно. Было бы странно, если иначе, на самом деле.

[Sender]

g______d в сообщении #1242573 писал(а):

Надо не в нуле, а в точке

Sender в сообщении #1242460

писал(а):
$(-1,-1,0),(-1,1,0),(1,-1,0),(1,1,0)$

Я, наверное, неточно выразился. Имелось в виду при $(x1,y1,z1,x2,y2,z2,x3,y3,z3,x4,y4,z4)=(0,0,0,0,0,0,0,0,0,0,0,0)$, что в выражении

Sender в сообщении #1242497 писал(а):

$(x_1-1,y_1-1,z_1),(x_2-1,y_2+1,z_2),(x_3+1,y_3+1,z_3),(x_4+1,y_4-1,z_4)$

и даст $(-1,-1,0),(-1,1,0),(1,1,0),(1,-1,0)$ (я перенумеровал точки квадрата в порядке обхода по контуру).

[g______d]

Sender в сообщении #1242585 писал(а):

Я, наверное, неточно выразился.

Нет, всё правильно, я просто плохо прочитал.

Действительно, тот факт, что сдвиг по $z$ в указанном примере нам помогает, является квадратичным и не виден на уровне линейного приближения. С квадратичными всё намного хуже, конечно: в общем случае это, кажется, NP-сложная задача.