Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given a curve, I have to prove or disprove that it is a straight line. How do I do this?

I tried by finding and comparing slopes but I can see that this will not be a very computationally efficient way (as I am implementing this on a PC) ; I will have to find slopes at different points and see if the slope is changing or not. If the slop has not changed, I will chose next point and find the slope at this new point. And yes there are infinite points on the line, so how many slopes I am going to measure ?

Another trick I adopted is Divide and Conquer; I divided the entire curve into N segments, and processed each segment using multi-threading, looking for slope changes at several different places simultaneously. This also seem not very efficient, given the kind of curves I am processing. Even I have to look for inter-segment slope changes in addition to intra-segment slope changes

Any other computationally efficient way? Some of the curves that I am dealing with are as follows: enter image description here

(As can be seen only one or two small curves look like straight lines. )

I want to understand an efficient algorithm from two different point of views:

1- When the equations for each curve is given; Algebra point of view

2- No equations are given, only images are given; may be I can call this Geometry point of view

share|improve this question
    
A quick way would be to select three points from the curve randomly. Check if the three are colinear. If not, you have eliminated the curve, if they are colinear, pick a new point and perform a colinearity test again. This way, you can eliminate a lot of curves quickly. What it does not do however is confirm that a curve is really a straight line. –  Raskolnikov Jan 31 '13 at 10:27
    
When the equation is given, show that it is linear suffices, right? –  awllower Jan 31 '13 at 10:49
    
One definition of a "straight line" is that it is the shortest possible line joining the endpoints. So rather then looking at slopes, it might be worth computing the length of the line you are given, and then comparing it with the length of the straight line joining the two endpoints. The larger the difference then the less "straight" your line is. –  Shard Jan 31 '13 at 20:12
    
@Shard Shard this is indeed a very useful observation! (Actually I can get the length information in my problem- at least approximately) –  gpuguy Feb 1 '13 at 6:43

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.