Angle-restricted tours in the plane.

DOI10.1016/S0925-7721(96)00012-0zbMath1133.90385MaRDI QIDQ2482907

Sándor P. Fekete, Gerhard J. Woeginger

Publication date: 25 April 2008

Published in: Computational Geometry (Search for Journal in Brave)

zbMATH Keywords

GeometryComplexityHamiltonian cycletraveling salesman problemNP-completeConvexityangle-restrictions

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Eulerian and Hamiltonian graphs (05C45)

Related Items (16)

Minimization and maximization versions of the quadratic travelling salesman problem ⋮ SFCDecomp: Multicriteria Optimized Tool Path Planning in 3D Printing using Space-Filling Curve Based Domain Decomposition ⋮ Going around in circles ⋮ On the approximability of covering points by lines and related problems ⋮ Unnamed Item ⋮ Connectivity guarantees for wireless networks with directional antennas ⋮ Bounded-angle spanning tree: modeling networks with angular constraints ⋮ Traversing a set of points with a minimum number of turns ⋮ Peeling meshed potatoes ⋮ Connected Rectilinear Graphs on Point Sets ⋮ On Covering Points with Minimum Turns ⋮ Paths with no Small Angles ⋮ Bounded-angle minimum spanning trees ⋮ INFINITE PATHS WITH NO SMALL ANGLES ⋮ Minimum Scan Cover with Angular Transition Costs ⋮ Approximation algorithms for lawn mowing and milling

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Nonholonomic multibody mobile robots: controllability and motion planning in the presence of obstacles
• Traveling salesman cycles are not always subgraphs of Delaunay triangulations or of minimum weight triangulations
• A non-Hamiltonian, nondegenerate Delaunay triangulation
• Optimal computation of finitely oriented convex hulls
• Shortest paths of bounded curvature in the plane
• On Some Distance Problems in Fixed Orientations
• Minimum-time turn trajectories to fly-to points
• Computing Simple Circuits from a Set of Line Segments is NP-Complete
• On the convex layers of a planar set
• Hamilton Paths in Grid Graphs
• The Angular-Metric Traveling Salesman Problem

This page was built for publication: Angle-restricted tours in the plane.