Euclidean chains and their shortcuts

DOI10.1016/j.tcs.2012.03.021zbMath1417.05142MaRDI QIDQ391221

Boting Yang

Publication date: 10 January 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2012.03.021

zbMATH Keywords

diameter; computational geometry; Euclidean graph

Mathematics Subject Classification ID

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

05C85: Graph algorithms (graph-theoretic aspects)

68W25: Approximation algorithms

05C62: Graph representations (geometric and intersection representations, etc.)

Related Items

Unnamed Item, Unnamed Item, Fast Algorithms for Diameter-Optimally Augmenting Paths and Trees, Shortcut sets for plane Euclidean networks (extended abstract), Shortcuts for the circle, Computing optimal shortcuts for networks, Minimizing the continuous diameter when augmenting a geometric tree with a shortcut, Shortcut sets for the locus of plane Euclidean networks

Cites Work

• Unnamed Item
• Facility location and the geometric minimum-diameter spanning tree.
• Computing a \((1+\varepsilon)\)-approximate geometric minimum-diameter spanning tree
• Algorithms for Reporting and Counting Geometric Intersections
• Comments on “algorithms for reporting and counting geometric intersections”
• Minimum Diameter Spanning Trees and Related Problems