1

This data

t  value
1   1
2   0
3   4
4   2
5   2
6   5
7   3
8   4
9   6
10  4
11  6
12  7
13  5
14  8
15  8
16  6
17  10
18  9
19  7
20  12

Represents actually 3 straight lines (1,2,3,....), (0,2,4,...), (4,5,6,...) each having a value every 3 ticks. What algorithm can take this data and find these lines? In other words, given a stream of values at various time stamps (maybe not uniformly spaced as in the example above), find the maximum number of non overlapping straight lines that approximately pass through the values.

IttayD
  • 133
  • 4
  • Isn't this question a variant of Euler's number? http://mathforum.org/isaac/problems/bridges1.html In other words, Euler developed the "first" network analysis by answering a question about the seven bridges in his hometown of Koenigsberg, "The people wondered whether or not one could walk around the city in a way that would involve crossing each bridge exactly once." In your case, the stream of values constitutes a network and you want to know how many unique sequences of values can be derived from it? These patterns could include linear sequences of 1, exponents of 2+ or fibonacci numbers? – Mike Hunter Nov 12 '15 at 12:26
  • When I plot your data, it only looks like there are 2 non-overlapping straight lines implied. – Matthew Plourde Nov 12 '15 at 14:32
  • Do you know the number of groups, or can it be found by visual inspection? This significantly alters the complexity of the problem. Also, the lines intersect at 0. Is this going to be a problem? – RegressForward Nov 12 '15 at 14:37
  • 2
    The "the maximum number of non overlapping straight lines" that pass through *any* finite collection of points is equal to the number of points--and there are infinitely many such solutions. (If you choose a direction uniformly at random and look at the lines emanating from each point in that direction, then with probability 1 those lines are all distinct and non-overlapping.) Perhaps you asked exactly the opposite of what you meant? Don't you want to find the *minimum* number of *distinct* (and likely overlapping) lines that cover the points? See http://stats.stackexchange.com/questions/33078 – whuber Nov 12 '15 at 14:44

0 Answers0