Minimum dilation stars

DOI10.1016/J.COMGEO.2006.05.007zbMATH Open1130.05023OpenAlexW3098722153MaRDI QIDQ871060FDOQ871060

Authors David Eppstein, Kevin Wortman 

Publication date 15 March 2007

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.comgeo.2006.05.007

zbMATH Keywords

dilationfacility locationquasiconvex programmingstretch factorEuclidean graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Distance in graphs (05C12) Discrete location and assignment (90B80)

Recommendations

• Minimum dilation stars
• Inhomogeneous minima of star bodies
• scientific article; zbMATH DE number 3049090
• Deep minima in stellar dynamos
• On diameters of uniformly rotating stars
• Minimal surfaces over stars
• Very low mass stars in binaries: a theoretical look
• Maximum star densities

Cites Work

• scientific article; zbMATH DE number 2086390 (Why is no real title available?)
• scientific article; zbMATH DE number 1424297 (Why is no real title available?)
• scientific article; zbMATH DE number 6469174 (Why is no real title available?)
• 2-point site Voronoi diagrams
• An O(n log n) algorithm for the all-nearest-neighbors problem
• Approximating the Stretch Factor of Euclidean Graphs
• Efficient randomized algorithms for some geometric optimization problems
• Optimal Point Placement for Mesh Smoothing

Cited In (14)

• On the dilation spectrum of paths, cycles, and trees
• SINGLE-SOURCE DILATION-BOUNDED MINIMUM SPANNING TREES
• Dilation-optimal edge deletion in polygonal cycles
• Minimum dilation stars
• Most finite point sets in the plane have dilation \(>1\)
• Approximate weighted farthest neighbors and minimum dilation stars
• Optimal algorithms for geometric centers and depth
• Eutactic star closest to a given star
• Testing Euclidean Spanners
• Computing geometric minimum-dilation graphs is NP-hard
• Optimal Embedding into Star Metrics
• Inhomogeneous minima of star bodies
• Approximate weighted farthest neighbors and minimum dilation stars
• Distribution-sensitive construction of the greedy spanner

This page was built for publication: Minimum dilation stars

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q871060)