Minimum Dilation Stars
| dc.creator | Eppstein, David | |
| dc.creator | Wortman, Kevin A. | |
| dc.date | 2004-12-07 | |
| dc.date | 2005-03-16 | |
| dc.date.accessioned | 2026-07-07T08:09:28Z | |
| dc.date.available | 2026-07-07T08:09:28Z | |
| dc.description | 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. | |
| dc.description | 6 pages, 3 figures | |
| dc.identifier | https://arxiv.org/abs/cs/0412025 | |
| dc.identifier | http://arxiv.org/abs/cs/0412025 | |
| dc.identifier | Comp. Geom. Theory and Appl. 37(1):27-37, 2007 | |
| dc.identifier | doi:10.1016/j.comgeo.2006.05.007 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/131553 | |
| dc.subject | Computational Geometry | |
| dc.subject | F.2.2; G.1.6 | |
| dc.title | Minimum Dilation Stars | |
| dc.type | text |