高级检索

周培德三角剖分不是最小权三角剖分

Zhou's Triangulation is not the Minimum Weight Triangulation

  • 摘要: 平面点集的(欧几里德)最小权三角剖分问题是计算几何和算法领域的一个长期悬而未决的公开问题.周培德于文献1中提出了一个新的平面点集三角剖分算法,并称该算法能够获得最小权三角剖分.文中通过给出反例,证明了该三角剖分不是最小权三角剖分,因此,最小权三角剖分问题仍有待于进一步研究.

     

    Abstract: The (Euclidean) minimum weight triangulation (MWT) of a planar point set is a long-standing open problem in the fields of computational geometry and algorithm design. Reference 1 presents a new triangulation algorithm, and claims that the algorithm can derive the MWT of a planar point set. By presenting counter-examples, this note proves that the triangulation is not the MWT. So, the problem of the MWT is still open.

     

/

返回文章
返回