Разделение фигуры на конгруэнтные субрегионы

Question

Учитывая неправильный многоугольник с равными сторонами. Есть ли алгоритм, чтобы разделить его на шесть равных по размеру областей?

Answer 1

Нет. Такое подразделение не всегда возможно:

Рассмотрим многоугольник P получается путем объединения двух правильных многоугольников P1 а также P2 с другим и очень большим количеством сторон N1 а также N2, Этот многоугольник приближается к паре круглых дисков C1 а также C2 с точностью до произвольной.

Рассмотрим его подразделение на шесть конгруэнтных областей.

Рассмотрим множество вершин P1, Там должен быть регион, который содержит по крайней мере (N1)/6 Вершины. Назовите вершины V1 и регион R1, Там должен быть регион, который содержит по крайней мере (N2)/6 вершины P2, Назовите вершины V2 область R2,

Если R1 != R2 тогда должно быть сопоставление конгруэнтности R2 в R1, Если 2*N1 < N2 такое отображение невозможно. Выберите N2, чтобы быть намного больше, чем N1.

Таким образом, R1 == R2, Существует регион, который содержит как V1 а также V2, Диаметр каждой области должен быть больше диаметра P2,

Используйте двухкружное приближение. Каждая область должна содержать дугу не менее 1/6 периметра C1 и дуга не менее 1/6 периметра C2, Кроме того, есть по крайней мере одна область, которая находится внутри обоих кругов, и ни одна область не находится полностью внутри меньшего круга.

Рассмотрим возможные сравнения R1, Любая конгруэнтность либо 1) является отражением вдоль главной оси, либо 2) отображает либо P1, либо P2 вне P, либо 3) отображает некоторую часть периметра во внутреннюю часть P. Отражение недостаточно, поэтому любое подразделение должно содержать конгруэнтность который отображает некоторую часть P1 во внутреннюю часть P1.

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

---

Существует много классов полигонов, которые вы можете обнаружить:

• Симметрия вращения порядка 6 C6, Их можно подразделить любым способом, который учитывает симметрию вращения.
• Диэдральная симметрия порядка-3 D6 (порядок-3 вращения + зеркала). Разрезать по зеркалам.
• формы, которые покрывают плоскость с переводом с четырьмя многоугольниками, встречающимися в вершине. Это фигуры, которые имеют две пары совпадающих противоположных путей. Дублируйте режущую кромку в одном направлении и трижды в другом.
• некоторые формы имеют симметрию отражения, и каждая отдельная половина имеет симметрию вращения порядка 3. Их также можно обнаружить и сократить.
• некоторые формы имеют симметрию вращения порядка 2 и могут разрезаться в двух конгруэнтных областях, которые имеют симметрию вращения порядка 3. Ищите повторный образец вдоль границы.
• некоторые фигуры имеют симметрию вращения порядка 3 и могут быть разбиты на три области с симметрией. Я не уверен, что смог надежно обнаружить такие формы (обнаружение C3 легко, последующее сокращение не), и я человек.
• ...
• Полиомино - это фигуры, сделанные из квадратов, многоугольники - это фигуры, сделанные из шестиугольников, а полиамины - это фигуры, сделанные из треугольников. Их легко обнаружить, а у некоторых даже есть подразделение. Подразделение, если оно существует, также может быть трудно обнаружить, но, по крайней мере, вы можете перечислить все подразделения, которые относятся к выровненной сетке с правильным размером, чтобы увидеть, являются ли они конгруэнтными.
• ...

Чтобы продемонстрировать сложность проблемы: существует определенный класс логических головоломок, цель которых состоит в том, чтобы разбить сложную форму (60 квадратов) на две конгруэнтные области. Если человеку нелегко разделить полиомино на две конгруэнтные области, как вы ожидаете, как компьютер разделит общую форму на шесть конгруэнтных областей?

Если вы хотите обнаружить большинство случаев, когда возможное подразделение, вы должны найти компромисс между временем программирования (для поддержки все большего числа особых случаев) и силой теста. Для начала придерживайтесь C6, D3 and checkerboard tiles => easy to subdivide; polyforms => maybe possible; the rest => probably no subdivision,