Angle-restricted tours in the plane.

DOI10.1016/S0925-7721(96)00012-0MaRDI QIDQ2482907zbMATH OpenFDO

Authors Sándor P. Fekete, Gerhard J. Woeginger

Publication date 25 April 2008

Published in Computational Geometry (Search for Journal in Brave)

zbMATH Keywords

Hamiltonian cycletraveling salesman problemNP-completeComplexityConvexityGeometryangle-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)

Recommendations

• The Angular-Metric Traveling Salesman Problem
• Drawing Hamiltonian cycles with no large angles
• Going around in circles
• Geometric and LP-based heuristics for angular travelling salesman problems in the plane
• Drawing Hamiltonian cycles with no large angles

Cites work

• scientific article; zbMATH DE number 426008 (Why is no real title available?)
• scientific article; zbMATH DE number 4032498 (Why is no real title available?)
• scientific article; zbMATH DE number 4062601 (Why is no real title available?)
• scientific article; zbMATH DE number 4067744 (Why is no real title available?)
• scientific article; zbMATH DE number 16594 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1263210 (Why is no real title available?)
• A non-Hamiltonian, nondegenerate Delaunay triangulation
• Computing Simple Circuits from a Set of Line Segments is NP-Complete
• Hamilton Paths in Grid Graphs
• Minimum-time turn trajectories to fly-to points
• Nonholonomic multibody mobile robots: controllability and motion planning in the presence of obstacles
• On Some Distance Problems in Fixed Orientations
• On the convex layers of a planar set
• Optimal computation of finitely oriented convex hulls
• Shortest paths of bounded curvature in the plane
• The Angular-Metric Traveling Salesman Problem
• Traveling salesman cycles are not always subgraphs of Delaunay triangulations or of minimum weight triangulations

Cited in

(19)

• On Covering Points with Minimum Turns
• Going around in circles
• Drawing Hamiltonian cycles with no large angles
• Minimization and maximization versions of the quadratic travelling salesman problem
• Connected Rectilinear Graphs on Point Sets
• Acute tours in the plane
• Connectivity guarantees for wireless networks with directional antennas
• Bounded-angle minimum spanning trees
• Paths with no Small Angles
• Minimum scan cover with angular transition costs
• Acute tours in the plane
• Infinite paths with no small angles
• Approximation algorithms for lawn mowing and milling
• Edge sparsification for geometric tour problems
• Traversing a set of points with a minimum number of turns
• Peeling meshed potatoes
• Bounded-angle spanning tree: modeling networks with angular constraints
• On the approximability of covering points by lines and related problems
• SFCDecomp: multicriteria optimized tool path planning in 3D printing using space-filling curve based domain decomposition

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

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