Minimum dilation stars

DOI10.1016/j.comgeo.2006.05.007zbMath1130.05023OpenAlexW3098722153MaRDI QIDQ871060

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

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

Related Items (8)

SINGLE-SOURCE DILATION-BOUNDED MINIMUM SPANNING TREES ⋮ Optimal Embedding into Star Metrics ⋮ DILATION-OPTIMAL EDGE DELETION IN POLYGONAL CYCLES ⋮ Testing Euclidean Spanners ⋮ COMPUTING GEOMETRIC MINIMUM-DILATION GRAPHS IS NP-HARD ⋮ Distribution-sensitive construction of the greedy spanner ⋮ Most finite point sets in the plane have dilation \(>1\) ⋮ Optimal Algorithms for Geometric Centers and Depth

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• An O(n log n) algorithm for the all-nearest-neighbors problem
• 2-point site Voronoi diagrams
• Efficient randomized algorithms for some geometric optimization problems
• Optimal Point Placement for Mesh Smoothing
• Approximating the Stretch Factor of Euclidean Graphs

This page was built for publication: Minimum dilation stars