This library includes C++ implementation of different algs for computing triangulations and TSP approximations.
There are in fact 3 libraries: geometry, triangulation computing, TSP approximations computing.
.png)
.png)
.png)
- Bowyer-Watson algorithm for computing Delaunay Triangulation.
- Cheapest Link Algorithm
- Kruskal's Algorithm
- 2-approximation algorithm.
- Cheapest Edges + DFS approximation.
- Delaunay Triangulation + Iterative Point Addition
| Name | Result | Time | Memory | Optimality |
|---|---|---|---|---|
| B-W | Triangulation | O(VlogV) | O(VlogV) | Optimal |
| CLA (pointset) | TSP tour | O(VlogV) | O(V^2) | 1.5 Optimal |
| Kruskal (pointset) | MST | O(VlogV) | O(V^2) | Optimal |
| 2-approximation (pointset) | TSP tour | O(VlogV) | O(V^2) | 2 Optimal |
| 2-approximation (triangulation) | TSP tour | O(VlogV) | O(VlogV) | ? |
| CE + DFS | TSP tour | O(VlogV) | O(VlogV) | ? |
| DT + IPA | TSP tour | O(VlogV) | O(VlogV) | ? |
The library works with text files.
input.txt (coordinates of points)
316.83673906150904 2202.34070733524 4377.40597216624 336.602082171235 3454.15819771172 2820.0530112481106 4688.099297634771 2935.89805580997 1010.6969517482901 3236.75098902635 ... main.cpp
#include "triangulation.h" #include "geometry.h" using namespace std; int main() { BowyerWatson bw; // reading points from a file with coordinates bw.fromCoords("input.txt"); // computing the triangulation bw.compute(); // writing to a file bw.toEdges("triang.txt"); } triang.txt (edges of triangulation; each number represents a point according to the input sequence)
197338 88708 88708 20109 88708 12785 88708 123994 88708 123616 ... main.cpp
#include "geometry.h" #include "tsp.h" #include <bits/stdc++.h> using namespace std; int main() { // read coordinates from file vector<Point> coords = toPoints("input.txt"); TSP tsp(toEdges("triang.txt", coords, 3)); // creating an edge subset for faster solution finding tsp.toSmallestEdges(); // computing the tour tsp.fromMST(); // writing to file tsp.toFile("output.txt"); return 0; } output.txt (resulting tour)
0 78934 111804 52086 18295 ... - Bowyer-Watson algorithm and improvements: http://www.gdmc.nl/publications/2002/Bowyer_Watson_algorithm.pdf
- O(nlogn) Euristic for Eucledian TSP: https://www.researchgate.net/publication/215753374_An_On_log_n_Heuristic_for_the_Euclidean_Traveling_Salesman_Problem
- Images are generated from a dataset from this Kaggle competition.