CODEWITHSUNDEEP
algorithmgraph-algorithm
RagingBull
RagingBull

Reputation: 97

minimum number of lines connecting points

A set of points are given in a 2D space. The X co-ordinate of all points is unique.

These points have to be joined by lines whose slope is between -1 to +1. Now if two or more such lines join each other, it'll be counted as a single line if the overall line does not "turn around".

A line joining (0,0) (1,1) and (0,2) is "turned around" at (1,1).In such case line joining (0,0) & (1,1) and (1,1) & (0,2) are two separate lines and cannot be counted as one.

How can I determine global minimum number of such "overall" lines (or at-least approximate solution to it)? Is it some known algorithm ?

All the final number of "overall" lines need not touch or intersect each other.

For example if I have points {(1,1)(3,3)(5,5)} the answer is 1

If I have points {(1,1)(2,5)(3,3)(4,6)(5,1)} the answer is 2. One line joining (2,5)&(4,6) and other joining other points.

Thanks.

Edit: regarding "turn-around" .

The "overall line" consists of line segments each of whose slope is between -1 and +1. Each such "overall line" must be such that there does not exist a line x=const which cuts the "overall line" in more than one place.

Objective is to find minimum number of such "overall lines".

Upvotes: 3

Views: 1993

Answers (2)

dvvrd
dvvrd

Reputation: 1689

Let us consider given set of points as oriented graph where points are vertices and there is an edge between two points iff they can be connected with a segment with slope between -1 and 1 . To deal with no turns arounds each edge would be oriented upwards (this will restrict moving downwards and thus getting turn arrouns). It is rather obvious that one line with your conditions corresponds to a path in this graph.

So having such graph your problem transforms into a famous one. The task is to cover an oriented acyclic graph with the minimal amount of ways. You can find a lot of material through the internet on this topic, for example take a look on this:

Edit: Initially I wrongly perceived turn-arround condition, I was considering y=const line. Actually edges must be oriented to the right (x1 < x2) or left (x1 > x2).

Upvotes: 1

Volodymyr Balytskyy
Volodymyr Balytskyy

Reputation: 577

There are many possibilities that can be generated, and it is impossible to test all! First thing that comes to my mind is the Genetic algorithm.

Not sure how to implement, but I think it could be handy.

Upvotes: 0

Related Questions