The traveling salesmanpProblem for lines in the plane

DOI10.1016/S0020-0190(01)00259-9zbMath1013.68265OpenAlexW2035400240MaRDI QIDQ1603540

Håkan Jonsson

Publication date: 14 July 2002

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0020-0190(01)00259-9

zbMATH Keywords

TSPshortest pathcomputational geometrywatchman problem

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items

The touring rays and related problems ⋮ An improved algorithm for computing a shortest watchman route for lines ⋮ Watchman routes for lines and line segments ⋮ THE TRAVELING SALESMAN PROBLEM FOR LINES AND RAYS IN THE PLANE ⋮ Polynomial-time algorithms for the touring rays and related problems

Cites Work

• Shortest watchman routes in simple polygons
• The Euclidean traveling salesman problem is NP-complete
• Shortest zookeeper's routes in simple polygons
• Finding the shortest watchman route in a simple polygon
• Computing the convex hull of line intersections
• Linear Programming in Linear Time When the Dimension Is Fixed
• An Optimal Algorithm for Finding the Kernel of a Polygon
• CORRIGENDUM TO "AN INCREMENTAL ALGORITHM FOR CONSTRUCTING SHORTEST WATCHMAN ROUTES"
• Unnamed Item
• Unnamed Item