[转载]关于一个平面内矩形个数的问题

作者:CSDN:wang3312362136
原文地址:关于一个平面内矩形个数的问题 – wang3312362136
转载已授权,下面正文


问题

一个平面内的n个点,以这n个点为顶点,
最多能构成多少个矩形?点的排列是自己决定的。
先说结论:构成矩形的个数,上下界分别是:
O(n^2\sqrt n) Ω(n^2)


上界

记Ca,b表示a,b为直径的圆。
对于每一个点pi,如果pa,pb,pc,pd能构成一个矩形,当且仅当CPa,Pc=CPb,Pd
记di为Ci上相反的点来说,就是说di=|{(pj,pk)|Ci=CPj,Pk}|。
可以得出,矩形个数就是以下式子
\sum^m_{i=1}\frac{d^i\times(d_i-1)}2,\sum^m_{i=1}d_i=\frac{n\times(n-1)}2
我们假设d1≤d2≤⋯≤dn。记k满足如下式子
d_k>2\sqrt n,d_{k+1}\leqslant 2\sqrt n
由于两圆只可能交于两点,因此可以得到k\leqslant\sqrt n
证明:如果k>\sqrt n,设点的个数为m,可以发现m满足以下关系
m\geqslant\sum^k_{i=1}(2d_i-2(i-1))>4k\sqrt n-k(k-1)4n-n+\sqrt n>n
因此,k2≤n一定是成立的。
那么矩形个数就是
\sum\limits^m_{i=1}\frac{d_i\times(d_i-1)}2\leqslant\sum\limits_{i=1}^md^2_i=\sum\limits_{i=1}^kd^2_i+\sum\limits_{i=k+1}^md^2_i\leqslant\sum\limits^n_{i=1}(2\sqrt n)^2\leqslant=O(n^2\sqrt n)
因此,n个点能构成的矩形个数的上界是O(n^2\sqrt n)


下界

构造一个网格,边长为\sqrt n,每选择两个点,必定能构成一个边平行于坐标轴的矩形,这样的矩形个数显然是\Omega(n^2)。显然还有可能其他的矩形,这里不做考虑。
点我回到主页

发表评论

Fill in your details below or click an icon to log in:

WordPress.com 徽标

You are commenting using your WordPress.com account. Log Out /  更改 )

Google+ photo

You are commenting using your Google+ account. Log Out /  更改 )

Twitter picture

You are commenting using your Twitter account. Log Out /  更改 )

Facebook photo

You are commenting using your Facebook account. Log Out /  更改 )

Connecting to %s