###
DOI:
Journal of Software:2001.12(3):440-447

基链分治算法与Voronoi区的面积计算定理研究
付庄,王树国,王剑英,蔡鹤皋
(哈尔滨工业大学 机器人研究所,黑龙江 哈尔滨 150001;中国科技大学 计算机科学与技术系,安徽 合肥 230027)
The Main-Chain Divide-and-Conquer Algorithm and the Area Computation Lemma for Voronoi Cell
FU Zhuang,WANG Shu-guo,WANG Jian-ying,CAI He-gao
()
Abstract
Chart / table
Reference
Similar Articles
Article :Browse 2580   Download 2482
Received:August 23, 1999    Revised:January 05, 2000
> 中文摘要: 基于一般曲线多边形Voronoi图的面向对象数据结构,提出了一种改进的Voronoi图生成算法——基链分治算法.该算法与经典的分治法相比更容易被实现.同时,在欧氏米制中,由于Voronoi区的边界包含抛物线或双曲线,因而Voronoi区的面积很难被计算.为此提出了Voronoi区的面积计算定理,并给出了定理证明和算例,从而为某些工程应用中的面积计算提供了一种方法.
Abstract:Based on the object-oriented data structure of Voronoi diagram for normal curvilinear polygon, an improved Divide-and-Conquer algorithm is presented in this paper for Voronoi diagram generation called Main-Chain Divide-and-Conquer algorithm. It is easier to implement compared with the classical one. Meanwhile, because the boundary of a Voronoi cell contains parabolic or hyperbolic curves in the Euclidean metric, it is difficult to compute the Voronoi cell area in practice. For this reason, an area computation lemma of the Voronoi cell is presented. The lemma proof and an example are also given. Thus, a way is provided for the area calculation in some engineering applications.
文章编号:     中图分类号:    文献标志码:
基金项目:国家自然科学基金资助项目(69685006) 国家自然科学基金资助项目(69685006)
Foundation items:
Reference text:

付庄,王树国,王剑英,蔡鹤皋.基链分治算法与Voronoi区的面积计算定理研究.软件学报,2001,12(3):440-447

FU Zhuang,WANG Shu-guo,WANG Jian-ying,CAI He-gao.The Main-Chain Divide-and-Conquer Algorithm and the Area Computation Lemma for Voronoi Cell.Journal of Software,2001,12(3):440-447