VORONOI DIAGRAM IN THE LAGUERRE GEOMETRY AND ITS APPLICATIONS
VORONOI DIAGRAM IN THE LAGUERRE GEOMETRY AND ITS APPLICATIONS
复制标题
DOI：
10.1137/0214006
复制
发表时间：
1985-01-01
影响因子：
1.6
通讯作者：
MUROTA, K
中科院分区：
文献类型：
--
作者：
IMAI, H;IRI, M;MUROTA, K
本文将普通欧几里德几何中关于点的Voronoi图的概念推广到Laguerre几何中关于平面上的圆的Voronoi图的概念，其中圆与点的距离由切线的长度定义，并证明了这种推广情况下的Voronoi图的算法。拉盖尔几何中的Voronoi图可以有效地解决一些几何问题，如确定一点是否属于n圆的并集，求n圆的连通分量，求n圆的并集的轮廓等。在普通的Voronoi图的情况下，这里提出的算法，这些问题是最佳的常数因子内。本文还从不同的角度提出了问题和算法的一些推广。
We extend the concept of Voronoi diagram in the ordinary Euclidean geometry fornpoints to the one in the Laguerre geometry forncircles in the plane, where the distance between a circle and a point is defined by the length of the tangent line, and show that there is analgorithm for this extended case. The Voronoi diagram in the Laguerre geometry may be applied to solving effectively a number of geometrical problems such as those of determining whether or not a point belongs to the union ofncircles, of finding the connected components ofncircles, and of finding the contour of the union ofncircles. As in the case with ordinary Voronoi diagrams, the algorithms proposed here for those problems are optimal to within a constant factor. Some extensions of the problem and the algorithm from different viewpoints are also suggested.