Voronoi图的细分，它仍然是Voronoi图，是原始Voronoi图的超集

Question

考虑在一组站点S上构建的现有Voronoi图V。这张图有效地解决了“邮局服务于距离它们最近的地区”的问题。

考虑到邮局的问题是在need of decentralization without redefining the borders方面发展起来的。也就是说，除了以前的站点之外，还需要在当前站点的区域内有更多更小的站点，这些站点将具有相同的原始“外部”边界(但显然是一些新的“内部”边界)。

在更正式的定义方面，是否存在现有Voronoi图的细分，该细分反过来又是新的Voronoi图，使得它是原始站点集和结果边集的超集？

EDIT1:也许更正式:如果D是一组边，D={E}，是一组点的Voronoi图S: D=DV(S)，那么是否存在一组新的点S1，使得S'=S+S1，其中新的Voronoi图D'=DV(S')={E'}是原始图的“超集”：U{E} < U{E'}？

Answer 1

您可以使用点对位置算法来解决您的问题：http://en.m.wikipedia.org/wiki/Point_location。也许你可以查看TOPOJSON并合并相邻的单元格：http://bl.ocks.org/mbostock/9927735。