研究成果与问题 / Research results and questions¶

按研究状态组织，保留当前结论与探索过程。证明状态表示仓库提供了文字证明；有限实验不替代一般证明。

Organized by research status. A proof record indicates a written proof in this repository; finite experiments do not establish a general theorem.

已给出证明 · Proof provided¶

已给出证明 · Proof provided

四邻接网格森林平移匹配的三次方复杂度上界¶

A cubic time bound for translation matching in four-neighbor grid forests

对只在新位移处筛选的候选列表算法，完整历史的收费证明去掉了对数因子，得到一般森林上的 O(n³+m) 上界。

Complete-history charging removes the logarithmic factor for candidate-list filtering at new displacements, giving O(n³+m) time on general forests.

中文 · English

稳定标识 / ID: grid-forest-matching-cubic-bound

改进: grid-forest-matching-logarithmic-bound

已给出证明 · Proof provided

诱导四邻接网格森林不一定能通过补点扩充成树¶

Induced four-neighbor grid forests need not extend to trees by adding vertices

保持原位置与全部四邻接边时，补点不一定能把森林连成树；这种障碍可以扩展到线性数量、每棵线性大小的路径。

With positions and all induced edges preserved, adding vertices need not connect a forest into a tree—even for linearly many paths of linear size.

中文 · English

稳定标识 / ID: induced-grid-forest-tree-extension-obstructions

已给出证明 · Proof provided

仅对角邻接的网格森林：奇偶拆分与三次方界¶

Diagonal-only grid forests: parity decomposition and cubic bounds

只允许四个对角方向时，两种奇偶类各自同构于四邻接网格，保留原检查次数上界与三次方最坏量级；补树障碍也可迁移。

With diagonal directions only, each parity class is isomorphic to an orthogonal grid, preserving the check bound, cubic worst-case order, and tree-extension obstructions.

中文 · English

稳定标识 / ID: grid-forest-matching-diagonal-only

推广: grid-forest-matching-cubic-bound · 推广: induced-grid-forest-tree-extension-obstructions

已给出证明 · Proof provided

八邻接诱导森林：三次方复杂度仍然成立¶

Eight-neighbor induced forests retain the cubic bound

同时允许正交和对角方向时，秩四方向词保留完整历史收费与有限第二轴引理，得到相同的检查次数上界和三次方最坏量级。

With both orthogonal and diagonal moves, rank-four direction words preserve complete-history charging and the finite second-axis lemma, giving the same exact check bound and cubic worst-case order.

中文 · English

稳定标识 / ID: grid-forest-matching-eight-neighbor

推广: grid-forest-matching-cubic-bound · 相关: grid-forest-matching-diagonal-only

已给出证明 · Proof provided

顶点与路径障碍：四邻接、八邻接仍有三次方界¶

Vertex and edge obstacles: cubic bounds for four and eight neighbors

只要求实际开放边构成森林时，修改重复位置规则并使用公共开放边交域，仍保留原精确检查次数上界和三次方最坏量级。

When only the actual open-edge graph is a forest, revised revisit handling and common open-edge intersections preserve the exact check bound and cubic worst-case order.

中文 · English

稳定标识 / ID: grid-forest-matching-edge-obstacles

推广: grid-forest-matching-cubic-bound · 推广: grid-forest-matching-eight-neighbor

已给出证明 · Proof provided