On stars and Steiner stars. II
| dc.creator | Dumitrescu, Adrian | |
| dc.creator | Tóth, Csaba D. | |
| dc.creator | Xu, Guangwu | |
| dc.date | 2008-06-30 | |
| dc.date.accessioned | 2026-07-07T09:47:26Z | |
| dc.date.available | 2026-07-07T09:47:26Z | |
| dc.description | A {\em Steiner star} for a set $P$ of $n$ points in $\RR^d$ connects an arbitrary center point to all points of $P$, while a {\em star} connects a point $p\in P$ to the remaining $n-1$ points of $P$. All connections are realized by straight line segments. Fekete and Meijer showed that the minimum star is at most $\sqrt{2}$ times longer than the minimum Steiner star for any finite point configuration in $\RR^d$. The maximum ratio between them, over all finite point configurations in $\RR^d$, is called the {\em star Steiner ratio} in $\RR^d$. It is conjectured that this ratio is $4/π= 1.2732...$ in the plane and $4/3=1.3333...$ in three dimensions. Here we give upper bounds of 1.3631 in the plane, and 1.3833 in 3-space, thereby substantially improving recent upper bounds of 1.3999, and $\sqrt{2}-10^{-4}$, respectively. Our results also imply improved bounds on the maximum ratios between the minimum star and the maximum matching in two and three dimensions. | |
| dc.description | 10 pages, 1 figure | |
| dc.identifier | https://arxiv.org/abs/0806.4858 | |
| dc.identifier | http://arxiv.org/abs/0806.4858 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/163879 | |
| dc.subject | Computational Geometry | |
| dc.title | On stars and Steiner stars. II | |
| dc.type | text |