绪论

均分田地问题中,gxqcn提出了如下问题

有一块田地需要分给n户家庭,要求各户分得面积都相等。田地内部不同家庭分得的区域将建田埂以分隔(原待分地已有田埂圈定)。现为实现耕地面积最大化,要求新建田埂总长度最小。请问如何规划?

关于这个问题的三维问题,存在Plateau’s laws

在这块田地是单位正方形,对于n=3,4,5, KeyTo9_Fans分别给出了很不错的结果:

n=3时, 田埂总长度可以仅为\frac23+\frac{\pi}6+\sqrt{3}=1.623278144157 (我们可以搜索到法语论坛相关讨论得出了相同的结果)
s3c

n=4时,田埂总长度可以仅为\sqrt{2}+\sqrt{1-\sqrt{3}+\frac{\pi}3}=1.975592884782 (我们可以搜索到意大利语相关讨论得出了相同的结果)
s4c

n=5时, 田埂总长度可以为2+((1+\sqrt{3})\pi-6) \sqrt{\frac{2}{15((2+\sqrt{3})\pi-3(1+\sqrt{3}))}}=2.502112930427 (可以网络找到Martin Gardner包含相同的结果)
s5c

对于单位圆形田地,在n=3时,从圆心发出三条两两夹角互为120°的半径就可以等分面积,总长度为3。

在n=4时,我们给出了田埂总长为3.945702967267的方案
c4

在n=5的圆形田地,我们找出了田埂总长为4.833846643527的方案
c5

在n=6的圆形田地,我们找出了田埂总长为5.406796929952的对称方案
c6

在n=7的圆形田地zgg__和数学星空指出在田地正中心使用正六边形,每个顶点向圆周引垂线可得田埂总长为6的方案

在帖子中,很早就有人发现每段田埂应该是直线段或者圆弧;在区域内部,三条田埂相交于一点时,交点处切向量两两夹角为120°;而且田埂和田地边界相遇时在相遇点的切线要和田地边界在相遇点的切线垂直。后文中,我们会直接用俩田埂的夹角为120°来表示俩田埂相遇于一个交点,而且在交点处的切向量夹角为120°;同样我们会直接用田埂和田地边界垂直代表田埂和田地边界相遇并且在相遇点两者切线相互垂直。

KeyTo9_Fans最早指出田埂两两夹角为120°。他的思路是如下图,在仅考虑三条田埂相交于点P的情况,分别在三条田埂上各自选择充分接近P点的A、B、C三点。为了达到田埂总长最小值,P点应该移动到三角形ABC的费马点才会让AP+BP+CP取到最小值,由此得出AP、BP、CP两两夹角应该为120°。但是这里稍微有点不严密,因为图中这种移动P到P’的方式会改变周围三个区域的面积,而我们的问题中要求所有区域的面积要求是相等的。
fermat

zgg__最早指出,本问题等价于二维肥皂泡稳态问题,由此得出每段田埂都必须是圆弧或直线段,而且两两夹角为120°;hujunhua进一步指出利用肥皂泡模型可以说明和田地边界相遇的田埂必然垂直于田地边界;gxqcn紧接着指出在区域数目n充分大时,内部区域应该出现“蜂窝”状。
我们对上面情况进行总结,并且尝试用数学方法进行证明:

i)田埂每一段必然是圆弧或直线段(可以看成圆弧的退化情况)。
ii)在内部,最多三个不同的田埂共点,这时田埂之间必然两两夹角相等
iii)田埂和边界接触的地方必然同边界垂直

其中性质i)可以直接用初等方法证明。我们可以利用一个大家所熟知的结论:面积一定的简单平面图形中,圆的周长最短。利用这个结论可以得出一侧为固定线段,另一侧为任意简单曲线围成的面积一定的图形中,在另一侧任意简单曲线为圆弧时,这条简单曲线长度达到最短。

arc
如上图所示,对于围住的面积固定的曲线BAC和固定直线段BC,我们先以线段BC为弦作出和这个图形等面积的弓形BA’C并且补充弓形BA”C形成一个完整的圆BA’CA”。于是图形BACA”和图形BA’CA”等面积,于是我们根据等面积图形中圆的周长最小可以得出(BA”C) ̂+(BA’C) ̂≤(BA”C) ̂+(BAC),所以我们可以得出(BA’C) ̂≤(BAC),得出结论i)。 于是我们得出极值条件所有田埂都是圆弧或直线段(直线段是圆弧的退化情况)。
后面我们均只需要考虑所有田埂都是直线段或圆弧的情况。

