In Euclidean graph where each vertex is a point on the $2D$ plane, so the weight of each edge is the Euclidean distance between the vertices. I want to find self-avoiding-filling-polygon from my graph vertices. Or in other words, a path that visit each vertex exactly once and returning to the starting position without intersecting itself on the way.
I wrote this pseudo code that is doing the job in $O(N^2)$, I want to know if using system of linear equations to represent my graph will provide me a better way finding my polygon?
Note that regions you specify using linear inequalities are necessarily convex: so unless you are OK with visiting only the convex hull of (some subset of) the vertices, I don't think that is the way to go for this problem.
How about an edge-flipping approach? Draw any random path that visits all of the vertices (but perhaps self-intersects). Then detect if two edges intersect, and if so, swap their endpoints so that they no longer do (i.e., turn
Xinto||or=, whichever doesn't disconnect the graph.) Repeat until no edges intersect. I'm not sure off-hand if this approach always terminates, but maybe you can think along these lines.