Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams
Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams
复制标题
DOI：
10.1145/800061.808751
复制
发表时间：
1983-12
期刊：
影响因子：
--
通讯作者：
DiagramsWelson Jacometti
中科院分区：
文献类型：
--
作者：
DiagramsWelson Jacometti
我们讨论以下问题：给定平面上的 n 个点（“站点”）和任意查询点 q，找到最接近 q 的站点。这个问题可以通过构造给定站点的 Voronoi 图，然后将查询点定位在其区域之一来解决。我们给出两种算法，一种在 O(n lg n) 时间内构造 Voronoi 图，另一种在 O(n) 时间内插入新站点。两者都基于 Voronoi 对偶、Delaunay 三角剖分的使用，并且足够简单，具有实用价值。这两种算法的简单性可以归因于问题的几何和拓扑方面的分离，以及使用两个简单但强大的原语、一个几何谓词和一个用于操作图的拓扑的运算符。拓扑由广义图的新数据结构表示，即图在二维流形中的嵌入。这种结构同时代表了一种嵌入、它的对偶和它的镜像。此外，只需两个运算符就足以构建和修改任意图表。
We discuss the following problem: given n points in the plane (the “sites”), and an arbitrary query point q, find the site that is closest to q. This problem can be solved by constructing the Voronoi diagram of the given sites, and then locating the query point in one of its regions. We give two algorithms, one that constructs the Voronoi diagram in O(n lg n) time, and another that inserts a new site in O(n) time. Both are based on the use of the Voronoi dual, the Delaunay triangulation, and are simple enough to be of practical value. The simplicity of both algorithms can be attributed to the separation of the geometrical and topological aspects of the problem, and to the use of two simple but powerful primitives, a geometric predicate and an operator for manipulating the topology of the diagram. The topology is represented by a new data structure for generalized diagrams, that is embeddings of graphs in two-dimensional manifolds. This structure represents simultaneously an embedding, its dual, and its mirror-image. Furthermore, just two operators are sufficient for building and modifying arbitrary diagrams.