Traversing a set of points with a minimum number of turns

DOI10.1007/s00454-008-9127-1zbMath1191.90087MaRDI QIDQ5901749

Prosenjit Bose, Pavel Valtr, Adrian Dumitrescu, Ferran Hurtado, Sergey Bereg

Publication date: 6 May 2009

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00454-008-9127-1

zbMATH Keywords

computational geometry; approximation algorithms; minimum link spanning path

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

68R10: Graph theory (including graph drawing) in computer science

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

On Covering Points with Minimum Turns, Distributed transformations of Hamiltonian shapes based on line moves, Improved parameterized algorithms for minimum link-length rectilinear spanning path problem, On the approximability of covering points by lines and related problems, Covering paths for planar point sets, Is It FPT to Cover Points with Tours on Minimum Number of Bends (Errata)?, FPT-ALGORITHMS FOR MINIMUM-BENDS TOURS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved lower bounds for the link length of rectilinear spanning paths in grids
• Minimum-link watchman tours
• Approximation algorithms for hitting objects with straight lines
• On the complexity of locating linear facilities in the plane
• Angle-restricted tours in the plane.
• Research Problems in Discrete Geometry
• COVERING A SET OF POINTS WITH A MINIMUM NUMBER OF TURNS
• Optimal Covering Tours with Turn Costs