2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 10- и 11-угольник как пересечение двух 4-угольников
Сообщение26.08.2016, 23:19 
Аватара пользователя


01/12/11

8634
Можно ли так изобразить два четырехугольника, чтобы их общая часть (пересечение) оказалась
десятиугольником?
(источник задачи: http://math.mosolymp.ru/upload/files/ma ... oboy_2.pdf , задача №2)

Мне кажется, что если вершины первого 4-угольника:
$$(0, 0), (-2, 2), (3, 2), (-1, -2)$$
, а второго:
$$(0, 1), (2, 3), (1, -3), (-2, 3)$$
, то всё получится.

Однако напрашивается вопрос, а является ли 10 максимальным количеством углов, которое может иметь пересечение двух 4-угольников? Может, можно построить и 11-угольник таким образом?

Пожалуйста, помогите решить.
Заранее спасибо!

 Профиль  
                  
 
 Re: 10- и 11-угольник как пересечение двух 4-угольников
Сообщение28.08.2016, 00:38 
Заслуженный участник


26/05/14
981
Если не требовать связности, то 16.

 Профиль  
                  
 
 Re: 10- и 11-угольник как пересечение двух 4-угольников
Сообщение28.08.2016, 11:13 
Аватара пользователя


01/12/11

8634
slavav
Можно пример?

 Профиль  
                  
 
 Re: 10- и 11-угольник как пересечение двух 4-угольников
Сообщение28.08.2016, 11:21 
Заслуженный участник


26/05/14
981
$(100, 0) - (-100, 1) - (99, 0) - (-100, -1)$
$(0, 100) - (1, -100) - (0, 99) - (-1, -100)$

Подобные примеры строятся для доказательства того что пересечение $M$- и $N$-угольников может иметь сложность $O(MN)$.

 Профиль  
                  
 
 Re: 10- и 11-угольник как пересечение двух 4-угольников
Сообщение29.08.2016, 00:19 
Аватара пользователя


01/12/11

8634
slavav
Спасибо!

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 5 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

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


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group