Algorithm for plotting a group of lines efficiently

Question

I found the following algorithms question online, but can't find any efficient solution.
It was asked at a Google Interview. The question goes like this:

Given a sequence of lines to be plotted(each line has start and end point),
give an algorithm that helps you to plot the lines in the least amount of time.
It is not necessary that a line has to be plotted from start point only.

There was one approach which treated each line as a node in the graph.
And the edge between 2 nodes is the distance between ending node of first line
and starting node of second line. After this, if we calculate Minimum Spanning Tree,
it will give the optimal answer.

But I am not sure if this gives optimal solution all the time since it assumes that
line is plotted in one direction only.

Can anyone provide a hint about how this kind of problem can be solved?

Answer 1

Assuming Steve314's interpretation of a pen plotter in the comment is correct (as stated by OP), then the problem is a certain generalization of the travelling salesman problem, which is known to be NP-complete.

Proof: if all lines have length 0, i.e., reduce to points, then the problem is: each point has to be touched by the pen and the total distance travelled by the pen has to be minimised. This is exactly the Euclidean travelling salesman problem.

So you should be looking for an approximation algorithm (you cannot find the optimal solution efficiently). Some of the approximation algorithms for the Euclidean TSP are based on a miminum spanning tree and can be modified to solve your problem. It might also be possible to prove that the resulting algorithm will give you a path that is no longer than X (=two?) times the length of the optimal path.

EDIT: Here's a complete example adapted from the "simplest" metric TSP approximate solution algorithm in Wikipedia

1. Interpret the lines you want to draw as edges of an undirected (possibly disconnected) graph whose vertices are the specified endpoints
2. Complete to a minimal connected (spanning) graph that contains the wanted edges (using Prim's algorithm)
3. Convert to directed graph and find an Eulerian circuit

This should give you a solution (follow the path drawing edges as appropriate) that is at most twice as long as the optimal path. It can be further optimized in many ways, for example, by taking a shortcut and skipping a vertex in the path whenever the next edge does not need to be drawn (again or at all).

Answer 2

For a minimum spanning tree you will have to use Djikstra's algorithm which will pick a shortest path and compare it to all others connected to the same node recursively until all the nodes are processed. Actually I just reread you question and since your path doesn't have to start at a certain point you can use Prim's which has the same idea as above but starts at any node. Both use a priority queue which allows for a breadth first search.

Answer 3

That's a pretty nasty problem. It's a Shortest Hamiltonian Path, but you have a ton of edges (all edges (u, v) where u is the endpoint of some line and v is the startpoint of a different line), and the distances aren't symmetrical. The elegant ZDD-based way described in TAOCP 4A doesn't really apply I think - it would get swamped in all those edges.

Here's an idea (not optimal, but it seems like a reasonably good idea anyway), borrowing from TSP:

For every line s
    Schedule = empty sequence
    For every line n
        insert n in the optimal position in Schedule
    Apply 2-opt (see TSP) to the Schedule
Take the best Schedule.

Be super careful with that 2-opt. It is often described for the symmetric-distances case, which lets you optimize the "change in distance" calculation. You can't do there here.

Here's an other idea, borrowing heavily from TSP:

Solve a ton of ILP problems. For every node s and t (not equal):

• a boolean variable for every edge.
• weights are the lengths of those edges.
• every node n that isn't s or t gives a constraint of the form "sum of all edges adjacent to n == 2"
• for nodes s and t, that sum is instead equal to 1
• lazily add constraints that the entire thing must be a single connected component, that is:
  • detect connected components. If there is 1, this is a solution.
  • if there is more than 1, for every connected component:
  • if it contains s or t, add the constraint that the sum of all edges adjacent to that connected component must be 1.
  • otherwise, that sum must be 2.

Take the best of all those solutions. It could take a while.