The Farthest Color Voronoi Diagram and Related Problems-猫眼课题宝

DOI：

发表时间：

2001

期刊：

影响因子：

通讯作者：

中科院分区：

其他

文献类型：

作者：

M. Abellanas;F. Hurtado;Christian Icking;R. Klein;E. Langetepe;Lihong Ma

假设有k种设施，e。G.学校、邮局、超市，在平面上用n个色点建模，每种类型都有自己的颜色。选择居住地点的一个基本目标是在社区中至少有一个代表每种设施类型的代表。在本文中，我们提供的算法，可能有助于实现这一目标的各种规格的术语“邻里”。关于多色点集的几个问题以前已经考虑过，例如双色最近点对，见E。G. Shamos [14，Section 5.7]，Agarwal et al. [1]，Graf and Hinrichs [8]，群Steiner树，参见Mitchell [11，Section 7.1]，或色最近邻搜索，参见Mount et al. [12]。让我们称一个集合为颜色跨越，如果它包含每种颜色的至少一个点。解决上述定位问题的一个自然方法是要求最小颜色跨度圆的中心。对于k = n，这相当于找到包围n个给定点的最小圆。这个问题可以通过最远点Voronoi图在时间O（n log n）内解决[3]，使用Megiddo的线性规划方法在时间O（n）内解决[10]，或者通过Welzl的minidisk算法在随机时间O（n）内解决[16]。一个特殊的情况是k = 2，那么解由双色最近对给出，见上文。对于2 < k < n，可以如下解决问题。让我们用下面的方式来概括Voronoi图。如果p表示颜色为c的位置，我们将平面上的所有点放在p的区域中，其中c是最远的颜色，p是最近的c色位置，i。例如，z属于

Suppose there are k types of facilities, e. g. schools, post offices, supermarkets, modeled by n colored points in the plane, each type by its own color. One basic goal in choosing a residence location is in having at least one representative of each facility type in the neighborhood. In this paper we provide algorithms that may help to achieve this goal for various specifications of the term “neighborhood”. Several problems on multicolored point sets have been previously considered, such as the bichromatic closest pair, see e. g. Preparata and Shamos [14, Section 5.7], Agarwal et al. [1], and Graf and Hinrichs [8], the group Steiner tree, see Mitchell [11, Section 7.1], or the chromatic nearest neighbor search, see Mount et al. [12]. Let us call a set color-spanning if it contains at least one point of each color. A natural approach to the above location problem is to ask for the center of the smallest color-spanning circle. For k = n this amounts to finding the smallest circle enclosing n given points. This problem can be solved in time O(n log n) by means of the farthest site Voronoi diagram [3], in time O(n) using Megiddo’s linear programming method [10], or in randomized time O(n) by Welzl’s minidisk algorithm [16]. A special case is k = 2, then the solution is given by the bichromatic closest pair, see above. For 2 < k < n one can solve the problem as follows. Let us generalize Voronoi diagrams in the following way. If p denotes a site of color c, we put all points of the plane in the region of p for which c is the farthest color, and p the nearest c-colored site, i. e., z belongs to the

The Farthest Color Voronoi Diagram and Related Problems

文献摘要

被引文献

相似文献