均分田地，田埂最短问题

056254628

43楼是否计算有错误？
按照43#的数据，中心图形的面积=0.20194975940609
而1/5面积，应=Pi/5=.628318530717959

056254628

n=5时，我的计算结果是：
中间四段圆弧（弧度为30°，半径为1.41085739578963），四个接点处向圆周辐射（各长0.483203729134676），总边界长度=4.88997201811376

hujunhua

n=5时，我的计算结果是：
中间四段圆弧（弧度为30°，半径为1.4119961813351850581103676413843），
四个接点处向圆周辐射（各长0.48317352758470343730345702574027），
总边界长度=4.8899719971251196888414772326709

hujunhua

.........
但是线与边界的夹角却不是90度，违反了与边界垂直的潜规则。
056254628 发表于 2010-11-21 12:36

经过初步估算，使用圆弧，满足与边界垂直的规则，总长大约还能改进0.015.

gxqcn

51# 056254628

仔细检查了一下，我一处计算有误，53# hujunhua 的结果是正确的。

gxqcn

...
$n=6$ 时，中间一梅花形，每瓣是以2.574半径为半径，12°为圆心角的圆弧，5个顶点向圆周辐射（各长0.5423），总边界长度=5.407
gxqcn 发表于 2010-11-19 10:45

有谁来计算一下，当 $n=6$ 时，下面这种方案是否会更优？

其中与外圆相交的是六段圆弧，它们垂直于外圆，且与内三叉形成120°夹角（上图为示意图，仅供参考）。

056254628

按照56楼的图形要求：
我的计算是：
六段圆弧，每段的弧度=0.405862342753588(换成角度约为23.25°)，半径=1.98563064939495
两段圆弧截得的外周圆弧的弧度=1.28267041688602(换成角度约为73.5°)
中心三个小段，每段长=0.269626133216857
总长度=5.64423464289114

KeyTo9_Fans

47楼图，凭直觉，总长应该大于两横一竖的方案，也就是说会大于3。
056254628 发表于 2010-11-21 13:33

我是根据两横一竖的方案，将其调整成三叉状的。

怎么总长度反而大了？

mathe

我觉得应该可以直接讨论更加一般的结论
如果不限定是不同部分面积不同，比如将单位正方形划分成三个部分，其中面积分别是事先给定的$S_1,S_2,S_3$,其中$S_1+S_2+S_3=1$,而要求边界总长度最短，那么也应该有相同的性 ...
mathe 发表于 2010-11-12 17:00

