pith. sign in

arxiv: 1803.02385 · v2 · pith:EGAIBPXPnew · submitted 2018-03-06 · 💻 cs.CG · cs.DM

Packing Plane Spanning Trees into a Point Set

classification 💻 cs.CG cs.DM
keywords planeboundgenerallowerpointspositionspanningtrees
0
0 comments X
read the original 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$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.