Traversing a set of points with a minimum number of turns

DOI10.1007/s00454-008-9127-1zbMath1191.90087OpenAlexW1982128583MaRDI 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 geometryapproximation algorithmsminimum link spanning path

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

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

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item