先取n个点中距离最小两点a,b
计算 除b外到a点最小值 d1
除a外到b点最小值d2
如果d1大于d2,则目标集合p不包括点b,删除b即可
如果d1大于d2,同理删除a。如果d1等于d2,随便删除a或者b
下面说明算法正确性
目标集合显然存在,不唯一,记其中一个n—m点集合为p,这些点最小距离为c(p)
如果d1大于d2,b包含在p中,以a点代替b构成新的n—m个p’点,这些点最小距离c(p’)不小于c(p)
【 在 lovellc 的大作中提到: 】:
已知平面内有n个点,从中删除m个,使剩下的点之间最小距离(欧氏距离)最大,有没有算法可以找出这m个点。
--
FROM 101.88.203.*