关于点的分布问题

aimisiyou · 发表于 2020-3-24 17:43:20

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

本帖最后由 aimisiyou 于 2020-3-25 01:50 编辑

在n×n的方格网上最多可以选取多少个网点，使得任意四个点(x1, y1), (x2, y2), (x3, y3) 和 (x4, y4) 均不满足{x1+x2=x3+x4 and y1+y2=y3+y4}.
n=32时，点数m=?

aimisiyou · 发表于 2020-3-25 11:59:24

本帖最后由 aimisiyou 于 2020-3-25 13:49 编辑

感觉有些类似筛法。

hujunhua · 发表于 2020-3-25 23:09:25

在n×n的方格网上最多可以选取多少个网点，使得其中任意四点都不是一个平行四边形（包括四点共线的退化情形）的顶点。

aimisiyou · 发表于 2020-3-26 11:11:09

本帖最后由 aimisiyou 于 2020-3-26 11:20 编辑

hujunhua 发表于 2020-3-25 23:09
在n×n的方格网上最多可以选取多少个网点，使得其中任意四点都不是一个平行四边形（包括四点共线的退化情形 ...

恩，是的。有没有好的算法。另外我不确定是否从第一个选取，判断后续是否可选的结果是最优的（比如不选第一个，从选第二个开始，再判断后续是否可选的结果可能更好）。若按皇后问题思路，运算量又太大了。

zeroieme · 发表于 2020-3-26 12:14:31

是否包括四点共线？ 1#2#的图有四点共线。

aimisiyou · 发表于 2020-3-26 12:28:33

本帖最后由 aimisiyou 于 2020-3-26 12:32 编辑

zeroieme 发表于 2020-3-26 12:14
是否包括四点共线？ 1#2#的图有四点共线。

只要不满足广义平行四边形，四个点可以共线。每点可以看成一个复数，即要求任意两个复数之和都不相等。

账号		自动登录	找回密码
密码			欢迎注册

[讨论] 关于点的分布问题

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。