What's the least number of straight lines do you need to connect a random set of dots?
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
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?
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.
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.
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.
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
This question is in the General Section. Responses must be helpful and on-topic.