General Question

Questionsaboutstuff's avatar

What's the least number of straight lines do you need to connect a random set of dots?

Asked by Questionsaboutstuff (265points) October 18th, 2014

What an optimal solution for working out what’s the least number of straight lines you need to go through every dot of a set of dots?

http://oi57.tinypic.com/uwo6s.jpg
Here’s an example.

Is there any easy way to work out the least number of lines for more complex examples?

Observing members: 0 Composing members: 0

6 Answers

gondwanalon's avatar

For your first question it seems logical that it depends of the number of points (dots) as well as the location of the points. As for how you get your answer, I doubt that there is an easy handy dandy formula to use. Why not just use your brain power?

flip86's avatar

.. 1 line.

CWOTUS's avatar

Since it takes two points to determine a line, the maximum number of lines should be n-1 for any n quantity of points. There is no way to determine a minimum number of lines to connect the points – given true randomness in the point distribution. (The number of lines may be forced lower if all of the points are coplanar, but that’s not a given in your problem. In any case, with true randomness and point area of 0, it’s not going to be a given that you can draw a line between two points that happens to “skim the edge” – nonexistent “edge of a point with >0 area” – of another “point” that’s not truly in line with the other two.) This isn’t like a map of the USA, where straight lines can be drawn to intersect with states that have positive area, for example, but where the line may only touch edges of some states and still count as an intersection.

In theoretical geometry, the points you’re talking about have no area, so in order for a line to cross more than two points, they have to be exactly colinear, and in a random distribution of points that may not always happen. On the other hand, it may happen sometimes, so your number of lines may not always be n-1, either.

So, though I cannot offer a geometric proof, I can tell you that there is no way to force a minimum number of lines through your points. On the other hand, some collections of points may offer more selections of colinear points, which would enable you to get to n-x lines, where x is a positive integer greater than 1, and less than n-1.

LostInParadise's avatar

My gut feeling is that there is no simple method of solving these types of problems. You have to pretty much try every combination, using your intuition to narrow the search.

Here is a classic variation on the type of problem you showed. Draw a square 3 by 3 array of dots. Without lifting your pencil or backtracing over a line, connect the dots using four lines.

dabbler's avatar

I think @flip86 is right, one line is the minimum possible.
If the dots randomly happen to be all lined up then one line does the trick.
As @CWOTUS describes the maximum, n-1, all those lines connect only two dots.
That could be reduced anywhere a third or more dots line up with the first two.

flutherother's avatar

The least number of lines required to connect n dots is n-1 if the dots have zero area. Joining two dots is easy and requires n-1 or one straight line. Then imagine a third dot being placed on the plane. What are the odds of a random dot being placed on this line of infinite thinness? I would say it is zero and so another line is required and this will be true of every subsequent random dot you can imagine.

Answer this question

Login

or

Join

to answer.

This question is in the General Section. Responses must be helpful and on-topic.

Your answer will be saved while you login or join.

Have a question? Ask Fluther!

What do you know more about?
or
Knowledge Networking @ Fluther