On stars and Steiner stars. II

Details On stars and Steiner stars. II On stars and Steiner stars. II

2008-06-30

arxiv.org/abs/0806.4858v1

Computer Science

Computational Geometry

10 pages, 1 figure

Scientific paper

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/\pi = 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.

Affiliated with

Also associated with

No associations

Rating

On stars and Steiner stars. II does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On stars and Steiner stars. II, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On stars and Steiner stars. II will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-154851