令M的多边形各具有重量w_i，写一个快速算法，输出n个多边形，使得：
- 没有两个多边形相交
- \总结w_i被最大化组给定的多边形的，希望得到尽可能多的不相交的多边形尽可能
当输入多边形是轴对齐的矩形时，是否有可能进行优化？非轴对齐的矩形？
添加一些参考：
1. Label Placement by Maximum Independent Set in Rectangles
2. Maximum Independent Set of Rectangles
3. Finding maximum non-overlapping intervals in 1 dimension
假设正的权重，只有不相交的多边形的最大子集被认为是（如果从最大删除一个元素子集，总和减少）。
您可以尝试一种增量式方法：假设对于M个第一个多边形，您已找到所有非相交多边形的最大子集。考虑多一个多边形。您将通过考虑所有可用的子集并从中删除与新的子集交叉的所有多边形，形成新的最大非相交子集。例如：A，B，C，D。A和B相交，A和C相交。
从{A}开始。
Add B. Form {A，A U B}。从A和B中丢弃A.你保留{A，B}。
Add C. Form {A，B，A U C，B U C}。从A U C中丢弃A并在B U C中吸收B.保留{A，B U C}。
Add D. Form {A，B U C，A U D，B U C U D}。你在B U C U D中吸收B U C并保持{A U D，B U C U D}。
解决方案是总和最大的最大子集。
通过穷尽搜索（O（N^2）交点计算）或更有效的方法（可能低至O（N.Lg（N）+ K）交点计算）预先计算交点可能会更好。
但亚群的建设可能是多边形的数量呈指数:(我不知道。
它也可能是一个动态的方法将让你得到更早摆脱某些子集（处理例如通过增加或减少交叉点的数量来确定多边形？）
你忽略了目标是找到具有最大价值的独立性。尽管这在很大程度上改变了检查子集的顺序。 – Nuclearman
根本不是。我说1）假设正权重，只考虑非交叉多边形的最大子集。 2）解决方案是总和最大的最大子集。 3）动态方法也可以让你在早些时候摆脱某些子集... –
您可以将这个问题作为图形来处理，图形节点是您的多边形，图形边缘意味着“无交集” - 然后您的问题变成最大集团问题。请参见图表here中关于集团的一般讨论。也搜索“最大权重集团算法”。
谈到一种实用的方法 - 您可以尝试Boost Graph Library，它包含算法来列出图中的所有派系。
当然，这种方法需要您提前计算所有的成对交点。所以，问题正在减少到另一个 - 给定一组多边形，找到一个计算“非相交”矩阵的快速方法。我认为，这个可以通过飞机清扫解决。
由于您正在绑定最大化总和。尝试将所有矩形分成若干独立集（通过贪婪算法），然后尝试将它们合并在一起以查看造成的交集，可能会更好。这可能是有益的，因为目标是创造一个高价值的独立集合。 – Nuclearman