Kuro5hin.org: technology and culture, from the trenches
create account | help/FAQ | contact | links | search | IRC | site news
[ Everything | Diaries | Technology | Science | Culture | Politics | Media | News | Internet | Op-Ed | Fiction | Meta | MLP ]
We need your support: buy an ad | premium membership

[P]
A Gentle Introduction to Projective Geometry, Part 1.

By i in Science
Tue May 27, 2003 at 04:29:56 PM EST
Tags: Science (all tags)
Science

It is assumed that the reader is somewhat familiar with Euclidean geometry and basic matrix and vector algebra.

In this installment we will introduce the basic concepts of projective geometry. In the next part will take a brief look at projective transforms.


Euclidean geometry is a very good mathematical framework for describing various properties of shapes and motions. Except it's got an exceptional case at its very foundation -- parallel lines, and when we move up to 3D, planes. Parallel lines don't intersect, while any other pair of (different) lines intersect at exactly one point. Of course, being lazy as we are, we hate handling exceptional cases.

Well, it turns out that we can get rid of parallelism and still obtain quite usable geometry.

We won't be giving axiomatic definitions here. Instead we will state some of the properties of projective planes and projective spaces. Some of the properties are axioms and some are theorems. It is not important to us which is which.

Plane properties

  1. For any two distinct points, there is exactly one line that passes through both of them.
  2. For any two distinct lines, there is exactly one point that is common to both of them.
  3. There exist at least three points, not all lying on the same line.
  4. There exist at least three lines, not all passing through the same point.
  5. Every line contains at least three points.
  6. Every point lies on at least three lines.
Any object that satisfies these properties is called a projective plane.

If you're bright enough (of course you are), you have already noticed some kind of symmetry here. Odd-numbered properties can be obtained from even-numbered properties if we replace the word "point" by the word "line" and vice versa, and also replace phrases like "point lies on line" with "line passes through point" and vice versa. This is a very handy property of projective planes. It's official name is duality. Duality means that for every theorem we can automatically obtain another theorem, called its dual, by exchanging points with lines and vice versa.

In order to simplify things even further, instead of saying "point lies on line" or "line passes through point", we will say "point and line coincide ". This phrase is symmetric w.r.t. points and lines, which makes turning a proposition into its dual a completely automatic process.

Why is this useful? It turns out that if we arbitrarily choose a single line (together with all the points that coincide with it) and call it "line at infinity" or "ideal line" and just throw it away, the rest of the projective plane turns into our familiar Euclidean plane. That is, any two lines that were intersecting at ideal line no longer intersect and become "parallel lines", and all axioms of Euclidean geometry hold.

Conversely, if we take an Euclidean plane and complement it with an object called "ideal line", and postulate that any family of parallel lines have their "intersection point" lying at the ideal line, we will get a projective plane. By the way, points on ideal line are called ideal points.

We will go by this route when deriving a coordinate representation of projective geometry. But first, a few words on projective space.

Space properties

  1. Three points not all coincident with the same line are coincident with a unique plane.
  2. Three planes not all coincident with the same line are coincident with a unique point.
  3. For a line and a plane not coincident with it, there's exactly one point that is coincident with both.
  4. For a line and a point not coincident with it, there's exactly one plane that is coincident with both.
  5. Two distinct planes are coincident with exactly one common line.
  6. Two distinct points are coincident with exactly one common line.
There are more properties akin to properties 5 and 6 of projective plane, but we'll not discuss them here.

Again, we can see that there's a symmetry between odd-numbered and even-numbered properties (we've made it apparent by talking about coincidence right from the start). The difference is that now points are dual with planes, not lines. You can guess what will happen if we move forward to higher dimensions.

In addition, there's a property of projective spaces which says that every plane is a projective plane, in the sense already defined.

Needless to say, a trick similar to that of ideal line will move us back and forth between projective space and Euclidian space, only now we introduce an ideal plane instead of ideal line.

Homogenous co-ordinates.

A point on plane is represented by a pair of co-ordinates (x, y). Let's add a third co-ordinate at the end. We postulate that

  • (x, y, 1) represents the same point as the pair (x, y);
  • (X, Y, Z) represents the same point as (αX, αY; αZ) for any scalar α
  • (0, 0, 0) is not allowed.
To arrive from homogenous co-ordinates back to Euclidean, we simply divide by the third co-ordinate: (x, y) = (X/Z, Y/Z). It is immediately clear that there are more "points" than the Euclidean plane has : (X, Y, 0) maps to nothing because we can't divide by zero! Not-so-amazingly, it turns out that such triples precisely correspond to ideal points of projective plane.

What does this buy us? Let's see how we would represent lines. We start with the familliar equation for a line in Euclidean plane:

ax + by + c = 0

Noting that this equation is not affected by scale, we arrive to

aX + bY + cZ = 0, or

uTp = pTu = 0

where u = [a, b, c]T is the line and p = [X, Y, Z]T is a point on the line. Surprise: points and lines have the same representation in homogenous co-ordinates! No wonder, because they are dual concepts. It is easy to derive a formula for intersection point of two lines: p = u1 u2, and for a line that passes through two points: u = p1 p2. Again, thanks to duality, the two formulas are identical. More fun with formulas: three points lie on the same line if det[p1 p2 p3] = 0. How would you determine whether three lines all go through the same point?

In three dimensions we will of course have 4-tuples for points and planes.

Now what?

You might wonder, what parallels (pardon the pun) in the real world these highly abstract concepts may have? Yet many people can see an ideal line with their naked eyes, without even realising it. You can too, if you live on a vast plain or near sea shore. Yes, it's the horizon.

Of course, railroad tracks or edges of a highway don't really intersect, but we perceive them intersecting at the horizon. That's because the world around us undergoes projective transform in our eyes. Photographs of tall buildings often exhibit the same phenomenon. If you take one and continue images of a bunch of lines that ought to be parallel in the real life, you will see that they all intersect at the same point. Another bunch of parallel lines will intersect at another point. All these points lie on a straight line -- the horizon. The horizon is the image of the ideal line in our eyes or on a film.

