Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Statistical Geometry

  1. Jul 5, 2005 #1
    You have two tools:
    1. A straight edge
    2. The ability to judge any distance to within 20%, or any angle to within 20 degrees.

    What can you construct with these tools, with an unlimited? In particular, is there a method for constructing an approximate circle that tends towards perfect accuracy as the number of steps you use tends towards infinity?

    For an example of what you can do, here is how to construct an approximate parallel line to a given line m through a point P:
    First prepare a length x = 100 light years.
    1. draw a line n through P that seems about parallel to your angle judgment. This line is either parallel to m (statistically impossible) or it intersects m at point Q.
    2. Does PQ appear, to your 20% accurate length judgment, to be at least 21% greater than x? If not, return to step 1. Otherwise, let x = PQ, and either return to step 1 or decide you are finished and n is your nearly parallel line.

    Given enough time, this method will produce an asymptotically accurate parallel line. It will never be exactly accurate. The fact that it may take a huge number of steps to become accurate is not important. Also, please disregard the fact that by some statistical fluke it might take a vast number of steps yet still not be any more accurate than it was to begin with--under reasonable expectations of chance, its accuracy will increase.

    So, can you find a similar method for creating a circle? Feel free to share any interesting sub-algorithms you come across. One that I am working on is how to, given an angle, reflect it over one of its rays.
     
  2. jcsd
  3. Jul 6, 2005 #2
    How do you know this won't result in an infinite loop?
     
  4. Jul 7, 2005 #3
    Mathematically I'm not so hot; but could I...

    1 - Measure out a square as close as possible to exactl right angles.
    2 - Measure out another square at 45 degrees from the angles of that square; but on top of it.
    3 - Keep bisecting the angles of the squares with another square on top of that and so on until you get a fairly roundish circle.

    In fact, if you use the straight edge and make all the lines exactly that long, then you won't be off on that distance by 20% making it more accurate. As the number of steps approaches infinity it becomes more of a circle.

    In fact, the more squares you put, the greater accuracy you'll have because the angel gets smaller and smaller so that 20 degrees is smaller visually.

    http://img242.imageshack.us/img242/1171/makingcircles9em.png
     
  5. Jul 8, 2005 #4
    Jimmy, I said:
    And here is a more exact description of just what you can do.
    You may name a point in any region you want, or along any line or line segment you want, or at any intersection you want.
    Given two points A and B, you may draw line AB.
    Given an angle ABC, you may name a degree amount x so that the difference between the measure of ABC and x is less than or equal to 20 degrees.
    Given a line segment AB, you may name a distance in inches x so that the difference between AB and x is less than or equal to 0.2 times the true length of AB.

    Assume nothing about the randomness or non-randomness of the two guessing methods, unless it turns out you absolutely can't proceed unless you assume they are random. However, since I don't think you can proceed otherwise, assume that when you select points from a region or along a line or line segment, the selection is random.


    Rahmuss, you have not shown that the steps you are describing are possible. For example, is it even possible to bisect an angle using the tools I have described? Is it possible to create a right angle?
     
    Last edited: Jul 8, 2005
  6. Jul 8, 2005 #5

    NateTG

    User Avatar
    Science Advisor
    Homework Helper

    It appears to be possible to create an arbitrary angle using your current rules. (Consider the possibility, for example, of starting with a 180 angle, and stepping down in increments of 20 degrees.)

    That means, that the following is possible:

    Pick the number of steps you want to take minimum 19 or so . Call that number [itex]n[/itex].

    In 5 steps you can construct a 90 degree angle.
    In (at most) another 5 steps you can construct a [itex]\frac{540}{n-10}[/itex] degree angle.

    Now, construct [itex]\frac{n-10}{2}[/itex] lines that meet at a point so that the smallest angles are all [itex]\frac{540}{n-10}[/itex].

    Choose an arbitrary point along one of the legs, and construct a perpendicular to both adjacent legs. Then reflect this perpendicular across the clockwise adjacent leg. Proceed clockwise around all [itex]{n-10}[/itex] legs (this takes only [itex]\frac{n-10}{2}[/itex] steps, since the reflection is over every other leg.

    This constructs a regular [itex]\frac{n-10}{2}[/itex] gon.

    Clearly, you can use this construction to build a regular polygon with an arbitrary number of sides - so you can approach a circle.
     
    Last edited: Jul 8, 2005
  7. Jul 9, 2005 #6
    "Stepping down" is not one of the rules.

    It is not possible to certainly construct a given angle in any fixed number of steps. It is only possible to approach that construction in a large number of steps.


    You have not shown that the steps of your method are possible, so I cannot accept this as a solution. You need to show how to construct any given angle, how to construct a perpendicular to a given line through a given point, and how to perform a reflection.
     
  8. Jul 11, 2005 #7
    Well, the only way I know of to make the circle is by using a kind of "trick," that's not explicitly allowed in the rules (though, one might argue, it is a not unreasonable extrapolation of those rules). Without using that trick, the best I can come up with is an ellipse.

    Warm-up Question: How do you approximate an ellipse using these tools?
     
  9. Jul 11, 2005 #8

    NateTG

    User Avatar
    Science Advisor
    Homework Helper

    Seems pretty obvious that if I start with a 180 degree angle, then I can name x at 160, and so on.

    Do you mean:

    Given an angle ABC it is possible to construct another angle DEF so that the difference in the measures of ABC and DEF is less than 20 degrees?
     
  10. Jul 11, 2005 #9
    The rule is, "Given an angle ABC, you may name a degree amount x so that the difference between the measure of ABC and x is less than or equal to 20 degrees."

    You don't get to choose how much less than or equal to 20 degrees it is. The only thing you know when you name x is that the error of x as an approximation to the measure of ABC is less than or equal to 20 degrees.

    For example, let's say I have an angle ABC and I use the rule to name the degree amount "fifty degrees." Now I know that the measure of angle ABC lies somewhere between thirty and seventy degrees, inclusive.

    I suppose the rule is slightly oddly worded.
     
    Last edited: Jul 11, 2005
  11. Jul 11, 2005 #10

    NateTG

    User Avatar
    Science Advisor
    Homework Helper

    I don't think your rules are sufficiently clear.
     
  12. Jul 11, 2005 #11
    I'll try again:

    1. You may name a point in any region you want, or along any line or line segment you want, or at any intersection you want. If you name a point in a region or along a line or line segment, the point has equal probability of being in any arbitrary subset of of the region, line, or line segment. (Relying on this working for infinite regions is, by the way, the sort of "cheat")

    2. Given two points A and B, you may draw line (or line segment) AB.

    3. Given an angle ABC, you have the function angleguess(ABC) that returns an arbitrary degree measure x so that the difference between x and the measure of ABC is less than or equal to 20 degrees.

    4. Given a line segment AB, you have the function lengthguess(AB) that returns an arbitrary length x so that the difference between x and the length of AB is less than or equal to 0.2 times the true length of AB.


    All points and lines lie in the Euclidean plane.
     
    Last edited: Jul 11, 2005
  13. Jul 11, 2005 #12

    NateTG

    User Avatar
    Science Advisor
    Homework Helper

    So there is no way to transfer angles or lengths except for picking at random, and seeing whether you're close?
     
  14. Jul 11, 2005 #13
    Yes; an inefficient method, but you have unlimited (though finite) steps to make your approximate circle in.

    I got to thinking about this when I was drawing somewhat inaccurate circles by hand and thinking, I can draw a straight line pretty well, and I can approximately guess distances and angles, so if you idealize those procedures as I did here, is there any algorithm to get as close to a circle as you like?

    I figured out the answer a little while ago: yes, there is, and without using the "cheat." Hint in white: The key to the method I found is finding a way to use the approximate distance guessing to get nearly exact distance guessing.
     
    Last edited: Jul 11, 2005
  15. Jul 11, 2005 #14

    NateTG

    User Avatar
    Science Advisor
    Homework Helper

    It's got to be pretty tricky unless you make assumptions about the distribution - otherwise the potential for malicious randomness will almost certainly make it impossible.
     
  16. Jul 12, 2005 #15
    Hey, I am able to construct an ellipse.

    Using BicycleTree's algorithm for parallel lines we can construct a parallelogram:
    Draw a straight line m.
    Take two points A and B on the line some distance apart.
    Draw a line n through B at any angle to m.
    Take a point C on n.
    Draw a line parallel to m through C.
    Draw a line parallel to n through A.
    Suppose the above two lines intersect in D. Then ABCD is a parallelogram.

    Since opposite sides of a parallelogram are congruent, the length AB is transferred to CD. Drawing another parallelogram, say BDCE, the length AB is further transferred to BE on the same line m. In this way we can get any no. of congruent segments on a given line. Also drawing parallel lines we can use n congruent segments on a line to divide a line segment into n equal parts.

    So we have developed two more tools: we can draw parallelograms and we can divide a given line segment in any no of equal parts.

    Therefore an ellipse can be easily constructed using the parallelogram method.
     
  17. Jul 17, 2005 #16
    Congratulations, Mustafa.

    Actually, I was in error about my original scheme for measuring lengths exactly. The method I had in mind was first squaring a given length, then squaring the result, and so on to a power of 2^n (n integer), and then measuring the final length and using that measurement to find the original length to much greater accuracy. But the method was flawed because it required an original estimation of a short length to perform the first squaring procedure, and the error in that estimation becomes amplified with every squaring so it nullifies the benefit from the power operation. Trying to use some exact technique like letting the small estimated length be 1/10 of the length to be squared does not result in an actual squaring.

    I was typing a further reply detailing a mistake I had made in my original solution, the "cheating" method for creating a nearly exact circle, and a correct solution for creating a nearly exact circle, but then I realized that the "randomness" guarantee of rule 1 is impossible. Corrected version of rule 1 (changes underlined):

    1. You may name a point in any region you want, or along any named line or line segment you want, or at any intersection you want. If you name a point in a region or along a line, ray or line segment, the point has equal probability of being in any two arbitrary subsets of equal area or length of the region, line, ray, or line segment. If the region, ray, or line has infinite area or length and other points have already been named, then the new named point is named only finitely far away from other named points (I don't think I really need to state this, except to be clear)

    Now, hopefully, you can do the problem. The "cheating" method makes extensive use of this rule with infinite regions, and can reasonably be argued not to work, but there is at least one method that doesn't stretch the rules.


    There are no guarantees on the randomness or nonrandomness of the two estimation functions, though that wasn't what was wrong with my earlier idea.
     
  18. Jul 24, 2005 #17
    Well, what I had in mind for the solution there was also flawed, and I have not been able to come up with one that is not flawed. I think that it is not possible for an intuitive but incomplete reason: if you imagine that you have constructed a circle, stretch the entire plane by a factor of 15% in one direction, and any length measurement from the original plane could also be chosen to apply to the stretched plane, due to the measurement error. I believe that the angle measurement provision does not change the problem since angles can also be measured by measuring the length of sides of a triangle. Not that thinking about it wasn't interesting.

    My original idea involved producing a distance proportional to the square of a given distance, and then squaring that derived distance, and so on to produce a distance proportional to the original distance taken to a power of 2^n. Then measure that final distance to within 20%, and you will know the original distance far more accurately. This doesn't work because taking the square of the original distance in the method I could think of necessarily involves introducing a small line segment of "known" length parallel to the distance to be squared. The device of taking the small line segment to be 1/10 of the distance to be squared do not work because they do not result in squaring the length. The inaccuracy in the small "known" line segment becomes amplified with successive squarings so that no advantage results.

    The method I had in mind later on had to do with measuring densities of randomly plotted points within a triangle to find equivalent lengths. There's no need to go into exactly what the idea was, but the problem was similar--no way around having a small initial segment of known length.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Statistical Geometry
  1. A Geometry challenge (Replies: 2)

  2. Geometry problem (Replies: 10)

  3. Great statistics (Replies: 3)

  4. Unknown geometry? (Replies: 6)

Loading...