Комбинаторная геометрия

Аватар пользователя
Ian
Сообщений: 686
Зарегистрирован: 18 янв 2016, 19:42

Комбинаторная геометрия

Сообщение Ian » 29 янв 2021, 02:10

geom1.png
geom1.png (13 KiB) 1395 просмотра

Перевод: На плоскости проведены n прямых, разбивающих ее на некоторое множество многоугольников С. Доказать , что сумма квадратов чисел вершин этих многоугольников оценивается константой на [math]
Мне кажется, разрешены и неограниченные многоугольники.Наличие пересечений трех и более прямых в одной точке, или параллельных прямых, только уменьшают оцениваемую сумму, поэтому будем считать что их нет. Тогда общее число вершин [math], а областей [math] ,но это ничего не дает.
Если даже среди областей есть n- угольник, это не гарантирует, что все остальные области будут треугольниками, например n=9- прямые . являющиеся продолжением сторон правильного 9-угольника, образуют и как минимум 9 4-угольников. В общем, задача похожа на олимпиадную

zykov
Сообщений: 1005
Зарегистрирован: 06 янв 2016, 17:41

Комбинаторная геометрия

Сообщение zykov » 30 янв 2021, 09:49

Ian писал(а):Source of the post Наличие пересечений трех и более прямых в одной точке, или параллельных прямых

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

Ian писал(а):Source of the post а областей $\frac{n(n+1)}{2}+1$

Это сразу даёт квадратное ограничение снизу. Остаётся только ограничить квадратно сверху.

Да, как-то оно не просто выглядит. Один многоугольник может иметь много вершин - вплоть до $n$.
Но при этом другие не могут иметь много вершин. В этом всё дело. Вопрос в том, как это формализовать.
Наверно надо как-то с углами похимичить. Там сумма $\sum_i (\pi - \alpha_i) = 2\pi$ для каждого многоугольника.
Все они выпуклые, значит внешний угол $\pi - \alpha_i > 0$, и если много вершин, то в своей массе эти внешние углы должны быть маленькие.
Но для большого числа многоугольников этого не может быть, т.к. сами эти углы - это углы между каким-то двумя прямыми из этих $n$, а все они не могут быть маленькими.
Вобщем интуитивно, что-то в этом направлении.

Аватар пользователя
Ian
Сообщений: 686
Зарегистрирован: 18 янв 2016, 19:42

Комбинаторная геометрия

Сообщение Ian » 30 янв 2021, 16:24

Вот еще две задачи в том же духе.
geom2.png
geom2.png (69.39 KiB) 1370 просмотра

Вольные переводы.
3. Есть (n-1)! перестановок чисел 1,2,...n, расположенных по окружности, далее кратко называемых "круговыми перестановками" . На плоскости есть n пронумерованных точек общего положения, никакие три не на одной прямой и никакие 4 не вершины трапеции. Рассмотрим для каждой иной точки плоскости круговую перестановку- порядок видения n точек при повороте наблюдателя из данной точки против часовой стрелки. Рассмотрим, сколько разных круговых перестановок можно получить изменением точки наблюдателя. Доказать, что это число оценивается снизу константой на [math]
5. M- множество из n точек общего положения (никакие три не лежат на одной прямой). Говорят, что множество P "прокалывающее треугольники" для множества M, если во внутренности всякого треугольника с тремя разными вершинами из М найдется точка множества Р. Доказать, что найдется P из (2n-5) точек, а из (2n-6) не обязательно.

Аватар пользователя
Ian
Сообщений: 686
Зарегистрирован: 18 янв 2016, 19:42

Комбинаторная геометрия

Сообщение Ian » 30 янв 2021, 16:34

