• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete optimization >Improved upper bounds for the Steiner ratio
【24h】

Improved upper bounds for the Steiner ratio

机译：改进了斯坦纳比的上限

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

摘要

Let P = {P_1, P_2, . . ., Pn} be a set of n points in Rd. For every 1 ≤ i ≤ n, define the star rooted at Pi as the union of all straight line segments joining Pi to all the other points in the set P. A Steiner star is the union of all straight line segments connecting some point in R~d to each point of P. The length of a star is defined as the total Euclidean length of its edges. We consider the problem of estimating the supremum of the ratio between the rooted star of minimal length and the Steiner star of minimal length, taken over all n point configurations in R~d. This is known as the Steiner ratio in Rd. It is conjectured that this ratio is 4/π when d = 2 and 4/3 when d = 3. Fekete and Meijer proved that for every d, this ratio is bounded from above by 2(1/2). Very recently, Dumitrescu, Tóth and Xu proved better upper bounds: 1.3631 for d = 2 and 1.3833 for d = 3. By a refinement of their approach we further improve these bounds to 1.3546 in the plane and 1.3801 in 3-space. These estimates yield improved upper bounds on the maximum ratio between the minimum star and the maximum matching in two and three dimensions.
机译：令P = {P_1，P_2，。 。 。，Pn}是Rd中的n个点的集合。对于每1≤i≤n，将以Pi为根的星定义为将Pi连接到集合P中所有其他点的所有直线段的并集。施泰纳星是将R中的某个点连接起来的所有直线段的并集。 〜d到P的每个点。恒星的长度定义为恒星边缘的欧几里得长度。我们考虑在R〜d的所有n点构型上估计最小长度的有根恒星与最小长度的Steiner恒星之比的最大值的问题。这称为Rd中的Steiner比率。可以猜想，当d = 2时，该比率为4 /π;当d = 3时，该比率为4/3。Fekete和Meijer证明，对于每个d，该比率都由2（1/2）限制。最近，Dumitrescu，Tóth和Xu证明了更好的上限：d = 2的1.3631和d = 3的1.3833。通过对它们的方法的改进，我们进一步将这些边界提高到平面上的1.3546和3空间上的1.3801。这些估计在二维和三维中最小恒星与最大匹配之间的最大比率的上限有了改进。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号