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.
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent