我正在使用层次聚类来尝试可视化已被展平为二维的大量数据 . 我想要做的是创建一个可视化，允许我通过将簇作为其组成点的凸包来查看层次结构中不同高度的数据 . 这个问题中最棘手的部分是我需要一种能够在向上移动层次结构时有效地合并对簇的凸包的算法 . 我已经看到很多用于计算O（n log n）时间点的凸包的算法，但在这种情况下似乎更有效地利用问题的子结构，但我是不确定如何 .
Edit:
有关更多信息，数据结构是一个以聚类的原始点开头的数组，然后说明哪些点/聚类组合在一起形成下一个聚类 . 所以它有点像树/指针结构，但包含在一个大数组中 . 重要的一点是，查看两个组成集群的任何超级集群是否有效，但获取属于集群的所有点的集合效率不高 . 所以任何合理的算法都必须自下而上 .
所以我们假设我们在某个地方的层次结构中间，并且预先计算的层次结构表明集群A和B被合并以产生集群C.我们从下往上，所以我们已经计算了凸包的凸包 . 集群A和B中的点，所以我们只需要将它们组合起来就可以产生集群C的凸包 . 集群A的凸包实际上可以是单个点，一对或一个完整的多边形 . 对于集群B来说也是如此 . 因此，有几种情况应该如何合并以形成集群C的凸包，但我敢打赌，这是一个聪明的解决方案，可能会对待单体并以与多边形相同的方式进行配对 .
最明显的解决方案是使用来自集群A和B的凸包的组合点来计算凸包 . 但是我需要在100k点的层次结构上执行此操作，所以我想知道是否更有效结合A和B凸壳的方法
Edit 2:
/----5
1---/ / \
/ \ / B 8
2 A 3 C 6 /
\ / \ /
4--------7
好的，所以我试图用ASCII来说明我的意思 . A组凸壳为1-2-3-4，B的凸壳为5-6-7-8，C的凸壳为1-2-4-7-8-5 . 据推测，集群A和B在其船体内部包含额外的点，但这些明显不可能成为C船体的一部分，因此问题是一种算法确定在哪里“拼接”集群A和B的船体以形成C的船体，基于点的坐标 . 这是整个过程的归纳步骤 . （最终C将与群集D组合，依此类推，直到算法以最顶层的群集结束，其将具有作为其凸包的所有点的凸包） .
2 回答
有多种方法可以让您在添加新点时“更新”凸包 . 另外一些凸壳和Delauney三角测量的方法已经很好地从内到外工作，这应该很好地适应这一点 . 看看s-hull算法 .
但是，由于您正在讨论层次聚类，因此在涉及复杂性时，凸包可能是您最不关心的问题 .
分层聚类不能很好地扩展到大型数据集，因为算法本质上通常是
O(n^3)（使它们成为您在实践中仍然使用的最慢的聚类算法之一） . 因此，考虑到您的聚类更昂贵，另外计算一些凸包不应该产生那么大的差别 . 您可能只需要一个O(n log n)凸包算法的快速增量实现 .我知道至少有两个凸包合并算法 - 图森的第5部分（本文第5部分）和Preparata和Hong的bridging algorithm（参见论文第3部分） . 这两种算法在h = h1 h2中花费时间线性，其中h1和h2分别是第一和第二凸包中的船体顶点的数量 .