Minimum dilation stars

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Minimum dilation stars

Full text

Pdf (158 KB)

Source

Annual Symposium on Computational Geometry archive
Proceedings of the twenty-first annual symposium on Computational geometry table of contents

Pisa, Italy

SESSION: Optimization problems table of contents

Pages: 321 - 326

Year of Publication: 2005

ISBN:1-58113-991-8

Authors

David Eppstein	University of California, Irvine
Kevin A. Wortman	University of California, Irvine

Sponsors

ACM: Association for Computing Machinery
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 14, Citation Count: 5

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1064092.1064142 What is a DOI?

ABSTRACT

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(n2^α(n) log²n) expected-time algorithm for finding an optimal center among the input points.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	P. K. Agarwal, R. Klein, C. Knauer, and M. Sharir. Computing the detour of polygonal curves. Technical Report B 02-03, Freie Universität Berlin, Fachbereich Mathematik und Informatik, 2002.
	2	Nina Amenta , Marshall Bern , David Eppstein, Optimal point placement for mesh smoothing, Journal of Algorithms, v.30 n.2, p.302-322, Feb. 1999 [doi>10.1006/jagm.1998.0984]
	3	Timothy M. Chan, An optimal randomized algorithm for maximum Tukey depth, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	4	Z. Drezner and H. W. Hamacher. Facility Location: Applications and Theory. Springer-Verlag, 2001.
	5	D. Eppstein. Spanning trees and spanners. In J.-R. Sack and J. Urrutia, editors, Handbook of Computational Geometry, chapter 9, pages 425--461. Elsevier, 2000.
	6	D. Eppstein. Quasiconvex programming. ACM Computing Research Repository, cs.CG/0412046, 2004.
	7	Stefan Langerman , Pat Morin , Michael A. Soss, Computing the Maximum Detour and Spanning Ratio of Planar Paths, Trees, and Cycles, Proceedings of the 19th Annual Symposium on Theoretical Aspects of Computer Science, p.250-261, March 14-16, 2002
	8	Giri Narasimhan , Michiel Smid, Approximating the Stretch Factor of Euclidean Graphs, SIAM Journal on Computing, v.30 n.3, p.978-989, 2000 [doi>10.1137/S0097539799361671]
	9	Micha Sharir , Pankaj K. Agarwal, Davenport-Schinzel sequences and their geometric applications, Cambridge University Press, New York, NY, 1996
	10	P. M. Vaidya, An O(n log n) algorithm for the all-nearest-neighbors problem, Discrete & Computational Geometry, v.4 n.2, p.101-115, Jan. 1989 [doi>10.1007/BF02187718]

CITED BY 5

	Mohammad Farshi , Panos Giannopoulos , Joachim Gudmundsson, Finding the best shortcut in a geometric network, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy
	Rolf Klein , Martin Kutz, The density of iterated crossing points and a gap result for triangulations of finite point sets, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA
	Mihai Bǎdoiu , Julia Chuzhoy , Piotr Indyk , Anastasios Sidiropou, Embedding ultrametrics into low-dimensional spaces, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA
	Boris Aronov , Mark de Berg , Otfried Cheong , Joachim Gudmundsson , Herman Haverkort , Michiel Smid , Antoine Vigneron, Sparse geometric graphs with small dilation, Computational Geometry: Theory and Applications, v.40 n.3, p.207-219, August, 2008
	Jean Cardinal , Sébastien Collette , Ferran Hurtado , Stefan Langerman , Belén Palop, Optimal location of transportation devices, Computational Geometry: Theory and Applications, v.41 n.3, p.219-229, November, 2008