...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>IEEE transactions on visualization and computer graphics >On compatible star decompositions of simple polygons
【24h】

On compatible star decompositions of simple polygons

机译：关于简单多边形的相容星分解

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

摘要

The authors introduce the notion of compatible star decompositionsnof simple polygons. In general, given two polygons with a correspondencenbetween their vertices, two polygonal decompositions of the two polygonsnare said to be compatible if there exists a one-to-one mapping betweennthem such that the corresponding pieces are defined by correspondingnvertices. For compatible star decompositions, they also requirencorrespondence between star points of the star pieces. Compatible starndecompositions have applications in computer animation and shapenrepresentation and analysis. They present two algorithms fornconstructing compatible star decompositions of two simple polygons. Thenfirst algorithm is optimal in the number of pieces in the decomposition,nproviding that such a decomposition exists without adding Steinernvertices. The second algorithm constructs compatible star decompositionsnwith Steiner vertices, which are not minimal in the number of pieces butnare asymptotically worst-case optimal in this number and in the numbernof added Steiner vertices. They prove that some pairs of polygonsnrequire Ω(n2) pieces, and that the decompositionsncomputed by the second algorithm possess no more than O(n2)npieces. In addition to the contributions regarding compatible starndecompositions, the paper also corrects an error in the only previouslynpublished polynomial algorithm for constructing a minimal starndecomposition of a simple polygon, an error which might lead to annonminimal decomposition
机译：作者介绍了简单多边形的相容星分解的概念。通常，给定两个多边形之间具有对应关系的两个多边形，如果在两个整数之间存在一对一的映射关系，则两个多边形的两个多边形分解就认为是兼容的，从而使对应的片段由对应的顶点定义。对于兼容的恒星分解，它们还需要各个星体的星点之间的对应关系。兼容的starn分解在计算机动画以及shapen表示和分析中具有应用。他们提出了两种算法，用于构造两个简单多边形的兼容星形分解。然后，第一个算法在分解的片段数上是最佳的，前提是在不添加Steinernvertices的情况下存在这样的分解。第二种算法构造与Steiner顶点兼容的星形分解，其碎片数不是最小的，但在此数目和添加的Steiner顶点的数目n中，渐近渐近最优。他们证明了某些多边形对需要Ω（n2）个，通过第二种算法计算的分解n不超过O（n2）n个。除了在兼容的starn分解方面做出的贡献外，本文还纠正了以前发布的用于构造简单多边形的最小starn分解的多项式算法中的错误，该错误可能导致非最小分解

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号