• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International Conference on Computational Science and Its Applications(ICCSA 2006) pt.1; 20060508-11; Glasgow(GB) >Visibility Maps of Segments and Triangles in 3D
【24h】

Visibility Maps of Segments and Triangles in 3D

机译：3D中线段和三角形的可见性图

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

摘要

Let T be a set of n disjoint triangles in three-dimensional space, let s be a line segment, and let t be a triangle, both disjoint from T. We consider the visibility map of s with respect to T, i.e., the portions of T that are visible from s. The visibility map of t is defined analogously. We look at two different notions of visibility: strong (complete) visibility, and weak (partial) visibility. The trivial Ω (n~2) lower bound for the combinatorial complexity of the strong visibility map of both s and t is almost tight: we prove an O(n~2 log n) upper bound for both structures. Furthermore, we prove that the weak visibility map of s has complexity Θ(n~5), and the weak visibility map of t has complexity Θ(n~7). If T is a polyhedral terrain, the complexity of the weak visibility map is Ω(n~4) and O(n~5), both for a segment and a triangle. We also present efficient algorithms to compute all discussed structures.
机译：设T为三维空间中n个不相交的三角形的集合，s为线段，t为三角形，均与T不相交。我们考虑s相对于T的可见性图，即部分从可见的T的T。 t的可见性图类似地定义。我们查看可见性的两种不同概念：强（完整）可见性和弱（部分）可见性。 s和t的强可见性图的组合复杂度的琐碎Ω（n〜2）下限几乎是紧密的：我们证明了两种结构的O（n〜2 log n）上限。此外，我们证明了s的弱可见性图具有复杂度Θ（n〜5），而t的弱可见性图具有复杂度Θ（n〜7）。如果T是多面体地形，则对于线段和三角形，弱可见性图的复杂度分别为Ω（n〜4）和O（n〜5）。我们还提出了有效的算法来计算所有讨论的结构。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号