RANDOMIZED INCREMENTAL CONSTRUCTION OF ABSTRACT VORONOI DIAGRAMS
RANDOMIZED INCREMENTAL CONSTRUCTION OF ABSTRACT VORONOI DIAGRAMS
复制标题
DOI：
10.1016/0925-7721(93)90033-3
复制
发表时间：
1993-08-01
影响因子：
0.6
通讯作者：
MEISER, S
中科院分区：
文献类型：
--
作者：
KLEIN, R;MEHLHORN, K;MEISER, S
Voronoi图是R. Klein（1988）作为Voronoi图的公理化基础。本文基于克拉克森和肖尔（Shor）的随机增量构造技术（1989），给出了一个时间复杂度为O（nlog n）的抽象Voronoi图的随机构造算法.新算法与已有算法相比具有以下优点：它能处理比Klein（1989）和Mehlhorn，Meiser and O'Dunlaing（1991）提出的算法更广泛的抽象Voronoi图。它可以通过提供一个简单的基本操作，即构造五个点的Voronoi图，来适应于一种具体的Voronoi图。此外，所有的几何决策被限制在基本操作，并使用此操作，抽象的Voronoi图可以构造在一个纯粹的组合方式。
Voronoi diagrams were introduced by R. Klein (1988) as an axiomatic basis of Voronoi diagrams. We show how to construct abstract Voronoi diagrams in time O(n log n) by a randomized algorithm, which is based on Clarkson and Shor's randomized incremental construction technique (1989). The new algorithm has the following advantages over previous algorithms: It can handle a much wider class of abstract Voronoi diagrams than the algorithms presented in by Klein (1989) and, Mehlhorn, Meiser and O'Dunlaing (1991). It can be adapted to a concrete kind of Voronoi diagram by providing a single basic operation, namely the construction of a Voronoi diagram of five sites. Moreover, all geometric decisions are confined to the basic operation, and using this operation, abstract Voronoi diagrams can be constructed in a purely combinatorial manner.