Back to Search Start Over

Packing plane spanning trees into a point set

Authors :
Ahmad Biniaz
Alfredo García
Source :
Zaguán: Repositorio Digital de la Universidad de Zaragoza, Universidad de Zaragoza, Scopus-Elsevier, Computational Geometry: Theory and applications, Zaguán. Repositorio Digital de la Universidad de Zaragoza, instname
Publication Year :
2020

Abstract

Let $P$ be a set of $n$ points in the plane in general position. We show that at least $\lfloor n/3\rfloor$ plane spanning trees can be packed into the complete geometric graph on $P$. This improves the previous best known lower bound $\Omega\left(\sqrt{n}\right)$. 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$.

Details

Database :
OpenAIRE
Journal :
Zaguán: Repositorio Digital de la Universidad de Zaragoza, Universidad de Zaragoza, Scopus-Elsevier, Computational Geometry: Theory and applications, Zaguán. Repositorio Digital de la Universidad de Zaragoza, instname
Accession number :
edsair.doi.dedup.....14710d7e4335e7b30f503c019b55a8ec