27 October 2009

Pythagoras On Screen

Euclid of Alexandria "invented" geometry. Before him, there was no squares or circles. Everything was just a collection of messy shapes. One even wonders how they managed to build houses without straight lines and triangles.

Ok, just kidding...

Pythagoras of Samos actually did know a thing or two about triangles before Euclid ever did, so much so that he discovered the mathematical relationship between the sides of right-angled triangles.
How are these two gentlemen related? Well, they lived a couple of centuries apart, so they are not directly related to each other as such, but in terms of mathematics they are very closely related: the pythagorean theorem only "works properly" in euclidean spaces.

What are euclidean spaces? They are those spaces that satisfy the axioms of Euclidean geometry. Most of us have studied Euclidean geometry at school: we learn that the shortest path between two points is the straight line, that the sum of the angles of a triangle is 180 degrees, and other wonderful rules.
A lot of these rules, however, start falling apart when we try to apply them to non-Euclidean geometries. In general, though, if we stick to flat 2-D surfaces (like a piece of paper), Euclid's rules will survive just fine.

Let's test this.

If we draw on a piece of paper a right-angled triangle, with one leg being 300mm long and the other being 400mm long, Pythagoras taught us that the hypotenuse should be 500mm long, and indeed it is. In general, the hypotenuse will always be longer than either of the two legs.
What else do we have, apart from a piece of paper resting on a desk, that is a flat 2-D surface? Well, there's the flat LCD screen on which I'm writing this article, of course. So if I draw a segment that is 300 pixels long, at a right angle with another segment that is 400 pixels long, then I should be able to join the two open ends of each segment with a third segment that is 500 pixels long, right?

Wrong.

Why? The reason is not that difficult to find: the computer screen is not a continuous surface: it's made out of "tiles" called pixels, and each pixel is either turned on or off. There is no such thing as a fractionary pixel, so you can't draw half a pixel, or two-third of a pixel: you either draw it entirely or you don't. In other words, the surface of my LCD screen is quantised. So when the two legs of my right-angled triangle on screen are 12 and 8 pixels long, the hypotenuse cannot possibly be 14.42 pixels. So how long is it? 14 pixels? 15 pixels? Does it round up by eccess or by defect?

Well... Neither.

It turns out that it depends on how you want to draw the line so that it appears continuous to the average person looking at the screen. I think two pixels can be considered contiguous if they touch each other one way or another, even if only by one corner. Sticking to this constraint, the minimum number of pixels required to draw the hypotenuse of the above triangle would be 12, which is the same number of pixels required to draw the longest leg of the triangle.

In my head, this means two very important things:
  1. quantised surfaces are not Euclidean in nature, even though they may intuitively appear to be so
  2. the concept of "distance" between two points on a quantised surface is very, very funny
M.