• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International Conference on Computational Science and Its Applications(ICCSA 2006) pt.1; 20060508-11; Glasgow(GB) >Reduction of the Search Space in the Edge-Tracing Algorithm for the Voronoi Diagram of 3D Balls
【24h】

Reduction of the Search Space in the Edge-Tracing Algorithm for the Voronoi Diagram of 3D Balls

机译：3D球Voronoi图的边缘追踪算法中搜索空间的减少

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Voronoi diagram for 3D balls can be applicable to various fields in science and engineering. The edge-tracing algorithm constructs the Voronoi diagram in O(mn) time in the worst-case where m and n are the numbers of edges and balls, respectively. The computation time of the algorithm is dominated by finding the end vertex of a given edge since all edges in the Voronoi diagram should be traced essentially. In this paper, we define the feasible region which a ball to define the end vertex of a given edge should intersect. Then, balls which do not intersect the feasible region are filtered out before finding an end vertex since they cannot define an end vertex. Therefore, we improve the runtime-performance of the edge-tracing algorithm via the feasible region.
机译：3D球的Voronoi图可应用于科学和工程学的各个领域。在最坏的情况下，其中m和n分别是边缘和球的数量，边缘跟踪算法在O（mn）时间中构造Voronoi图。该算法的计算时间主要是通过找到给定边的末端顶点来控制的，这是因为Voronoi图中的所有边都应被追踪。在本文中，我们定义了一个用于定义给定边的末端顶点的球应该相交的可行区域。然后，在找到终点之前，将不与可行区域相交的球过滤掉，因为它们无法定义终点。因此，我们通过可行区域提高了边缘跟踪算法的运行时性能。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号