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

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




 10- и 11-угольник как пересечение двух 4-угольников
Аватара пользователя
Можно ли так изобразить два четырехугольника, чтобы их общая часть (пересечение) оказалась
десятиугольником?
(источник задачи: 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-угольников
Если не требовать связности, то 16.

 Re: 10- и 11-угольник как пересечение двух 4-угольников
Аватара пользователя
slavav
Можно пример?

 Re: 10- и 11-угольник как пересечение двух 4-угольников
$(100, 0) - (-100, 1) - (99, 0) - (-100, -1)$
$(0, 100) - (1, -100) - (0, 99) - (-1, -100)$

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

 Re: 10- и 11-угольник как пересечение двух 4-угольников
Аватара пользователя
slavav
Спасибо!

 [ Сообщений: 5 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group