On the Stretch Factor of Polygonal Chains
From MaRDI portal
Publication:5001847
DOI10.1137/20M1335698OpenAlexW2970729539MaRDI QIDQ5001847
Ke Chen, Wolfgang Mulzer, Adrian Dumitrescu, 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
Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Paths and cycles (05C38) Connectivity (05C40)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On plane geometric spanners: a survey and open problems
- Constructing plane spanners of bounded degree and low weight
- On the dilation spectrum of paths, cycles, and trees
- Computing a minimum-dilation spanning tree is NP-hard
- On Steiner trees for bounded point sets
- Unsolved problems in geometry
- Beta-skeletons have unbounded dilation
- Minimum rectilinear Steiner tree of \(n\) points in the unit square
- Geometric applications of a randomized optimization technique
- Self-approaching paths in simple polygons
- Multilevel polynomial partitions and simplified range searching
- Computing the detour and spanning ratio of paths, trees, and cycles in 2D and 3D
- Local Versus Global Properties of Metric Spaces
- On self-approaching and increasing-chord drawings of 3-connected planar graphs
- Research Problems in Discrete Geometry
- The shortest path and the shortest road through n points
- Geometric Spanner Networks
- Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems
- Self-approaching curves
- Curves with increasing chords
- Approximating the Stretch Factor of Euclidean Graphs
- How Long Can a Euclidean Traveling Salesman Tour Be?
- Self-approaching Graphs
- Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications
- On Range Searching with Semialgebraic Sets. II
- Steiner Minimal Trees
- On the Shortest Path Through a Number of Points
- Generalized self-approaching curves