对于其中任意一个三条田埂汇聚于一点的P(x_p,y_p )的情况,假设这三段田埂另一个端点分别为A(x_a,y_a ),B(x_b,y_b ),C(x_c,y_c), 而三段圆弧和对应端点连线的有向夹角分别为\theta_a,\theta_b,\theta_c (对应三段圆弧的弧度分别为2\theta_a,2\theta_b,2\theta_c)。 其中圆弧关于P点向顺时针方向凸出(也就是对应圆心落在对应直线段的逆时针位置时)对应的\theta_s看成是正角度;而圆弧逆顺时针凸出时,对应的\theta_s看成是负角度,比如图中所示\theta_a,\theta_b为负角度,\theta_c为正角度。另外需要注意的是,一段田埂在一个端点处的角度为\theta,那么在另外一个端点处的角度必然是-\theta

basic

使用拉格朗日乘数法,选择A、B、C三点固定不动,仅让P点保持运动并且让P点周围三个区域的面积保持不变,要求三条田埂长度之和最小,可以得出一些约束方程,
最后可以把极值约束条件化简
\begin{cases} F_1=\frac{\sin⁡(\theta_a)}{L_a} +\frac{\sin⁡(\theta_b)}{L_b} +\frac{\sin⁡(\theta_c)}{L_c} =0\\ F_2=D_{a,x}+D_{b,x}+D_{c,x}=0\\ F_3=D_{a,y}+D_{b,y}+D_{c,y}=0 \end{cases} (I)

其中
\begin{cases} D_{s,x}=\frac{x_s-x_p}{L_s}\cos⁡(\theta_s)+\frac{y_s-y_p}{L_s}\sin⁡(\theta_s )\\ D_{s,y}=\frac{y_s-y_p}{L_s}\cos⁡(\theta_s)-\frac{x_s-x_p}{L_s}\sin⁡(\theta_s )\\ L_s=\sqrt{(x_p-x_s )^2+(y_p-y_s )^2 }\\ s\in \text{{a,b,c}} \end{cases}

上面约束条件(I)中第一条方程代表三段圆弧(或直线段)有向曲率之和为0。而后面两条方程代表三段圆弧在P点处单位切线向量之和为零向量,所以它们两两夹角都相等,均为120°(P点同时为三个单位切线向量末端构成三角形的外心和重心,所以这是一个正三角形)。

对于边界为直线段构成的凸田地,可以想象如果某个田埂的一个端点落在田地边界上,那么将整个田地和所有田埂关于这个边界线做对称图形,然后把原图形和对称图形合并在一起并且将仅被这条分界直线段分隔的区域相互合并,于是变成一个关于更大的田地更多区域的固定面积最优化问题,结果同样需要满足类似的约束条件。于是我们可以看出在原问题中,这个田埂必须垂直于田地边界才符合要求。

另外我们推导了田地边界是圆弧构成的情况,同样得出了和边界相遇的田埂必须垂直于圆弧田地边界的条件。

boundary
如图,不妨设田地边界这一段圆弧为单位圆的圆弧,设田埂在边界上点为U(\cos⁡(u),\sin⁡(u) ),田埂另外一个端点为点P(x_0,y_0 ),圆弧和俩端点连线夹角为\theta。并且设P点极坐标为(r_0,θ_0 ), 得出的约束条件为
\tan⁡(\theta)-\frac{r_0\sin⁡(u-\theta_0 )}{1-r_0\cos⁡(u-\theta_0 )}=0
E_1=\sin(\theta)(1-\cos⁡(u) x_0-\sin⁡(u) y_0 )-\cos⁡(θ)(\sin⁡(u) x_0-\cos⁡(u) y_0)=0 (II)

这个条件正好就是要求田埂(UP) ̂垂直单位圆田地边界于U点。

利用上面分析结论我们使用计算机将正方形田地均分到最多14个区域并且将圆形田地均分到最多19个区域.
但是很快我们发现英国数学家Simon Cox已经计算到42个区域以内的非常不错的结果。

后来我们利用pari/gp计算出了圆形情况不超过43个区域下的50位精度的高精度结果。 点击链接可以下载关键点的坐标和圆弧角度的高精度结果
另外我们还继续计算得出将圆形划分44~52个区域时的不错结果,如下面是将圆形田地划分为44个区域的划分方案图:
c44

更多内容…