Minimum Dilation Stars

Details Minimum Dilation Stars Minimum Dilation Stars

2004-12-07

arxiv.org/abs/cs/0412025v3

Comp. Geom. Theory and Appl. 37(1):27-37, 2007

Computer Science

Computational Geometry

6 pages, 3 figures

Scientific paper

10.1016/j.comgeo.2006.05.007

The dilation of a Euclidean graph is defined as the ratio of distance in the graph divided by distance in R^d. In this paper we consider the problem of positioning the root of a star such that the dilation of the resulting star is minimal. We present a deterministic O(n log n)-time algorithm for evaluating the dilation of a given star; a randomized O(n log n) expected-time algorithm for finding an optimal center in R^d; and for the case d=2, a randomized O(n 2^(alpha(n)) log^2 n) expected-time algorithm for finding an optimal center among the input points.

Affiliated with

Also associated with

No associations

Rating

Minimum Dilation Stars 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 Minimum Dilation Stars, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Minimum Dilation Stars will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-76822