Определения и обозначения. Пусть $P\subset {\mathbb{R}}^2$ — выпуклый ограниченный многоугольник с непустой внутренностью. Для вектора сдвига $v\in {\mathbb{R}}^2$ обозначим сдвиг множества через $P+v=\{x+v:x\in P\}$. Введём разностное тело (Minkowski difference)
$$D:=P-P=\{x-y:x,y\in P\}.$$
Критерии пересечения / «самопокрытия».
1) Для любого вектора $v$ верно
$$P\cap (P+v)\ne \varnothing ⟺v\in D.$$ Доказательство: если $z\in P\cap (P+v)$, то $z=x$ и $z=y+v$ для некоторых $x,y\in P$, значит $v=x-y\in D$. Обратно, если $v=x-y\in D$, то $y+v=x\in P$, т.е. $P\cap (P+v)\ne \varnothing$.
2) Пересечение с непустой внутренностью (настоящее «перекрытие»):
$$\mathrm{int}P\cap \mathrm{int}(P+v)\ne \varnothing ⟺v\in \mathrm{int}D.$$ Доказательство: множество $D$ выпукло; если $v\in \mathrm{int}D$, то в некоторой окрестности $v$ все сдвиги представимы как разности точек интерьера $P$, откуда существует точка общей внутренности. Обратно, если внутренности пересекаются, то существует пара внутренних точек $x,y\in \mathrm{int}P$ с $v=x-y$, значит $v\in \mathrm{int}D$.
3) Касание границ (без внутреннего перекрытия):
$$(P\cap (P+v)\ne \varnothing \text{и}\mathrm{int}P\cap \mathrm{int}(P+v)=\varnothing )⟺v\in \partial D.$$
Следствие (существование ненулевого сдвига с перекрытием). Так как $0\in \mathrm{int}D$ для любого выпуклого множества с непустой внутренностью, то в любой окрестности нуля есть ненулевые $v\in \mathrm{int}D$. Следовательно всегда существует ненулевой вектор сдвига, при котором $P$ и $P+v$ имеют непустое внутреннее пересечение (т. е. «самопокрытие» в смысле перекрытия).
Применение к разрезанию и упаковке.
- Критерий некроссинговой упаковки (транслевантной упаковки): пусть набор сдвигов $T\subset {\mathbb{R}}^2$ даёт упаковку копий $P+T=\{P+t:t\in T\}$ с непересекающимися внутренностями тогда и только тогда, когда для любых разных $t_1,t_2\in T$ $$t_1-t_2\notin \mathrm{int}D.$$ Иначе разность лежит в $\mathrm{int}D$ и соответствующие копии перекрываются.
- Тесселяция (упаковка с покрытием) решёткой. Пусть $\Lambda$ — решётка. Необходимые и (при допустимых условиях по границе) достаточные условия, чтобы семейство $\{P+\lambda :\lambda \in \Lambda \}$ давало тесселяцию ${\mathbb{R}}^2$:
a) $\Lambda \cap \mathrm{int}D=\{0\}$ (чтобы внутренности копий не пересекались);
b) $\mathrm{area}(P)=\det \Lambda$ (чтобы суммарная площадь копий равнялась площади плоскости в пределах фундаментального параллелограмма).
При выполнении (a) и (b) и при условии, что граница $P$ имеет нулевую меру, упаковка автоматически покрывает плоскость.
- Разрезание (диссекция) и реконструкция. При разрезании $P$ на части, которые затем переводят сдвигами $v_i$, для получения безперекрывающей сборки необходимо выбирать сдвиги так, чтобы разности между сдвигами не попадали в $\mathrm{int}D$. Для получения сознательного перекрытия (наложения частей) выбирают сдвиги из $\mathrm{int}D$; для касания по краю — сдвиги из $\partial D$. Для симметричных многоугольников критерии упрощаются: если $P$ центрально-симметричен, то $D=2P$, и условия сводятся к простому масштабированию.
Замечания по практическому вычислению. Множество $D=P-P$ — выпуклый (центрально-симметричный) многоугольник, его границу легко получить как Minkowski сумму $P+(-P)$. Поэтому в конкретной задаче вычисление запрещённой области сдвигов и проверка условий сводятся к простому вычислению геометрии $D$.
Таким образом: проверка существования ненулевого сдвига, приводящего к самопересечению/перекрытию, сводится к проверке принадлежности этого сдвига разностному телу $D=P-P$; критерии для упаковки и тесселяции формулируются через исключение разностей сдвигов из $\mathrm{int}D$ и через равенство площадей при тесселяции.