Suppose I have a number of points in 2-dimensional space. I want to draw as many lines between the points as possible such that no two lines cross.

Hoping for a polynomial time algorithm, I constructed a maximum flow network. Each line between the points in my problem become a node in my maximum flow network. Arcs connect the source to each of the nodes in my flow network. Nodes representing links that do not cross with any other link gets connected straight to the sink with bounds [0,1]. Pairs of nodes representing pairs of lines that are mutually exclusive (crossing lines) are first connected to a dummy node, and then and arc to the sink with bounds [0,1].

At first glance, this seems like a brilliant polynomial-time solution. Unfortunately the maximum flow network doesn't work. Let me illustrate:

Node 1 is incompatible with node 2. Node 2 is incompatible with node 3:

   1 ---O
  /      \____ [0,1]
 /       /          \____T
S--2 ---O           /
 \       \____ [0,1]
  \      /
   3 ---O

Now, there's nothing stopping flow through node 2 to the sink via the upper dummy node, and flow through node 3 to the sink via the lower dummy node. This means the crossing links constraint is violated and solution is infeasible.

I can construct a very simple integer program:

$$\text{max:} \sum_{i = 1}^{n}X_i\\ \\ X_1 + X_2 <= 1\\ X_2 + X_3 <= 1\\ \text{(etc...)}\\ \\ X_i \in {0,1} \quad i = 1,2,\ldots,n $$

This works exactly as expected, and obviously give the optimal solution. It is very simple to construct this IP, but for very large number of points in the original problem, there is a huge number of potential lines and an enormous number of crossing lines. In short, I can only solve up to about 15 points in any reasonable time.

Can anyone see any obvious reduction that shows that this problem is inherently difficult (i.e. NP-Hard)? Or does there exist a P-Time algorithm that solves this optimally?

  • $\begingroup$ Straight lines? $\endgroup$ – fedja Feb 25 '13 at 4:27
  • $\begingroup$ Yes, straight lines. $\endgroup$ – AKrip Feb 25 '13 at 4:52

Assuming no three points collinear, you can draw enough lines to triangulate the figure, and no more.

If you have $n$ points, first draw the convex hull. Let's say this has $c$ points. The triangulation will have $e$ edges (these are your lines), with $2e=3f+c$, and $f-e+n=1$, where $f$ is the number of triangles. Eliminating $f$, we get $2e=3e-3n+3+c$, or $e=3n-3-c$.

I guess this doesn't answer the question, but it reduces it to finding the complexity of finding the convex hull, and finding a triangulation.

  • 1
    $\begingroup$ I think this totally answers the question, given the existence of ready-made computational geometry software for convex hulls and triangulations (e.g.). $\endgroup$ – Rahul Feb 25 '13 at 6:37
  • $\begingroup$ It looks like a lattice. +1 $\endgroup$ – mrs Feb 27 '13 at 16:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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