1

So this is my problem, I have n nodes (can be called points without positions), and I have a list of lines, were a line is defined by connecting 2 nodes (points).

My problem is to find the right position for each node (point) to minimize the amount of intersections between the lines.

I have no clue how to even start solving this problem. If someone can give me a way or explain some kind of an algorithm that can help be I will be glad, I am not seeking for Code.

For illustration:

If we have 4 nodes [1,2,3,4] and 4 lines {[1,2],[2,3],[3,4],[4,1]}

The minimum amount of intersections can be 0 if we order the points like this: 4 Points no intersections

But there is a way that we can have 1 intersection like this:

4 Points 1 intersection

My problem is finding the positions for the minimum amount of interactions when the inputs are much more complex.

Green Fire
  • 720
  • 1
  • 8
  • 21
  • I think we lack information about the problem, because if the points have no fixed positions, making all lines parallel seems an easy way to do that. – RaymoAisla Nov 17 '16 at 09:14
  • @RaymoAisla In the simplest case where you have 3 nodes and all of them are connected to each other there is no way to make all lines parallel. – Green Fire Nov 17 '16 at 09:29
  • Ok, i understand now, i didn't catch the fact that the lines are attached to the nodes before. – RaymoAisla Nov 17 '16 at 09:47
  • 2
    In this case, it is a problem that can be seen as a graph theory problem. Knowing the minimal number of intersections in a graph is a NP problem. In polynomial time, it is possible to determine is the graph is planar, and if it is, thanks to Fary's theorem, it is possible to have zero intersections and to draw the graph in plane with segments. But if the graph admit minimal non-planar graphs in its minor, problem is then NP-complete – RaymoAisla Nov 17 '16 at 11:06
  • 1
    @RaymoAisla's last comment is mostly good, except that finding the minimal number of intersections in a graph is an NP*-complete* problem, and I can't see how "G admits minimal non-planar graphs in its minor" is any simpler than just saying "G is not planar". – j_random_hacker Nov 17 '16 at 12:23
  • @RaymoAisla I know that this problem is a npc problem, I am still searching for an algorithm that can "almost solve the problem" and approximate the best solution (not saying it will give the optimal solution every time but it will give a "good" solution most of the times) – Green Fire Nov 17 '16 at 13:48
  • 1
    I don't have an answer but just brainstorming: if you can identify faces in your mesh (ie 1,2,3,4) you could see the intersection as a twisted face. Then you could use an elastic mesh model to minimize the energy of your mesh which may (or may not) converge towards your desired result. – atb Nov 17 '16 at 14:02
  • Intuitively, i'll go on a divide-and-conquer approach, by dividing the set of points E in two sets E1 and E2 such that the number of lines bounding E1 and E2 is minimal, compute the algorithm on these two sets, and then reunite the results by separating the plane in two parts, one for E1 and one for E2, with maybe geometrical transformation to allow the reunification lines to cross the less lines they could. I think that stretch the structure near the plane separation line could be a correct idea. However this is a very imperfect algorithm because of the links influence on each subset – RaymoAisla Nov 17 '16 at 14:05
  • duplicate of http://stackoverflow.com/questions/5028433/graph-auto-layout-algorithm ? – coproc Nov 17 '16 at 15:51
  • @coproc actually if you solve that question it May be an answer to this question, but I have no intend of drawing it as a graph there for I cant use the libraries proposed in the answers for that question, This is what differ the questions – Green Fire Nov 17 '16 at 16:00
  • @GreenFire ok, no duplicate. still: the software packages mentioned in the answers of that other question do a pretty good job in positioning the nodes s.t. edge intersections are avoided as much as possible. – coproc Nov 18 '16 at 08:53

0 Answers0