Back to Search
Start Over
Packing plane spanning trees into a point set
- 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$.
- Subjects :
- Computational Geometry (cs.CG)
FOS: Computer and information sciences
Control and Optimization
Discrete Mathematics (cs.DM)
Dimension (graph theory)
0102 computer and information sciences
02 engineering and technology
Center (group theory)
01 natural sciences
Upper and lower bounds
Set (abstract data type)
Combinatorics
Spatial network
0202 electrical engineering, electronic engineering, information engineering
Mathematics
Spanning tree
Plane (geometry)
Computer Science Applications
Computational Mathematics
Computational Theory and Mathematics
010201 computation theory & mathematics
Computer Science - Computational Geometry
020201 artificial intelligence & image processing
Geometry and Topology
General position
Computer Science - Discrete Mathematics
Subjects
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