%0 Journal Article
%T The Main-Chain Divide-and-Conquer Algorithm and the Area Computation Lemma for Voronoi Cell<br>基链分治算法与Voronoi区的面积计算定理研究
%A FU Zhuang
%A WANG Shu-guo
%A WANG Jian-ying
%A CAI He-gao
%A <br>付庄
%A 王树国
%A 王剑英
%A 蔡鹤皋
%J 软件学报
%D 2001
%I 
%X 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.
%K Voronoi cell
%K object-oriented data structure
%K candidate contour bisector
%K main-chain divide-and-conquer algorithm<br>Voronoi区
%K 面向对象的数据结构
%K 候选轮廓平分线
%K 基链分治法
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=7735F413D429542E610B3D6AC0D5EC59&aid=EE2569866CB1AD66&yid=14E7EF987E4155E6&vid=59906B3B2830C2C5&iid=38B194292C032A66&sid=78976D931AD1540F&eid=C66DE7562B0326E2&journal_id=1000-9825&journal_name=软件学报&referenced_num=6&reference_num=6