On the stretch factor of polygonal chains

DOI10.1137/20M1335698MaRDI QIDQ5001847zbMATH OpenOpenAlexFDO

Authors Ke Chen, Adrian Dumitrescu, Wolfgang Mulzer, Csaba D. Tóth

Publication date 23 July 2021

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1906.10217

zbMATH Keywords

Koch curvepolygonal chainrecursive constructionvertex dilation

Mathematics Subject Classification ID

Paths and cycles (05C38) Connectivity (05C40) Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• A fast algorithm for approximating the detour of a polygonal chain.
• Efficient algorithms for approximating polygonal chains
• Locked and unlocked polygonal chains in three dimensions
• Reconfiguring closed polygonal chains in Euclidean \(d\)-space
• scientific article; zbMATH DE number 1875426

Cites work

• Approximating the Stretch Factor of Euclidean Graphs
• Beta-skeletons have unbounded dilation
• Computing a minimum-dilation spanning tree is NP-hard
• Computing the detour and spanning ratio of paths, trees, and cycles in 2D and 3D
• Constructing plane spanners of bounded degree and low weight
• Curves with increasing chords
• Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications
• Generalized self-approaching curves
• Geometric applications of a randomized optimization technique
• Geometric Spanner Networks
• How Long Can a Euclidean Traveling Salesman Tour Be?
• scientific article; zbMATH DE number 4155925 (Why is no real title available?)
• scientific article; zbMATH DE number 1749054 (Why is no real title available?)
• scientific article; zbMATH DE number 1424297 (Why is no real title available?)
• scientific article; zbMATH DE number 3386495 (Why is no real title available?)
• Linear-Time Algorithms for Linear Programming in R^3 and Related Problems
• Local versus global properties of metric spaces
• Minimum rectilinear Steiner tree of n points in the unit square
• Multilevel polynomial partitions and simplified range searching
• On plane geometric spanners: a survey and open problems
• On range searching with semialgebraic sets. II.
• On self-approaching and increasing-chord drawings of 3-connected planar graphs
• On Steiner trees for bounded point sets
• On the dilation spectrum of paths, cycles, and trees
• On the Shortest Path Through a Number of Points
• Research Problems in Discrete Geometry
• Self-approaching curves
• Self-approaching graphs
• Self-approaching paths in simple polygons
• Steiner Minimal Trees
• The shortest path and the shortest road through n points
• Unsolved problems in geometry

Cited in

(2)

• Properties of topological networks of flexible polygonal chains
• On the stretch factor of polygonal chains

This page was built for publication: On the stretch factor of polygonal chains

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