Соображения по 3й. Понятно, что число прямых проведенных через каждую пару точек [math], а число областей, на которые они делят плоскость, [math]. Раскрасим каждую прямую так: отрезок между точками в красный цвет, а оставшиеся два луча -в синий цвет. При переходе из области в соседнюю через красную границу - круговая перестановка не меняется, а через синюю -обязательно меняется (умножается на транспозицию соседних точек).
1. Есть возможность доказать, что только синие лучи -разбивают плоскость на число частей, оцениваемых снизу константой на [math]
2. Но этого мало, для n=3 у нас (после стирания красных отрезков) 4 области на плоскости, а число круговых перестановок 2!=2 всего. То есть нет гарантии, что в разных несоседних областях - сидят разные круговые перестановки.
Последний раз редактировалось Ian 31 янв 2021, 08:47, всего редактировалось 1 раз.

zykov
Сообщений: 1005
Зарегистрирован: 06 янв 2016, 17:41

Комбинаторная геометрия

Сообщение zykov » 30 янв 2021, 22:47

Ну это наверно не олимпиадные задачи, а задачник по теме "Комбинаторная геометрия".
Если в олимпиадных ещё можно догадаться логически, то в задачнике обычно рассчитано на то, что студент изучил теорию. А там есть сложные теоремы, которые так просто, с пол пинка, не докажешь.
Я с этой теорией не сталкивался. Только так, мимоходом, какие-нибудь простые олимпиадные задачи.

Аватар пользователя
Ian
Сообщений: 686
Зарегистрирован: 18 янв 2016, 19:42

Комбинаторная геометрия

Сообщение Ian » 31 янв 2021, 08:20

Даже не задачник, а задания студентам из Праги. Мне тоже интересно, в чем у них состояла теория, если она позволяет такое решить.

zykov
Сообщений: 1005
Зарегистрирован: 06 янв 2016, 17:41

Комбинаторная геометрия

Сообщение zykov » 31 янв 2021, 11:54

Не знаю, никогда этим не занимался.
Вот например студентам курс предлагали:
https://page.mi.fu-berlin.de/sanyal/teaching/dg1/
Там в списке литературы:
  • Arne Brondsted, An Introduction to Convex Polytopes, Springer GTM 90
  • Branko Grünbaum Convex Polytopes, Springer GTM 221 (Second Edition)
  • Gil Kalai, Günter Ziegler, Polytopes - Combinations and Computation, Birkhäuser DMV Seminar, Band 29
  • Peter Gruber Convex and discrete Geometry, Springer Grundlehren 336
  • Jirka Matousek, Lectures on Discrete Geometry, Springer GTM 212
  • Peter McMullen, Geoffrey Shephard, Convex polytopes and the upper bound conjecture, LMS Lecture Notes 3
  • Günter Ziegler, Lectures on Polytopes, Springer GTM 152

Можно посмотреть, что там за теоремы у них имеются.
Например вот это может иметь отношение к таким задачам:
Combinatorial geometry / Geometric combinatorics
  • Arrangements of points and lines, Sylvester-Gallai, Erdos-Szekeres,
  • Szemeredi--Trotter
  • Arrangements, zonotopes, zonotopal tilings, oriented matroids

zykov
Сообщений: 1005
Зарегистрирован: 06 янв 2016, 17:41

Комбинаторная геометрия

Сообщение zykov » 08 фев 2021, 08:27

По поводу задачи 1 видимо вот это подходит: Complexity of arrangements.
Там сказано: "Summing the complexities of all zones, one finds that the sum of squares of cell complexities in an arrangement is $O(n^2)$".

И дана ссылка [7]: Aronov, B.; Matoušek, J.; Sharir, M. (1994), "On the sum of squares of cell complexities in hyperplane arrangements", Journal of Combinatorial Theory, Series A, 65 (2): 311–321.

zykov
Сообщений: 1005
Зарегистрирован: 06 янв 2016, 17:41

Комбинаторная геометрия

Сообщение zykov » 08 фев 2021, 08:43

Более фундаментальный результат тут - это Szemerédi–Trotter theorem.


Вернуться в «Математика»

Кто сейчас на форуме

Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 8 гостей