这个问题的一般结论现在还缺乏理论方面的支持:
i)内部分界线每一段必然是圆弧或直线段（可以看成圆弧的退化情况）
ii)在内部，最多三个不同的分界线共点，这时必然两两夹角相等
iii)分界线和边界接触的地方必然同边界垂直  
其中，i)我们可以用纯初等的方法来反证，这个只要利用面积一定的封闭图形中圆的边长最短来得出固定面积的弓形（一侧固定线段，另外一侧任意曲线）中，圆弧的长度最短来反证。
而对于iii),由于边界是直线段，我们可以将图形按边界做出对称图形，然后将边界线抹去（也就是边界线两边的区域合并成一个区域），对于合并以后的图形，根据条件i)就可以得出原图形中的条件iii).
所以主要余下的是条件ii),而且我们已经知道所有分界线都是圆弧。
而对于三条分界线共点:
假设周边三个点A,B,C的坐标为$(x_a,y_a),(x_b,y_b),(x_c,y_c)$，这三个坐标已知
待定点P为三条分界线的公共点，坐标为$(x_p,y_p)$
记${(L_a=sqrt((x_p-x_a)^2+(y_p-y_a)^2)),(L_b=sqrt((x_p-x_b)^2+(y_p-y_b)^2)),(L_c=sqrt((x_p-x_c)^2+(y_p-y_c)^2)):}$
也即是$L_a,L_b,L_c$是直线段AP,BP,CP的长度。
分别假设$2\theta_a,2\theta_b,2\theta_c$为三条弧AP,BP,CP的弧度，而且它们的半径分别为$R_a,R_b,R_c$
于是我们知道
$2R_a sin(\theta_a)=L_a$
所以
$R_a={L_a}/{2sin(\theta_a)}$
而直线AP和弧线AP所夹部分面积为$D(A)=1/2 R_a^2(2\theta_a-sin(2\theta_a))={L_a^2}/8{2\theta_a-sin(2\theta_a)}/{sin^2(\theta_a)}$
而弧线AP的长度为$2R_a\theta_a=L_a{\theta_a}/{sin(\theta_a)}$
我们可以记函数$f(x)=x/{sin(x)},g(x)={2x-sin(2x)}/{sin^2(x)}$
于是弧线三角形ABP的面积为三角形ABP的面积加上$D(A)$再减去$D(B)$,即
$S_{ABP}=1/2(x_ay_p-y_ax_p+x_by_a-x_ay_b+x_py_b-x_by_p)+{L_a^2}/8g(\theta_a)-{L_b^2}/8g(\theta_b)$
同样可以有
$S_{BCP}=1/2(x_by_p-y_bx_p+x_cy_b-x_by_c+x_py_c-x_cy_p)+{L_b^2}/8g(\theta_b)-{L_c^2}/8g(\theta_c)$
$S_{CAP}=1/2(x_cy_p-y_cx_p+x_ay_c-x_cy_a+x_py_a-x_ay_p)+{L_c^2}/8g(\theta_c)-{L_a^2}/8g(\theta_a)$
而弧线AP,BP,CP的长度之和为
$T=L_af(\theta_a)+L_bf(\theta_b)+L_cf(\theta_c)$
我们的目的是在给定约束条件$S_{ABP},S_{BCP},S_{CAP}$为常数的条件下，求T的最小值，其中$x_p,y_p,\theta_a,\theta_b,\theta_c$为变量，也就是P点可以移动，而且弧线PA,PB,PC的曲率可以改变:
记$H=T+u_AS_{BCP}+u_BS_{CAP}+u_CS_{ABP}$,其中$u_A,u_B,u_C$为待定系数
于是
${\delH}/{\del\theta_a}=L_af'(\theta_a)-u_B{L_a^2}/8g'(\theta_a)+u_C{L_a^2}/8g'(\theta_a)$
${\delH}/{\del\theta_b}=L_bf'(\theta_b)-u_C{L_b^2}/8g'(\theta_b)+u_A{L_b^2}/8g'(\theta_b)$
${\delH}/{\del\theta_c}=L_cf'(\theta_c)-u_A{L_c^2}/8g'(\theta_c)+u_B{L_c^2}/8g'(\theta_c)$
${\delH}/{\delx_p}={x_p-x_a}/{L_a}f(\theta_a)+{x_p-x_b}/{L_b}f(\theta_b)+{x_p-x_c}/{L_c}f(\theta_c)+1/2u_A(y_c-y_b+{x_p-x_b}/2g(\theta_b)-{x_p-x_c}/2g(\theta_c))$
$+1/2u_B(y_a-y_c+{x_p-x_c}/2g(\theta_c)-{x_p-x_a}/2g(\theta_a))+1/2u_C(y_b-y_a+{x_p-x_a}/2g(\theta_a)-{x_p-x_b}/2g(\theta_b))$
${\delH}/{\dely_p}={y_p-y_a}/{L_a}f(\theta_a)+{y_p-y_b}/{L_b}f(\theta_b)+{y_p-y_c}/{L_c}f(\theta_c)+1/2u_A(x_b-x_c+{y_p-y_b}/2g(\theta_b)-{y_p-y_c}/2g(\theta_c))$
$+1/2u_B(x_c-x_a+{y_p-y_c}/2g(\theta_c)-{y_p-y_a}/2g(\theta_a))+1/2u_C(x_a-x_b+{y_p-y_a}/2g(\theta_a)-{y_p-y_b}/2g(\theta_b))$
由于$L_a,L_b,L_c$都不是0，所以取极值时，由前面三个导数为0，我们可以得到
${(u_B-u_C={8f'(\theta_a)}/{L_ag'(\theta_a)}),(u_C-u_A={8f'(\theta_b)}/{L_bg'(\theta_b)}),(u_A-u_B={8f'(\theta_c)}/{L_cg'(\theta_c)}):}$
三式相加，我们得到约束条件i)
${f'(\theta_a)}/{L_ag'(\theta_a)}+{f'(\theta_b)}/{L_bg'(\theta_b)}+{f'(\theta_c)}/{L_cg'(\theta_c)}=0$
整理后面的偏导数，得到
${\delH}/{\delx_p}={x_p-x_a}/{L_a}f(\theta_a)+{x_p-x_b}/{L_b}f(\theta_b)+{x_p-x_c}/{L_c}f(\theta_c)+1/2y_c(u_A-u_B)+1/2y_b(u_C-u_A)+1/2y_a(u_B-u_C)$
$+{x_p-x_b}/4g(\theta_b)*(u_A-u_C)+{x_p-x_c}/4g(\theta_c)*(u_B-u_A)+{x_p-x_a}/4g(\theta_a)(u_C-u_B)$
$={x_p-x_a}/{L_a}f(\theta_a)+{x_p-x_b}/{L_b}f(\theta_b)+{x_p-x_c}/{L_c}f(\theta_c)+4y_c{f'(\theta_c)}/{L_cg'(\theta_c)}+4y_b{f'(\theta_b)}/{L_bg'(\theta_b)}+4y_a{f'(\theta_a)}/{L_ag'(\theta_a)}$
$-(x_p-x_b){2g(\theta_b)*f'(\theta_b)}/{L_bg'(\theta_b)}-(x_p-x_c){2g(\theta_c)*f'(\theta_c)}/{L_cg'(\theta_c)}-(x_p-x_a){2g(\theta_a)*f'(\theta_a)}/{L_ag'(\theta_a)}$
$={x_p-x_a}/{L_a}(f(\theta_a)-{2g(\theta_a)f'(\theta_a)}/{g'(\theta_a)})+{x_p-x_b}/{L_b}(f(\theta_b)-{2g(\theta_b)f'(\theta_b)}/{g'(\theta_b)})+{x_p-x_c}/{L_c}(f(\theta_c)-{2g(\theta_c)f'(\theta_c)}/{g'(\theta_c)})$
$+4{y_a}/{L_a}{f'(\theta_a)}/{g'(\theta_a)}+4{y_b}/{L_b}{f'(\theta_b)}/{g'(\theta_b)}+4{y_c}/{L_c}{f'(\theta_c)}/{g'(\theta_c)}$
再次由于约束条件i)，我们可以将上式减去约束条件的$-4y_p$倍，得到约束条件ii)
${\delH}/{\delx_p}=sum ({x_p-x_a}/{L_a}(f(\theta_a)-{2g(\theta_a)f'(\theta_a)}/{g'(\theta_a)})+4{y_a-y_p}/{L_a}{f'(\theta_a)}/{g'(\theta_a)})=0$
同样可以得到约束条件iii)
${\delH}/{\dely_p}=sum ({y_p-y_b}/{L_a}(f(\theta_a)-{2g(\theta_a)f'(\theta_a)}/{g'(\theta_a)})-4{x_a-x_p}/{L_a}{f'(\theta_a)}/{g'(\theta_a)})=0$
上面的求和都是分别将下标a轮换改成b和c求和
也就是说，我们需要查看能否根据这三个约束条件得出三个角都相等的条件.
而如果进行数值计算，那么就可以直接利用这些方程，使用牛顿迭代法进行计算。
其中角度($\theta_a,\theta_b,\theta_c$都是有向的）
特别的，如果选择这些角度都是0（也就是限制所有线段都是直线段，那么由于${f'(x)}/{g'(x)}|_{x=0}=0$,相当于要求$\sum{x_p-x_a}/{L_a}=0,\sum{y_p-y_a}/{L_a}=0$,也就是三个方向单位向量之和为0向量，就是直线段两两夹角都是120度）

mathe

上面的分析仅仅对于边界是矩形的情况适用。而对于边界是圆的情况，连接到边界的分割线不一定会同圆周垂直。
我们不妨设这个圆是单位圆，分割线圆内端点坐标为$(x_0,y_0)$,另外一个点是动点$(cos(u),sin(u))$
而分割线弧度为$2\theta$,对应半径为$R$,于是记
$L=sqrt((x_0-cos(u))^2+(y_0-sin(u))^2)$
$2Rsin(\theta)=L$
弧线长度为$2R\theta=L\theta/{sin(\theta)}$
最后简化得出极值情况的要求是:
$(sin(2\theta)-\theta cos(2\theta)-\theta)/(\theta sin(2\theta)+cos(2\theta)-1)=cos(u)y_0-sin(u)x_0$