Packing plane spanning trees into apoint set

被引：4
作者：
Biniaz, Ahmad [1 ]
Garcia, Alfredo [2 ]
机构：
[1] Univ Windsor, Windsor, ON, Canada
[2] Univ Zaragoza, Zaragoza, Spain
来源：
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS | 2020年 / 90卷
基金：
加拿大自然科学与工程研究理事会; 欧盟地平线“2020”;
关键词：
Plane trees; Edge-disjoint trees; Dimension of a point set;
D O I：
10.1016/j.comgeo.2020.101653
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
Let P be a set of n points in the plane in general position. We show that at least left perpendicular n/3 right perpendicular plane spanning trees can be packed into the complete geometric graph on P. This improves the previous best known lower bound Omega(root n). Towards our proof of this lower bound we show that the center of a set of points, in the d-dimensional space in general position, is of dimension either 0 or d. (C) 2020 Elsevier B.V. All rights reserved.
引用
收藏
页数：5
相关论文
共 13 条
  • [1] Packing plane spanning trees and paths in complete geometric graphs
    Aichholzer, Oswin
    Hackl, Thomas
    Korman, Matias
    van Kreveld, Marc
    Loffler, Maarten
    Pilz, Alexander
    Speckmann, Bettina
    Welzl, Emo
    [J]. INFORMATION PROCESSING LETTERS, 2017, 124 : 35 - 41
  • [2] CROSSING FAMILIES
    ARONOV, B
    ERDOS, P
    GODDARD, W
    KLEITMAN, DJ
    KLUGERMAN, M
    PACH, J
    SCHULMAN, LJ
    [J]. COMBINATORICA, 1994, 14 (02) : 127 - 134
  • [3] BOOK THICKNESS OF A GRAPH
    BERNHART, F
    KAINEN, PC
    [J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 1979, 27 (03) : 320 - 331
  • [4] Biniaz A, 2015, DISCRETE MATH THEOR, V17, P119
  • [5] Partitions of complete geometric graphs into plane trees
    Bose, P
    Hurtado, F
    Rivera-Campo, E
    Wood, DR
    [J]. COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2006, 34 (02): : 116 - 125
  • [6] Chan Timothy M, 2004, P 15 ANN S DISCR ALG, P430
  • [7] Edelsbrunner Herbert, 1987, EATCS Monographs in Theoretical Computer Science
  • [8] GRUNBAUM B, 1962, PAC J MATH, V12, P197
  • [9] COMPUTING A CENTERPOINT OF A FINITE PLANAR SET OF POINTS IN LINEAR-TIME
    JADHAV, S
    MUKHOPADHYAY, A
    [J]. DISCRETE & COMPUTATIONAL GEOMETRY, 1994, 12 (03) : 291 - 312
  • [10] Kundu Sukhamay, 1974, J. Combinatorial Theory Ser. B, V17, P199
12