Testing the necklace condition for shortest tours and optimal factors in the plane

DOI10.1016/0304-3975(89)90133-3zbMath0686.68035OpenAlexW2080333071WikidataQ54309769 ScholiaQ54309769MaRDI QIDQ1262765

Ermo Welzl, Günter Rote, Herbert Edelsbrunner

Publication date: 1989

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(89)90133-3

zbMATH Keywords

linear programmingcombinatorial geometrytransportation problemcomputational geometryintersection graphsdisksm-factorstraveling salesman tour

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05) Discrete mathematics in relation to computer science (68R99)

Related Items

Collision detection for deforming necklaces ⋮ A network approach for specially structured linear programs arising in 0-1 quadratic optimization ⋮ Relaxing the strong triadic closure problem for edge strength inference ⋮ The \(x\)-and-\(y\)-axes travelling salesman problem ⋮ Triangulations with Circular Arcs ⋮ Special cases of the traveling salesman problem ⋮ Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality

Cites Work

• A note on two problems in connexion with graphs
• Traveling salesman cycles are not always subgraphs of Voronoi duals
• On the use of optimal fractional matchings for solving the (integer) matching problem
• The Euclidean traveling salesman problem is NP-complete
• Algorithms for Reporting and Counting Geometric Intersections
• Towards a Genuinely Polynomial Algorithm for Linear Programming
• Optimal Point Location in a Monotone Subdivision
• Generalized Nested Dissection
• Deciding Linear Inequalities by Computing Loop Residues
• Integer and Fractional Matchings
• On k-Nearest Neighbor Voronoi Diagrams in the Plane
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• A CLASS OF COMBINATORIAL EXTREMA
• On some techniques useful for solution of transportation network problems
• A Problem on Circles
• Geometrical Extrema Suggested by a Lemma of Besicovitch
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item