• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International Conference on Computational Science and Its Applications - ICCSA 2003 Pt.3 May 18-21, 2003 Montreal, Canada >Partitioning Polygons into Tree Monotone and Y-monotone Subpolygons
【24h】

Partitioning Polygons into Tree Monotone and Y-monotone Subpolygons

机译：将多边形划分为树单调和Y单调子多边形

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

摘要

A polygon Q is tree monotone if, for some highest or lowest point p on Q and for any point q interior to Q, there is a y-monotone curve from p to q whose interior is interior to Q. We show how to partition an n vertex polygon P in Θ(n) time into tree monotone subpolygons such that any y-monotone curve interior to P intersects at most two of the subpolygons. We then use this partition to further partition P into y-monotone subpolygons such that the number of subpolygons needed to cover any given y-monotone curve interior to P is O(log n). Our algorithm runs in Θ(n) time and space which is an improvement by an O(log n) factor in time and space over the best previous result.
机译：如果对于Q上某个最高点或最低点p以及对于Q内部的任何点q，存在从p到q的y单调曲线，且内部在Q内部，则多边形Q是树单调。 Θ（n）中的n个顶点多边形P成为树单调子多边形，使得P内部的任何y-单调曲线最多与两个子多边形相交。然后，我们使用此分区将P进一步划分为y-单调子多边形，从而覆盖P的任何给定y-单调曲线内部所需的子多边形数量为O（log n）。我们的算法在Θ（n）的时间和空间上运行，这在时间和空间上比以前的最佳结果提高了O（log n）因子。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号