Packing plane spanning trees into a point set

Biniaz, Ahmad ; García, Alfredo (Universidad de Zaragoza)

Resumen: Let P be a set of n points in the plane in general position. We show that at least ¿n/3¿ plane spanning trees can be packed into the complete geometric graph on P. This improves the previous best known lower bound O(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.

Idioma: Inglés

DOI: 10.1016/j.comgeo.2020.101653

Año: 2020

Publicado en: Computational Geometry: Theory and Applications 90 (2020), 101653 [5 pp.]
ISSN: 0925-7721

Factor impacto JCR: 0.537 (2020)

Categ. JCR: MATHEMATICS, APPLIED rank: 255 / 265 = 0.962 (2020) - Q4 - T3
Categ. JCR: MATHEMATICS rank: 288 / 330 = 0.873 (2020) - Q4 - T3

Factor impacto SCIMAGO: 0.354 - Computational Mathematics (Q3) - Computational Theory and Mathematics (Q3) - Geometry and Topology (Q3) - Control and Optimization (Q3) - Computer Science Applications (Q3)

Financiación: info:eu-repo/grantAgreement/EC/H2020/734922/EU/Combinatorics of Networks and Computation/CONNECT
Financiación: info:eu-repo/grantAgreement/ES/MINECO/MTM2015-63791-R

Tipo y forma: Article (PostPrint)

Área (Departamento): Área Estadís. Investig. Opera. (Dpto. Métodos Estadísticos)