In the next part we will take closer look at projective transforms.

End of part 1.

Sponsors

Voxel dot net
o Managed Hosting
o VoxCAST Content Delivery
o Raw Infrastructure

Login

Poll
Should this article have a poll?
o Yes. 49%
o No. 50%

Votes: 63
Results | Other Polls

Related Links
o Euclidean
o geometry
o basic
o matrix
o vector
o algebra
o Also by i


Display: Sort:
A Gentle Introduction to Projective Geometry, Part 1. | 135 comments (71 topical, 64 editorial, 1 hidden)
complete crap (1.34 / 35) (#17)
by turmeric on Mon May 26, 2003 at 11:26:38 AM EST

dear math jerks,

before posting any more 'articles' i would ask that you spend a year or two without reading any math gobbldycrack or any journals or papers or anything. during this time you will start to remember how to speak a little langauge known as 'english'. after this perhaps you have a chance of communicating with other human beings instead of robotic professors who hate their jobs.

also, as a special note to this particular artciel author, projection geometry does not require vectors, it does not require matrices, and it sure as hell does not require complicated words. it might require basic euclidean geometry but nowhere near the amount of crap you seem to think it does.



Dearest Turmeric. (4.56 / 16) (#18)
by i on Mon May 26, 2003 at 11:46:24 AM EST

First, a 'langauge' called English is looks infinitely better when you capitalise your words properly. This is something you should never forget. Also, if you refrain from insulting your audience, or at least chose your insults creatively, it might, just might, actually listen to you.

Second, though projective geometry surely does not require matrices and vectors, they come handy when you apply it to real life tasks such as computer graphics. On the other hand it does not require Euclidean geometry.

and we have a contradicton according to our assumptions and the factor theorem

[ Parent ]

Hey Beavis. (1.66 / 3) (#41)
by tkatchev on Mon May 26, 2003 at 04:19:07 PM EST

He said "gauge".

   -- Signed, Lev Andropoff, cosmonaut.
[ Parent ]

More complete crap (3.80 / 15) (#24)
by buck on Mon May 26, 2003 at 01:01:30 PM EST

Dear Retards,

Before posting any more 'comments', I would ask that you spend a year or two learning how to use the shift key on your keyboard. During this time you will start to remember how to do something known as 'capitalization'. After this perhaps you have a chance of communicating with other human beings instead of people who are unable to sit the right way on a toilet seat.

Also, as a special note to this particular comment author, I used to be Pro-Life until I read your comment. Kids, if this isn't a good reason to practice safe sex, I don't know what is.

-----
“You, on the other hand, just spew forth your mental phlegmwads all over the place and don't have the goddamned courtesy to throw us a tissue afterwards.” -- kitten
[ Parent ]

Reading math (3.25 / 4) (#46)
by The Writer on Mon May 26, 2003 at 04:59:21 PM EST

I have not read a single math journal in at least 6 years. Neither papers or any other math publication, except perhaps for 1-2 pages of an old calculus text. Just so you know.

[ Parent ]

Beware us maths jerks (5.00 / 2) (#107)
by flo on Wed May 28, 2003 at 01:08:08 AM EST

Dear muggles,

You'd better start showing us some respect, or one day we'll revoke the Law of Large Numbers and cause your computer to explode.
---------
"Look upon my works, ye mighty, and despair!"
[ Parent ]
one "application" (4.70 / 10) (#25)
by BlueOregon on Mon May 26, 2003 at 01:35:15 PM EST

One of my favorites, at least, and simple as well.

Suppose you're doing a perspective drawing, and say you want the floor of a room in the drawing to be tiled with regular geometic shapes - a square or hexagon, for example. Obviously if your perspective were from "above" it would be the same as drawing a regular square or hexagon on on paper, but that's likely not the case. How to go about this? You could simply guess ... try to make it "look right" by experiment. You could use an actual floor or what not as a model, but you'd have to get the angles right. Or you could, like many Renaissance artists, use a variety of tools to draw something that already exists.

Or you could use projective geometry to get it right. For example, given any four non-colinear points you can create a "projective regular hexagon" ... and once you have one you can tile the whole "plane."

It's great for anyone doing perspective drawings. A compass is neither needed nor useful since projective geometry doesn't preserve angles, only relationships between points and lines. A straight-edge, however, is needed.

Interesting approach (4.80 / 10) (#42)
by Kalani on Mon May 26, 2003 at 04:28:10 PM EST

I think I should preface my comment by saying that it's easy for people to sit back and criticize articles without going to the trouble to write an article themselves. I thought your article was pretty clear about most things and it got to some of the nice aesthetic qualities of projective geometry quickly.

However, I think that if I was aiming at the general k5 audience I'd write an article on projective geometry a little differently.

You essentially have one sentence that covers the controversy over Euclid's parallel postulate, the failed efforts to derive it from the other axioms, the fact that Gauss felt he had to hide his work on non-Euclidian geometry to escape the vitriol of his fellow mathematicians and so on. I think you'd get the average reader to care more if you covered all of this stuff (or summarized it and linked to a more detailed historical account of some sort), because otherwise the average reader might not even care to question it. I suppose that might upset some people, and I'll get some replies saying spiteful things like that we shouldn't try to cater to "idiots", but I think it's obvious that in most cases it's a problem of people simply not knowing about the aesthetic principles and such that make it obvious.

Also, I think that it would help people to bring the coming examples into the very first submission. The projection transformation is easy to grasp in an intuitive way, and a few diagrams would make most of the other equations obvious. Obviously generalized projection is more complex than the simple case of projecting polygons onto a plane, but I think it provides people with an easy springboard to jump up to the more generalized operation of projection (plus it's a natural way to introduce things like properties of objects that are invariant under projection and so on).

The line/point duality treatment was great. It was the perfect introduction for homogenous coordinates I think.

Anyway, it looks like this could be an interesting series of articles.

-----
"I have often made the hypothesis that ultimately physics will not require a mathematical statement; in the end the machinery will be revealed
not to disagree (none / 0) (#99)
by the sixth replicant on Tue May 27, 2003 at 07:57:17 PM EST

but one of the things about the way maths is taught is how unhistorical it is. i mean my physics, even, heaven forbid, my computer science classes usually defined things is a historical way/context (eg Ultraviolet catastrophe, retrograde motion of the planets).

I never got that in my maths classes UNLESS we were doing some mathematical physics (eg mainifold theorems) and then you started hearing about Einstein, Poincare, Lorenz etc.

Never in maths (or rarely).

[ Parent ]

Really? Hmm (none / 0) (#105)
by Kalani on Wed May 28, 2003 at 12:39:05 AM EST

Maybe it's just because I've taught myself most of the math I know that I'm asking for historical context. I've frequently stumbled into interesting areas of math by following the history of math and the interests of notable mathematicians. Of course mathematics is interesting and useful in its own right, but I've found the history to give the math a particular kind of personal feeling.

Really it would have been great to have some diagrams and intuitive cases demonstrated with this article. I just think that most people will pick it up more quickly that way. I personally think that the history involved makes up an interesting story, but it's really not necessary for explaining the mathematical concept (although at least this mention will hopefully inspire some people to go out and look it up).

-----
"I have often made the hypothesis that ultimately physics will not require a mathematical statement; in the end the machinery will be revealed
[ Parent ]
one of the reasons (none / 0) (#110)
by the sixth replicant on Wed May 28, 2003 at 07:29:36 AM EST

is that a lot of maths is not taught in chronological order. For instance you might have a very old theorem but the proof in only 50 years old. Also history doesn't add much to the learning process in maths (btw, i'm a history buff so i'm not saying this just because i don't like history).

Maths just isn't taught this way (and internationally too) for some reason. Maybe it'll be better if it was - personally, i don't really need to know which dead white guy prooved which lemma, but that's me.

Ciao

[ Parent ]

Historical approach for undergraduates (none / 0) (#112)
by Three Pi Mesons on Wed May 28, 2003 at 03:35:40 PM EST

In analysis, particularly, our approach today is very different to that of even the nineteenth century. We have a significantly better understanding of continuity, for example. So while it would be possible to present the development chronologically, it would be very difficult to follow: you'd have to keep going back and correcting yourself, changing definitions, and so on. You see this sometimes in the Mathematical Intelligencer, say, but that's really for curiosity value for people already well-grounded in the subject.

Where you do see history mentioned in teaching is in the "motivation" for a topic - like the efforts to solve the quintic leading into Galois theory.

Perhaps it would be worthwhile having an undergraduate maths course that was taught like that, to give people more of a feel for what the development of mathematics was actually like - full of missteps and blind alleys. Too often it seems like definitions and theorems just come out of the air.

:: "Every problem in the world can be fixed with either flowers, or duct tape, or both." - illuzion
[ Parent ]

History of math (none / 0) (#120)
by vernondalhart on Thu May 29, 2003 at 12:24:53 PM EST

There is a class at my university that teaches the history of mathematics. As I understand it, they make you work with mathematical concepts using only the techniques available at that time. From what I understand, its certainly an interesting course, to say the least...
-- "It's like that old saying: A conservative is a liberal who's been attacked by aliens." Simon - mhm27x5
[ Parent ]
Mathematics isn't science (1.22 / 22) (#44)
by BankofNigeria ATM on Mon May 26, 2003 at 04:49:06 PM EST

It's a language.

1. S 2. V 3. PREP 4. V 5. N 6. PRO 7. N 8. PREP 9. V 10. V 11. V 12. PRO 13. PRO 14. V 15. N 16. V 17. PREP 18. ADV 19. N 20. ADV

Yes. (2.00 / 2) (#45)
by i on Mon May 26, 2003 at 04:52:01 PM EST

But it's a language of science.

and we have a contradicton according to our assumptions and the factor theorem

[ Parent ]
Languages have dialects (1.20 / 15) (#49)
by BankofNigeria ATM on Mon May 26, 2003 at 05:17:11 PM EST

For instance, ebonics mathematics differs from classical mathematics. We need more cohesion.

1. S 2. V 3. PREP 4. V 5. N 6. PRO 7. N 8. PREP 9. V 10. V 11. V 12. PRO 13. PRO 14. V 15. N 16. V 17. PREP 18. ADV 19. N 20. ADV
[ Parent ]

I assume you are familiar (2.25 / 3) (#50)
by knott art on Mon May 26, 2003 at 05:23:11 PM EST

with the works of George Bruce Halsted?
Knott Art
Alas. (none / 0) (#53)
by i on Mon May 26, 2003 at 05:41:22 PM EST

Wrong major, wrong country.

and we have a contradicton according to our assumptions and the factor theorem

[ Parent ]
Plane properties, the first. (4.00 / 7) (#52)
by codemonkey_uk on Mon May 26, 2003 at 05:30:39 PM EST

I worked this particular little rule out when I was playing with two Frisbees in primary school, and was struck with the belief this was absolutely the most amazing thought that anyone had ever had. I went on very quickly to 'realise' that any three points on a plane make a triangle.

Not that that is a partiular big deal now, or especially relevent to the article. I just wanted to share.
---
Thad
"The most savage controversies are those about matters as to which there is no good evidence either way." - Bertrand Russell

Well... (4.33 / 3) (#56)
by theElectron on Mon May 26, 2003 at 07:01:52 PM EST

Only if you're willing to call a line segment a special case of a triangle

--
Join the NRA!
[ Parent ]
And... (5.00 / 1) (#95)
by czth on Tue May 27, 2003 at 02:00:12 PM EST

Since he didn't say distinct, a point a special case of a line segment? :)

czth

[ Parent ]

Maybe I'm just stupid... (3.62 / 8) (#55)
by Kasreyn on Mon May 26, 2003 at 06:46:25 PM EST

"For any two distinct lines, there is exactly one point that is common to both of them."

...but what if the lines are parallel? Or are parallel lines not possible in a "projective" plane, whateverthefuck that is?

[waits patiently for someone to showoffishly explain how stupid he is]


-Kasreyn

P.S. Abstaining due to having forgotten all my math beyond basic trig. =\


"Extenuating circumstance to be mentioned on Judgement Day:
We never asked to be born in the first place."

R.I.P. Kurt. You will be missed.
Hm. (4.85 / 7) (#57)
by i on Mon May 26, 2003 at 07:16:04 PM EST

"Parallel" is synonymous to "not intersecting" in Euclidean plane. It doesn't make sense to extend the notion of parallelity to projective plane: we've just required every pair of lines to intersect! What then would parallelity mean?

Your "whateverthefuck that is" remark neatly sums up the axiomatic approach, and I applaud you for it. We pick a set of axioms that describe something, then we pick a name for it (we picked "projctive plane") and work with whateverthefuck that is.

Was that showoffish enough?

and we have a contradicton according to our assumptions and the factor theorem

[ Parent ]

ahh, (3.50 / 4) (#58)
by Kasreyn on Mon May 26, 2003 at 07:25:10 PM EST

so we're talking about a wholly different geometry.

How does this apply to the real world? Is this one of those abstract concepts that can be used to solve actual problems in math, or is this just a flight of fancy? No offense, but I waste enough of my life with abstract literary concepts, so I restrict my math to that which could actually prove useful to me...


-Kasreym


"Extenuating circumstance to be mentioned on Judgement Day:
We never asked to be born in the first place."

R.I.P. Kurt. You will be missed.
[ Parent ]
It is very applicable to the real world. (4.66 / 3) (#60)
by i on Mon May 26, 2003 at 07:39:59 PM EST

Every time you're looking at a photograph or a realistic drawing, computer-generated or otherwise, you are looking at a projective transform of the real object. A shadow of an object on a flat surface is a projective transform too. If you want to generate images of 3D objects correctly and efficiently, projective geometry is the tool to use.

and we have a contradicton according to our assumptions and the factor theorem

[ Parent ]
Renaissance painters used projective geometry (4.66 / 3) (#61)
by morkeleb on Mon May 26, 2003 at 07:40:58 PM EST

To make their paintings appear 3-dimensional. It's also used in 3-d games engines to project 3d computer generated objects onto a 2-dimensional screen.

How's that for real-world applications?
"If I read a book and it makes my whole body so cold no fire can ever warm me, I know that is poetry." - Emily Dickinson
[ Parent ]
Actually (5.00 / 3) (#62)
by Kalani on Mon May 26, 2003 at 07:47:59 PM EST

It's very applicable to the real world. In fact, it's not the only non-Euclidian geometry with real world applications. It's not at all unreasonable to wonder about actual applications of this in the real world ... not because you want to restrict yourself to a real world model (as some "culture of the word" mathematical purists might complain) but because it gives you a simple gradual step up to building an accurate mental model (with perhaps a freer set of constraints than a real world model might impose).

Anyway, to get to your point, one place where this applies to the real world is in describing what happens when things in the real world are registered by your eyeballs. At the back of your eye you have an (approximate) plane upon which the world is projected. If you're making a computer game and you want to show accurate behavior of objects in a 3D world, you use these techniques to "project" them onto the screen. Beyond that you can apply this mathematical framework to everything from special effects in movies (take a look at the "behind the scenes" clips from Lord of the Rings some time -- they apply this model analytically to achieve certain "depth of field" effects) to accurate perspective-correct paintings. There are many applications of this mathematical framework (though some can be fairly esoteric).

In fact, I'd argue that the usefulness of projective geometry can serve as inspiration for people to explore the other non-Euclidian geometries that are possible (and frequently used in many different fields today).

-----
"I have often made the hypothesis that ultimately physics will not require a mathematical statement; in the end the machinery will be revealed
[ Parent ]
More applications of non-Euclidian geometry (5.00 / 2) (#74)
by flo on Tue May 27, 2003 at 12:58:47 AM EST

Elliptic curves spring to mind. These are actually useful these days in cryptography. The whole theory of elliptic curves only really makes sense in projective space.

Another type of non-Euclidian geometry is hyperbolic geometry (sort of the opposite of projective geometry: here for any given line and given point not on the line, there are infinitely many different lines through the point which don't intersect the given line). This is also important for elliptic curves, specifically for modular forms and modular elliptic curves. I won't go into details.
---------
"Look upon my works, ye mighty, and despair!"
[ Parent ]
Yes, Elliptic Curves! (4.50 / 2) (#102)
by Hideyoshi on Tue May 27, 2003 at 11:30:31 PM EST

A subject near and dear to me.

For anyone interested in an undergraduate level introduction to elliptic curves within the context of arithmetic geometry, I'd recommend Silverman's "Rational Points on Elliptic Curves", published by Springer Verlag (who else?) In it you'll also get to see the projective transformation at work, and how it ties elliptic curves to at least one fairly well-known problem in number theory ...

[ Parent ]

Elliptic Curve books (5.00 / 3) (#106)
by flo on Wed May 28, 2003 at 12:56:19 AM EST

Actually "Rational points on elliptic curves" is written by Joe Silverman and John Tate. I think you got it mixed up with Silverman's other books on the topic, which are more technical.

For those with a strong maths background, these books are:
  • J.H. Silverman: "The arithmetic of elliptic curves" - this is the bible of elliptic curves
  • J.H. Silverman: "Advanced topics in the arithmetic of elliptic curves" - is that a cool title or what? Actually, it's just volume 2 of the above book.
  • M. Hindry and J.H. Silverman: "Diophantine geometry: an introduction" - this is not just about elliptic curves, but diophantine geometry in general (which includes ECs). <blatant namedropping> Marc Hindry happens to be my PhD supervisor </blantant namedropping>.
They are all very well written, but do require some background in algebra and plenty of mathematical maturity.
---------
"Look upon my works, ye mighty, and despair!"
[ Parent ]
My Bad! (none / 0) (#111)
by Hideyoshi on Wed May 28, 2003 at 02:56:03 PM EST

You're right. I didn't notice the omission until after I'd submitted the post (I actually have a copy of Silverman's AEC in front of me right now, but I didn't think it approachable enough to recommend to anyone who wouldn't know about the book already.)

Going further on the same topic, what exactly is your PhD dissertation on? I used to be very much into arithmetic geometry - the ABC conjecture was a particular interest of mine - but I haven't kept as much in touch with the subject in the last 3 years, now that I have to work full-time.

[ Parent ]

My thesis (none / 0) (#118)
by flo on Thu May 29, 2003 at 12:59:23 AM EST

was titled "On the Andre-Oort conjecture and Drinfeld modular curves". I'm currently working on Drinfeld modular varieties now, but am also still interested in elliptic curves, especially over global function fields. Hindry isn't really an expert on Drinfeld modules and the like, but when I started, he wanted me to work on abelian varieties and such.
If you're that interested, you can download my thesis here. Those pages haven't been updated recently, however.

So what kind of work are you doing, if it doesn't allow you to play with arithmetic geometry anymore?
---------
"Look upon my works, ye mighty, and despair!"
[ Parent ]
Two parallel lines (4.50 / 4) (#59)
by morkeleb on Mon May 26, 2003 at 07:30:42 PM EST

In a projective plane intersect at the point of infinity. You can think of a projective plane as being a canvas an artist paints on...so in the canvas if you were trying to draw a pair of railroad tracks going off forever, you would draw them as getting closer and closer together and finally meeting at a point (because you would want to draw the illusion of 3d depth on a 2d surface).


"If I read a book and it makes my whole body so cold no fire can ever warm me, I know that is poetry." - Emily Dickinson
[ Parent ]
Minor correction (4.00 / 1) (#73)
by flo on Tue May 27, 2003 at 12:51:31 AM EST

Parallel lines in the projective plane intersect in a point at infinity. There are plenty such points, a whole (projective) line full of them, in fact.
---------
"Look upon my works, ye mighty, and despair!"
[ Parent ]
oooops....you're right (none / 0) (#78)
by morkeleb on Tue May 27, 2003 at 06:02:57 AM EST


"If I read a book and it makes my whole body so cold no fire can ever warm me, I know that is poetry." - Emily Dickinson
[ Parent ]
-1 TP (1.02 / 48) (#65)
by BankofNigeria ATM on Mon May 26, 2003 at 08:17:54 PM EST

I printed out a copy of this and wiped my ass on it. This article sucks, no one cares about math. Therefore, -1 Toilet Paper.

1. S 2. V 3. PREP 4. V 5. N 6. PRO 7. N 8. PREP 9. V 10. V 11. V 12. PRO 13. PRO 14. V 15. N 16. V 17. PREP 18. ADV 19. N 20. ADV

don't have enough (2.25 / 4) (#69)
by freya on Mon May 26, 2003 at 09:59:46 PM EST

focus right now to read this, will read later. interesting topic

Thanks for letting me know! (nt) (none / 0) (#103)
by gilrain on Tue May 27, 2003 at 11:44:54 PM EST



[ Parent ]
Nice little geometry problem (5.00 / 4) (#71)
by flo on Tue May 27, 2003 at 12:36:50 AM EST

Here's a nice problem, that becomes even more fun once you understand the projective plane and duality between points and lines.

Consider a set S of points in the plane (projective or Euclidian). We say S is complete if it has the following property. Draw all the lines which coincide with pairs of distinct points in S (these are called connecting lines). Then every pair of distinct connecting lines intersect at a point that is already in S.

Examples of complete sets are:
  1. The whole plane (projective or Euclidian)
  2. The empty set
  3. Sets containing 1, 2 or 3 points
  4. Any set of points which all lie on a single line
  5. Any set of points such that all but one of the points lie on a single line (e.g. the vertices of a triangle).
  6. A set of 5 points, consisting of the vertices of a parallelogram and its center.
By now you should get the idea. Sets of the form (1)-(5) are complete in both the projective and Euclidian planes. Also, examples (3) and (4) are special cases of (5). A set of the form (6) is only complete in the Euclidian plane. This is because in the projective plane, a pair of "parallel" lines which form opposite sides of the parallelogram meet in the ideal line (I see the author has wisely avoided the term "line at infinity"), but this point on the ideal line was not part of the original set.

Now for the problem: Prove that every finite complete set is of the form (2), (5) or (6) above.

Now for a somewhat harder problem. A set of points S is said to be dense in the plane (projective or Euclidian), if every circle of non-zero radius, no matter where or how small, contains points of S. In other words, a set is dense if printing it would give you a completely black page, no matter at what resolution. Homework: show that every complete set which is not of the form (2), (5) or (6) above is dense.

One last meta-problem: generalize this to three dimensional (or n-dimensional) spaces.
---------
"Look upon my works, ye mighty, and despair!"
I'll take a stab at it... (none / 0) (#94)
by czth on Tue May 27, 2003 at 01:55:42 PM EST

Now for the problem: Prove that every finite complete set is of the form (2), (5) or (6) above.

Label the finite set of points P having n elements p0 to pn-1. Iff (if and only if) n = 0 we trivially have (2), so henceforth consider only n >= 1.

(6) is valid only for n = 5, it's not hard to see that all combinations of lines will not, by intersection, produce any new points (this can be shown by construction); furthermore if the centre point is missing, the set is not complete (because the centre point can be trivially derived); if any other point is missing, it reduces to (5). If a point is added, it cannot be collinear with all other sets of collinear points, thus affords an intersection that allows a new point, and thus the set would not be complete.

Perhaps it would have been better to start inductively; n = 0 clearly is valid by (2), n = 1..3 by (3), then consider the addition of the first (n+1)th non-collinear point (if the points make a line then they continue to describe a complete set by (4)). The set of pairwise lines now generated still does not realize any new points, since there are no intersections (except of entire lines on the existing "line", which do not add new points); the lines formed through pn are distinct. Points collinear with the first n may be still added to the set without violating the condition for completeness.

The difficulty is with adding a second point not collinear with the first n. If this is done either the set becomes incomplete or case (6) is introduced (and no more points may be added, as shown above). For case (6) we require that both (a) n = 4 and (b) that there already exist a point in the first n collinear with the two points added (if not, one can be generated and the set is not complete).

It remains to show that if either (a) or (b) are not satisfied then the addition of the second non-collinear point affords an incomplete set (or an infinite complete set, I suppose). Construct a line l0 containing point pn and a point on the "line" such that l0 does not contain pn+1 (such a point exists trivially, because the "line" must have at least 2 points). Construct l1 between pn+1 and a point on the "line" such that l1 does not contain pn and is not parallel to l0 (possible because n is at least 3 and the case where there are 3 points on the line that do not allow the construction has been eliminated - the parallelogram). The intersection of l0 and l1 will describe a new point, thus the set is no longer complete, QED.

A little long, I've been out of school for a while....

For the second, using the first result we know that the problem is equivalent to "show that all infinite complete sets are dense"; I'll come back later and see if I can come up with a proof.

czth

[ Parent ]

Mistake? (none / 0) (#104)
by flo on Wed May 28, 2003 at 12:34:48 AM EST

Firstly, there seems to be some minor mix-ups between points Pn and Pn+1, but that is not important.

Another little mistake is
For case (6) we require that both (a) n = 4 and (b) that there already exist a point in the first n collinear with the two points added (if not, one can be generated and the set is not complete).
(b) does not follow. Suppose P1,...,P4 are the vertices of a square, numbered anti-clockwise, starting with the lower left corner. Then, after I've added the forth point, there will not be a point on the base line collinear with the last two added, as the connecting line of these last two is parallel to the base line.

But that is also not important. What is important is your underlying idea: You add points one after another, and show that, at some stage you have n points forming a complete system, but adding an (n+1)th point will make the resulting system incomplete. That is not enough to complete the proof, however, as you have not ruled out the possibility that adding finitely many more points might make the system complete again.

But you're getting close :) Here's a hint: prove that a finite complete set cannot contain a subset of the following form (i.e. such a subset of points would generate an infinite set if you keep adding intersection points of the connecting lines): four points A,B,C,D such that ABC forms a triangle, and D is in the interior of the triangle (i.e. does not lie on any of the sides). Once you've done that, it remains to show that any finite set not containing such a triangle with interior point must be of the form (2)-(6).

Warning: the density problem is harder, you must show that the "bad triangle" above will generate a set which is not just infinite, but also dense.

Have fun :)
---------
"Look upon my works, ye mighty, and despair!"
[ Parent ]
Slight rewording (none / 0) (#123)
by dcturner on Thu May 29, 2003 at 04:37:48 PM EST

Then every pair of distinct connecting lines intersect at a point that is already in S.

Then Euclidean space isn't complete. Or rather, it probably is because you said it is but I'm confused. Do you mean the following?

The point of intersection of any pair of distinct connecting lines is in S.


Remove the opinion on spam to reply.


[ Parent ]
Nope, now I've confused me (none / 0) (#124)
by dcturner on Thu May 29, 2003 at 04:44:54 PM EST

What I mean is:

\forall L1 \ne L2, L1 \cap L2 \subset S

Apologies, the HTML to do this escapes me.

Remove the opinion on spam to reply.


[ Parent ]
Correction (none / 0) (#128)
by flo on Fri May 30, 2003 at 12:38:21 AM EST

The Euclidian plane is complete in Euclidian geometry. But the subset of the projective plane, which can be identified with the Euclidian plane, is not complete in Projective geometry.

Thanks for pointing this out. So let me correct my definition.

Choose a geometry, either Euclidian or projective (that amounts to choosing an axiom concerning parallels - hell, you could even choose any other geometry, such as hyperbolic). Then a set S in the (Euclidian/projective/other) plane is deemed complete if every pair of distinct connecting lines of S either don't intersect (if this is possible in the chosen geometry), or intersect in a point in S.

Please note that "complete" is my own terminology here. The same term is also used in other contexts in mathematics, and means different things. So don't assume your professor has ever heard of this definition ;)

I'm still waiting for somebody to solve my problem :)
If nobody does, I'll post the solution sometime next week.
---------
"Look upon my works, ye mighty, and despair!"
[ Parent ]
Solution (Spoiler) (none / 0) (#135)
by flo on Fri Jun 06, 2003 at 01:04:50 AM EST

Okay, so only one guy tried it and nobody solved it. I'm disappointed... as promised, here's the solution, which you'll see isn't even terribly difficult.

Bad triangles
First, the notion of a "bad triangle". This is a triangle ABC with a point P in its interior, which doesn't lie on any of the sides of ABC. We denote it by (ABC,P)

Lemma. Any complete set containing a bad triangle is infinite.

Proof. Let S be a complete set containing a bad triangle (ABC,P). The line BP intersects AC in a point B1, and CP intersects AB in C1. Both B1 and C1 must again lie in S. Now consider the line B1C1. It intersects AP in P1, which must also lie in S. Now we see that S also contains the bad triangle (ABC,P1). We repeat the above procedure, and find another bad triangle (ABC,P2), with P2 between P1 and A, etc. It follows that S must contain infinitely many points P1,P2,P3, etc, so S is infinite. QED

We now use the lemma to prove the following theorem. (The word "lemma" means theorem, but a theorem which is less interesting in its own right, and proved mainly because it is useful for proving a more important theorem.)

Theorem. Let S be a finite complete set (in either Euclidian or projective geometry). Then S is of one of the following forms:
(1) All points of S, except possibly for one, lie on a single straight line.
(2) S consists of the vertices and center of a parallelogram. (This is only possible in Euclidian geometry).

Proof. Let S be a finite complete set. We consider its convex hull H. This is the smallest convex polygon containing S. Intuitively, the convex hull is what you get when you stretch an elastic band around all the points in S and then let it go. Let n be the number of vertices (corners) of H (note that these vertices all lie in S).
(1) If n is more than 4, then H has two sides, which do not meet in a corner, but which are not parallel, hence meet in another point outside H. This point would have to be in S (as S is complete), but that's impossible, as we assumed that all of S lies in H. So H has at most 4 vertices.
(2) If n=4, then the 4 vertices must form a parallelogram ABCD, for the reason shown above. Then S must also contain the center P of the parallelogram. If S also contains another point Q, besides A,B,C,D and P, then Q must lie in the interior of one of the four triangles ABC,ABD,ACD,BCD, and we get a bad triangle. Hence, from the lemma, S must be infinite, a contradiction. So we've seen that if n=4 then S is precisely the set of vertices and center of a parallelogram. And this is only complete in Euclidian geometry.
(3) If n=3, then the three vertices ABC of H form a triangle. All other points lie inside ABC. If any point lies in the interior of ABC, then we get a bad triangle, and hence a contradiction. So all the remaining points must lie on the edges of ABC. But if we have two points, P and Q, lying on different edges (say AB and AC, respectively) then BQ and PC intersect in an interior point R, and (ABC,R) is again a bad triangle. So the only possibility is for all other points to lie on only one edge of ABC. This give the form where all but one of the points of S are collinear.
(4) Lastly, if n=2, then H is a line, and all the points of S are collinear. QED.

As for showing that any complete set S not of one of the forms above is dense? Well, for that you must show that any complete set S containing a bad triangle is not only infinite, but also dense. Maybe somebody else will want to give it a shot. It is a little bit more difficult. Have fun!
---------
"Look upon my works, ye mighty, and despair!"
[ Parent ]
-1 (1.14 / 21) (#79)
by ragman on Tue May 27, 2003 at 10:52:16 AM EST

Math is for nerds and computers.

Um... So? (none / 0) (#117)
by pla on Wed May 28, 2003 at 07:49:25 PM EST

Math is for nerds and computers.

...And of course, we don't have ANY such folks on K5, now do we?


Now if only part 2 will deal with projective hyperplane mapping onto reduced dimensional spaces, I'll call this a good series (and useful to a personal research topic of mine). ;-)


[ Parent ]
+1 to section page (5.00 / 3) (#82)
by djeaux on Tue May 27, 2003 at 12:34:33 PM EST

It is assumed that the reader is somewhat familiar with Euclidean geometry and basic matrix and vector algebra.
That's probably a bit too stiff a set of prerequesites for the average K5 reader...

djeaux
"Obviously, I'm not an IBM computer any more than I'm an ashtray." (Bob Dylan)

Not if they've been through high school. (nt) (5.00 / 1) (#85)
by gilrain on Tue May 27, 2003 at 01:07:14 PM EST



[ Parent ]
highschool: (1.00 / 1) (#125)
by Prophet themusicgod1 on Thu May 29, 2003 at 06:38:01 PM EST


i was in advanced courses in highschool. we spent 1 class on matrix-work...but 95% of class was talking about sports, and basketball(brit, especially). i got to university math and failed - they just didnt teach us anything and by university we were expected to know
it appears that getting hundreds of questions of homework done every night so that we were burned out all the time *(and thus couldnt get into trouble) was much more important to learning things...like any of the above.
i still have no idea what a vector is...and beleive me...im about as math-geek as they come around here. and i know im not alone: my highschool had 1500 students...and my city(Saskatoon) had more highschools...
"I suspect the best way to deal with procrastination is to put off the procrastination itself until later. I've been meaning to try this, but haven't gotten around to it yet."swr
[ Parent ]
Get some books and read up (none / 0) (#133)
by hex11a on Mon Jun 02, 2003 at 07:08:36 PM EST

I recommend AG Hamilton's Linear Algebra. You can catch up on stuff you were never taught if you have an open mind and an open book. It's harder, yes, than being taught, but it's certainly not impossible. In the summer vacation before I came to university I taught myself everything I needed to know about matrices, vectors etc and I'm glad I did, because they went at lightning speed once I got here!

Hex

[ Parent ]

thanks for the reply (none / 0) (#134)
by Prophet themusicgod1 on Thu Jun 05, 2003 at 11:07:17 AM EST

and yes, this appears to be the plan. until further motivation extinguishes and i collapse(it happens occasionally ;), i have a good 8-10 books on the go All_The_Time(mathwise and otherwise) catching up on missed oppertunity, and generally just absorbing stuff. i kind of am taking a leave from math to figure out how to use linux, and a few other things. so far with little success, but after a good 30 *n*x/*BSD installs (10 last night alone) i at least have some things working...
"I suspect the best way to deal with procrastination is to put off the procrastination itself until later. I've been meaning to try this, but haven't gotten around to it yet."swr
[ Parent ]
This article better not make it to the front page (1.75 / 8) (#84)
by cux on Tue May 27, 2003 at 12:55:20 PM EST

it will only encourage them.

-
"Chaos, Mr. Who," Lupus Yonderboy said. "That is our mode and modus. That is our central kick."
-1 Resection (1.05 / 17) (#87)
by debacle on Tue May 27, 2003 at 01:12:12 PM EST

This belongs under "Technical Circle-Jerk."

It tastes sweet.
oh my god (4.00 / 5) (#98)
by the sixth replicant on Tue May 27, 2003 at 07:50:02 PM EST

I did my PhD thesis in finite projective geomery. Jesus, I thought this stuff was out of bounds for a public forum. But, no, I'm wrong. Could I use my powers for good?

Ummm

Ciao

Cool. (none / 0) (#100)
by i on Tue May 27, 2003 at 08:25:52 PM EST

Go ahead.

and we have a contradicton according to our assumptions and the factor theorem

[ Parent ]
approach (5.00 / 1) (#115)
by adiffer on Wed May 28, 2003 at 04:17:40 PM EST

Remember that many of us aren't up to the high power stuff, so start at a level we can hope to master and then work up.

You will have to deal with the usual crap from those who wish to remain ignorant around here, but know that many of us would really appreciate some intellectual contributions.  Find your courage and then write something up!  8)
--BE The Alien!
[ Parent ]

Matroid Theory (4.50 / 2) (#113)
by unshaven on Wed May 28, 2003 at 03:46:35 PM EST

Wow, it's quite interesting to see this up here, especially since I got into mathematics because of a finite projective geometry course.  Good article, looking forward to the next.

And, anyone who finds this fun can also look into matroid theory, which is more general (all finite projective geometries are matroids, but not the other way around).  It focuses on generalizing the idea of linear independence and the combinatorics thereof.  It's good stuff, especially oriented matroids.
______________
"I think we found a way to put the fun back in sin." -- Sleater-Kinney

write write write (none / 0) (#114)
by adiffer on Wed May 28, 2003 at 04:13:56 PM EST

please?

I like this kind of stuff.  It does our community some good even if we don't write up text book quality material.
--BE The Alien!
[ Parent ]

Maybe... (none / 0) (#119)
by unshaven on Thu May 29, 2003 at 09:25:49 AM EST

Currently, I'm finishing up my thesis, so just a bit busy.  <cross my fingers> By August, everything should be done.

Thanks for the interest, I'll keep it in mind when I've got a bit more free time.
______________
"I think we found a way to put the fun back in sin." -- Sleater-Kinney
[ Parent ]

yup (none / 0) (#122)
by adiffer on Thu May 29, 2003 at 04:36:31 PM EST

Been there.  Takes lots of work and focus.  Good luck.
--BE The Alien!
[ Parent ]
We know what is projective geometry (none / 0) (#127)
by United Fools on Thu May 29, 2003 at 11:56:35 PM EST

If you have a tree that's 1 meter tall, and its shadow is 0.5 meter long, than another tree 2 meters tall will have a shadow 1 meter long. That sums it up :-)
We are united, we are fools, and we are America!
Walk me through this.... (none / 0) (#129)
by BlaisePascal on Fri May 30, 2003 at 04:03:06 PM EST

You assert that the projective plane is equivalent to a Euclidian plane where some arbitrarily chosen line is declared to be the "ideal line", where "parallel" lines intersect.  I'd like to use that idea to create a projective lattice on a Euclidian plane -- as if I was trying to tile an infinite plane with squares and look at it from above, parallel to the plane.  Standard stuff for projective/perspective drawing.

So...  I'm going to arbitrarily define the line y=100 as my "ideal line", and assume that a=(-1,0), b=(0,0), c=(1,0) and d=(0,1) are points on the lattice.  All other points should be able to be determined by intersections of "parallel" lines -- I will not declare, for instance, that a bunch of lattice points are on the y=1 line unless I can actually construct the y=1 line from at least two points otherwise identified.  I am also going to assume that lines of the form x=a (in the projective plane) converge at e=(0,100).

Immediately I can draw lines a-e, b-e, c-e, and d-e (coincident with b-e).  These lines are parallel, since the intersect at a common point on the ideal line.  Also, they determine one coordinate of three columns of projected lattice points.

I can also draw lines a-d and c-d, which intersect c-e and a-e at f and g, respectively.  a-d and c-d correspond to the diagonals across the lattice, and so should contain all points of the form (x-1,x) and (x,1-x) (both Euclidian and projective).  They are not parallel, but perpendicular.  f and g, then should be points (1,2) and (-1,2) (projective).  I'll draw a line through them, which should be parallel (in a Euclidian sense) to a-c.  It also establishes h (projective point (0,2) at the intersection of f-g and b-e.

a-d should intersect the ideal line at i=(99,100), and c-d should intersect the idea j=(-99,100).  This means that any line parallel to a-d or c-d should also intersect at those points.  So...  Let's add a few more parallels here.....  h-i intersects a-e (at projected k=(-1,1)), a-c (at projected l=(-2,0)), and c-e (at projected m=(1,3)). h-j hits the same three lines at projected n=(-1,3), o=(1,1), and p=(2,0). n-m gives us another horizontal for projected y=3, and we can finally draw l-o to get us the projected y=1 line.

This is where things start to get iffy...  Assuming this was done correctly, l-o should pass through d.  Right?

Not quite. (none / 0) (#130)
by i on Fri May 30, 2003 at 07:18:56 PM EST

You can't just take a regular Euclidean line and declare it ideal.

To get Euclidean plane from projective, you pick an arbitrary (projective) line and throw it away (declare it "ideal line", "line on infinity", nonexistent, whatever). Conversely, to get projective from Euclidean, you add a new line that is not in Euclidean plane.

It could be visualised as follows. Instead of points, we will talk about families of lines. A set of lines all passing through the same point uniquely determines that point, so it could be though as if it is that point. So instead of points we have bunches of lines, but it's really the same thing. Now attention! We declare that bunches of parallel lines are also points (though these bunches don't really have any common points). We call them ideal points, and together they make the ideal line.

and we have a contradicton according to our assumptions and the factor theorem

[ Parent ]

A Gentle Introduction to Projective Geometry, Part 1. | 135 comments (71 topical, 64 editorial, 1 hidden)
Display: Sort:

kuro5hin.org

[XML]
All trademarks and copyrights on this page are owned by their respective companies. The Rest 2000 - Present Kuro5hin.org Inc.
See our legalese page for copyright policies. Please also read our Privacy Policy.
Kuro5hin.org is powered by Free Software, including Apache, Perl, and Linux, The Scoop Engine that runs this site is freely available, under the terms of the GPL.
Need some help? Email help@kuro5hin.org.
My heart's the long stairs.

Powered by Scoop create account | help/FAQ | mission | links | search | IRC | YOU choose the stories!