Robust Computation of 3D Apollonius Diagrams
文献类型：会议论文
| 作者 | Wang, Peihui; Yuan, Na; Ma, Yuewen; Xin, Shiqing; He, Ying; Chen, Shuangmin; Xu, Jian; Wang, Wenping |
| 出版日期 | 2020 |
| 会议日期 | 2020 |
| 关键词 | VORONOI-DIAGRAM LAGUERRE GEOMETRY ALGORITHM SPHERES TESSELLATIONS CONSTRUCTION TOPOLOGY |
| 卷号 | 39 |
| 期号 | 7 |
| DOI | 10.1111/cgf.14125 |
| 英文摘要 | Apollonius diagrams, also known as additively weighted Voronoi diagrams, are an extension of Voronoi diagrams, where the weighted distance is defined by the Euclidean distance minus the weight. The bisectors of Apollonius diagrams have a hyperbolic form, which is fundamentally different from traditional Voronoi diagrams and power diagrams. Though robust solvers are available for computing 2D Apollonius diagrams, there is no practical approach for the 3D counterpart. In this paper, we systematically analyze the structural features of 3D Apollonius diagrams, and then develop a fast algorithm for robustly computing Apollonius diagrams in 3D. Our algorithm consists of vertex location, edge tracing and face extraction, among which the key step is to adaptively subdivide the initial large box into a set of sufficiently small boxes such that each box contains at most one Apollonius vertex. Finally, we use centroidal Voronoi tessellation (CVT) to discretize the curved bisectors with well-tessellated triangle meshes. We validate the effectiveness and robustness of our algorithm through extensive evaluation and experiments. We also demonstrate an application on computing centroidal Apollonius diagram. |
| 学科主题 | Computer Science |
| ISSN号 | 0167-7055 |
| 源URL | [http://ir.nimte.ac.cn/handle/174433/23280]  |
| 专题 | 会议专题 会议专题_会议论文 |
| 推荐引用方式 GB/T 7714 | Wang, Peihui,Yuan, Na,Ma, Yuewen,et al. Robust Computation of 3D Apollonius Diagrams[C]. 见:. 2020. |
入库方式： OAI收割
来源：宁波材料技术与工程研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。