均分田地，田埂最短问题

mathe

应该可以证明如果田地是凸形，那么最优划分，所有田埂都是直线段

mathe

Fans 11#的答案正好是他这种模式的图形中最有的，挺神奇的。
设正方形边长为1，假设这种图形中中间4段圆弧弧度为2t,对应半径为r,那么我们知道中间部分面积为
$4r^2(t-1/2sin(2t)+sin^2(t))=1/5$
而田埂总长度为$8rt+2(1-2sqrt(2)rsin(t))=2+4r(2t-sqrt(2)sin(t))$
根据第一个条件可以得出$r^2=1/{20(t-1/2sin(2t)+sin^2(t))}$
而我们要求$r(2t-sqrt(2)sin(t))$最小，也就是$r^2(2t-sqrt(2)sin(t))^2$最小
将$r^2$消去，变成求函数${(2t-sqrt(2)sin(t))^2}/{t-1/2sin(2t)+sin^2(t)}$的最小值的条件。
比较有意思的是这么复杂的一个函数，它的最小值竟然正好在$t=pi/12$时取到（通过数值计算100位验证，但是没有严格证明）

mathe

12# KeyTo9_Fans
hujunhua提到三条线交叉的点出夹角应该是${2pi}/3$, 并且圆弧应与既有边界保持垂直，不知道有什么理论依据，不过感觉这个结论应该很正确。于是对于12#的这种方案，我们应该选择两个中间的点都是三个夹角各${2pi}/3$,并且各个圆弧同边界相垂直，如图：

由此，得出四条圆弧应该都是15度($pi/12$)，于是最终总长度为
1.9755928847815
其中大圆半径为$sqrt({3*sqrt(2)}/{sqrt(2)pi-12sin(pi/12)})$

mathe

理论依据是：
....
造成的面积差异可通过旋转三角形外的曲线弥补。

于是调整后仍然满足平分面积的条件，但是总长度缩短了

感觉这部分理由不够充分

mathe

我觉得应该可以直接讨论更加一般的结论
如果不限定是不同部分面积不同，比如将单位正方形划分成三个部分，其中面积分别是事先给定的$S_1,S_2,S_3$,其中$S_1+S_2+S_3=1$,而要求边界总长度最短，那么也应该有相同的性质：
i)内部分界线每一段必然是圆弧或直线段（可以看成圆弧的退化情况）
ii)在内部，最多三个不同的分界线共点，这时必然两两夹角相等
iii)分界线和边界接触的地方必然同边界垂直

mathe

这个题目应该可以计算机模拟一下。
比如假设有n种不同的质点，每种质点有k个，分布在一个正方形中，任意两个质点之间有排斥力$c/{r^u}$,其中
c是常数，根据两个质点是否同一种可以取两个不同的值（不同物质之间排斥力略大）。而其中u我不知道取多少比较合理，也许是1或2.
然后看模型状态平稳下来以后是何状态，很可能就可以给出本题一些比较合理的解。

mathe

我们只需要求稳定状态，实际上是解一个高阶方程

mathe

参考火车站问题n=6的解，我们可以构造如下图类型的图案:

图片上下对称，其中4条圆弧全部是30度圆弧。
这个应该比等分六份强。只是具体计算坐标还是挺复杂的。

mathe

我们可以利用角度来推断。
比如AEGNF等四个“五边形”中，我们知道内角和要求是90*3+120*2=510,比正常五边形小30度
所以只要一条凹向内部的30度弧就可以到达调整的目的。
而AEGNF中FN根据对称性应该是直线段，比较合适的是调整NG.
然后计算五边形NGHJK,在经过NG和NJ角度的调整后，总角度已经匹配，所以这时我选择GH,HK,KJ都是直线段。

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度）