问一个算法题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

问一个算法题

问一个算法题# JobHunting - 待字闺中

e*e2011-03-10 08:03

1 楼

今天被人问到一个问题，想不清楚，大家来讨论讨论：
平面中散布着若干rectangle，顶点坐标为floating，两两之间有可能会发生重叠。问
如何找到矩
形重叠最多的那个区域。要求算法尽量efficient.

e*e2011-03-10 08:03

2 楼

如果这个问题是一维的求线段的most overlapping segment，sweeping line应该就能
搞定了，需要nlog(n)的时间。但是现在是二维，我有点想不清楚

s*y2011-03-10 08:03

3 楼

平面离散化, 每一个区域统计被覆盖的次数.

w*02011-03-10 08:03

4 楼

这些矩形的边都平行于x,y轴吗？还是可以旋转成任意角度？

【在 e****e 的大作中提到】

: 今天被人问到一个问题，想不清楚，大家来讨论讨论：
: 平面中散布着若干rectangle，顶点坐标为floating，两两之间有可能会发生重叠。问
: 如何找到矩
: 形重叠最多的那个区域。要求算法尽量efficient.

e*e2011-03-10 08:03

5 楼

但是顶点不是floating的，这个怎么解决
另外，space的efficiency太低。
我想到的是构建hanan grid，然后基于每一个grid统计，但是这样的空间复杂度是n^2
，不知道还
有没有更好的办法

【在 s********y 的大作中提到】

: 平面离散化, 每一个区域统计被覆盖的次数.

e*e2011-03-10 08:03

6 楼

出题人的意图应该是平行于x,y轴的，不过如果能够旋转的话，好像更有意思的咯

【在 w********0 的大作中提到】

: 这些矩形的边都平行于x,y轴吗？还是可以旋转成任意角度？

D*d2011-03-10 08:03

7 楼

it seems that a rectangle could be represented by center, radius and
diagonal angle.
Just guessing

g*s2011-03-10 08:03

8 楼

这个好像是一道当年的acm/icpc试题，不过当时没去做。
给一个所有x,y没有相同值的基本思路：
把所有的矩形的左边和右边按x排序（），总共有2n条边。
初始话一个 hashmap A (float->int) 用来记录：对于记录当前x值下，对于点y，有多
少个重复。
同时，需要保存一个当前排好序的所有y值的队列R
从左向右扫描这2n条边。
对于左边，
× 检查R里面的点，被这条边覆盖。对于这些点，更改A里面的值 ++1
× 加入到边的两点的y值加入到A和R里面，A里面的值设为1
对于右边：
× 检查R里面的点，被这条边覆盖。对于这些点，更改A里面的值 --1
× 从A和R删除这两点。
在这个过程中，A里面出现的最大值就是最大overlapping最多的数目
最坏的可能性是O(n^2).

s*y2011-03-10 08:03

9 楼

离散化是指只存端点, 端点的话是float还是int没有关系啊, space complexity是O(n)
的, n是矩形个数.

2

【在 e****e 的大作中提到】

: 但是顶点不是floating的，这个怎么解决
: 另外，space的efficiency太低。
: 我想到的是构建hanan grid，然后基于每一个grid统计，但是这样的空间复杂度是n^2
: ，不知道还
: 有没有更好的办法