6
$\begingroup$

Note: I originally posed this question to Mathematics, but it was recommended that I try here as well.

Context

For context, this problem is part of my attempt to determine the path of least inertia for a free and open-source laser scanner DAC API I am developing. The following problem arises during the vector image optimisation pass. I convert the 2D vector image into a graph of 2D positions and add blank edges (i.e. transparent lines) to represent the image as a strongly connected, undirected Eulerian graph from which I should be able to determine the optimal Eulerian circuit.

Problem

Given a strongly connected, undirected Eulerian graph (i.e. each vertex has an even degree), I'm trying to determine the Eulerian circuit that results in the minimum possible accumulative angular distance, where each vertex is a position in 2D space and each edge describes a straight line between the vertices.

My Solution Attempt

Edit: Since posting, I've since realised that my solution attempt is incorrect as the resulting traversal is not guaranteed to form an Eulerian circuit. Feel free to skip this section and the My Solution Attempt Issues section.

My attempt at solving this was to first simplify the problem by looking at each vertex individually. We know that each vertex must have an even degree, and thus for each vertex there must be an optimal set of incoming/outgoing edge pairs (where each edge is used once) that results in a minimum accumulative angular distance. By minimum accumulative angular distance, I'm referring to the sum of the difference between the result of the difference between the angle of each incoming/outgoing edge pair and a straight line. For example, given the following vertex A and its neighbours B, C, D and E:

A is adjacent to B, C, D, and E

an example of optimal pairs would be (DA, AB) and (EA, AC) as they are cumulatively the least sharp angles through which A may be traversed (and in turn would induce the least inertia), whereas the pairs (EA, AD) and (BA, AC) would be the least optimal as cumulatively they contain the sharpest angles to be traversed (resulting in the highest inertia).

Once the set of optimal pairs is determined for each vertex, I suspect the Eulerian Circuit can be created by starting at one of the vertices, picking a direction to begin and following the optimal pairs until the beginning is reached again.

My Solution Attempt Issues

Currently however I'm running into two issues.

  1. I don't know for sure whether or not my assumption holds true for all Euler graphs (where all nodes have an even degree).
  2. I'm unsure of the best approach for determining the set of optimal edge pairs for each vertex. I suspect it may be possible to represent each vertex and its edges as a sub-graph and treat the problem as finding the shortest path (where the "shorter" distances are the paths through the vertex that result in the straightest angles), but I'm struggling to come up with a sub-graph representation that would allow me to do this.

Related Research

In section 3.4 of Abderyim, Halabi, Fujimoto, and Chiba - Accurate and Efficient Drawing Method for Laser Projection the paper describes using Hierholzer’s algorithm for finding an optimal Eulerian circuit with the amendment that during traversal of each vertex you select the unvisited edge along the angle closest to a straight line. One issue that occurs to me with this approach is that it is not clear to me that this always results in the absolute optimal circuit, only one that is probably nearer to optimal than a naïve construction without this added amendment.

Questions

  1. Is there an existing solution to the original Problem stated above? If so, is there somewhere I might read further on this?
  2. If not, does my attempted solution sound like a reasonable approach? If so, do you have an idea of how I might represent the sub-graph for determining the set of edge pairs resulting in the minimum accumulative angular distance for each vertex? Approach determined to be invalid.
  3. If not, can you recommend an approach I might be able to take to make progress on solving the previously mentioned Problem?

Any advice appreciated!

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ Try this: start with any Eulerian circuit, and label the edges with numbers so that the circuit goes from edge 1 to edge 2 to edge 3, all the way back to edge 1. Now optimize at each vertex by reversing paths. For illustration, suppose vertex v has incident edges a, a+1 less than b, b+1 less than c, and c+1. If reversing the path from a+1 to b improves the angularity at v, do that (or reverse b+1 and c, or c+1 and a). By reversing one path at a time, you can improve angularity at a vertex without losing gains elsewhere. Gerhard "Start With A Conservative Choice" Paseman, 2019.04.16. $\endgroup$
    – Gerhard Paseman
    Apr 17, 2019 at 4:47
  • $\begingroup$ Thanks a lot for the tip @GerhardPaseman! I am going to have a go at using Hierholzer’s algorithm to first construct a circuit, then have a play by applying your tip to optimising the resultant circuit and report back. $\endgroup$
    – mindTree
    Apr 17, 2019 at 9:24
  • 1
    $\begingroup$ Related: Aggarwal, Alok, Don Coppersmith, Sanjeev Khanna, Rajeev Motwani, and Baruch Schieber. "The angular-metric traveling salesman problem." SIAM Journal on Computing 29, no. 3 (2000): 697-711. $\endgroup$
    – Joseph O'Rourke
    Apr 17, 2019 at 10:38
  • $\begingroup$ A link to the paper. $\endgroup$
    – Alex Ravsky
    May 4, 2019 at 21:11

1 Answer 1

Reset to default
0
$\begingroup$

This might be the opposite of an answer, as it modifies the problem quite a bit. However, you may find it useful anyway.

The first observation is that vertex placement on the plane Is important. If I were to take a graph and squash it (leave x coordinates alone, but shrink y by a factor of a thousand), the answer becomes different, and it is a question whether an optimal tour for the first graph maps to an optimal tour for the squashed graph. I suspect not, and it would be good to write down what transformations of the plane preserve optimality and which don't. It would also be good to know if you can fudge the input slightly to improve the chances of reaching your goal.

The next is that it is unclear why you need a full Euler tour. I can imagine why you need a partial Euler tour to visit all vertices, but I am not seeing why you would want a full edge tour. If you don't need it, here is a quick way to generate a partial Euler tour: pick a start vertex, and then do a random non-edge repeating tour until you return to the start vertex. The edges not hit by the random tour are a union of cycles, and you can repeat this routine with a new (or old) start vertex and stick to previously untoured edges. When you have two such (disjoint) tours with a common vertex, you can patch them together to make a larger tour. Repeat until you are bored or have a vertex cover or an edge cover. Of course, the patch may generate a suboptimal partial Euler tour, but you may be lucky and find a domain vertex where you can minimize this deviation.

Suppose you decide to generate random disjoint tours this way. You can try for optimal subtours and merge them. The point is that if the graph decomposes into K disjoint subtours, each of which is as optimal as you can make it given the disjointness condition, then you can bound the spoilage by (K-1)*pi . So it might behoove you to generate optimal subtours to start, and then pick the five most promising subtours and extend those with other partial subtours, and save patching them together until you have looked at all the common points of intersection.

Gerhard "Sometimes Not Answering Is Helpful" Paseman, 2019.04.17.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.