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 ] 

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



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

Сейчас этот форум просматривают: mihaild


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

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