描述一组整数点的最小矩形集
给定一组 N 维整数点，如何找到最小的 N 维长方体集合（二维情况下为矩形），使得整数点位于整数点集合中当且仅当它包含在一个或多个长方体/矩形。 整数点表示具有整数坐标的点。
例如，给定点 (1,0)、(2, 0) 和 (3,1)、(4,1)，最小的矩形集是 (1,0-2,0)、(3,1-4) 1），见下图：
2 ..... 1 ...## 0 .##.. 01234
显然我可以进行强力搜索，但我正在寻找一种更有效的算法，即使它仍然具有很高的复杂性。
Given a set of N-dimensional integer points how do I find the smallest set of N-dimensional cuboids (rectangles in the 2-d case), such that an integer point is in the set of integer points if and only if it's contained in one or more of the cuboids/rectangles.
Integer point means a point with integer coordinates.
e.g. given the points (1,0), (2, 0) and (3,1), (4,1) the smallest set of rectangles is (1,0-2,0),(3,1-4,1), see diagram below:
2 ..... 1 ...## 0 .##.. 01234
Obviously I could do a brute force search, but I'm looking for a more efficient algorithm, even if it still has high complexity.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
我假设您愿意容忍重叠的矩形，因为如果这些点是
那么您可以用四个重叠的矩形覆盖，但需要五个不重叠的矩形。
这个算法怎么样：
对于每个点，找到包含该点的最大矩形。 最大的矩形是不能再变大但仍然只能覆盖点的矩形。 如果有两个最大的矩形，就选一个。 将最大的矩形存储在某种删除重复项的数据结构中。 完成对所有点的迭代后，矩形集必须覆盖所有点。
我不知道这是否实际上是一组最小的矩形，但我怀疑它是。
请注意，在上面的示例中，您将得到三个矩形：一个垂直矩形和两个水平矩形。
I assume that you are willing to tolerate overlapping rectangles, since if the points are
then you can cover with four overlapping rectangles, but would need five non-overlapping.
How about this algorithm:
For each point, find a largest rectangle containing that point. A largest rectangle is one that can't be made any bigger and still just cover the points. If there are two largest rectangles, just pick one. Store that largest rectangle in some sort of data structure that removes duplicates. After you've finished iterating over all the points, the set of rectangles must cover all the points.
I don't know if this is actually a minimal set of rectangles, but I suspect it is.
Note that in the example above, you would get three rectangles: One vertical and two horizontal.
定位现有点的方法有很多：
将点放入哈希映射中以便快速查找。 对于一般情况，这可能是最好的方法，在这种情况下，如果您尝试收集点，您将无法知道这些点会留下多少个洞。 在最坏的情况下，每个点都会得到一个矩形。
如果您有一个或几个 Z 坐标，请收集位图中的点（1 位深度）。 只需打开位图中的像素即可。
如果确实需要收集矩形中的点，则必须首先将它们放入有序集合中（按坐标）。 多次迭代这个集合。 每次，从集合中取出第一个点。 然后寻找与您已有的点左/右相邻的任何点。 如果有，将它们连接成一条（水平）线。 当你获得更多的点时，就增加这条线。
当没有剩下的点时，对线执行相同的操作以增长矩形。
There are many approaches to locate existing points:
Put the points into a hash map for quick lookup. This is probably the best approach for the general case where you can't know how many holes the points will leave if you try to collect them. In the worst case, you'll get one rectangle per point.
If you have one or few Z coordinates, collect the points in a bitmap (1 bit depth). Just turn the pixel in the bitmap on.
If you really need to collect the points in rectangles, you must first put them into an ordered set (by coordinate). Iterate over this set many times. Each time, take the first point out of the set. Then look for any point which is a left/right neighbor to the one you already have. If there is one, join them into a (horizontal) line. Grow that line as you get more points.
When there are no points left, do the same for the lines to grow rectangles.
一般情况是 NP 困难的：
http://www.computer.org/portal/web/ csdl/doi/10.1109/SFCS.1988.21976
看起来可以近似为 O(log N)。 在线查看“NP 优化问题纲要”，搜索“MINIMUM RECTANGLE COVER”
此外，您的特定用例可能仍然可以有效解决。
The general case is NP-hard:
http://www.computer.org/portal/web/csdl/doi/10.1109/SFCS.1988.21976
It looks like it can be approximated to O(log N). See "A compendium of NP optimization problems" online, search for "MINIMUM RECTANGLE COVER"
Also, it may be that your particular use case can still be solved efficiently.