How many points does it take to define…

You know how it is. One moment you are relaxing on the grass with some friends discussing the weather, the next you start stretching your mind as to how many points it takes to define various shapes: ellipses, ellipsoids, triangles, what not. Let’s take a peek at this sort of problem.
We’ll start with circles. One of the first things that you learn in school about circles, is that any three noncollinear points define the circumference of one circle, and one circle only. Lets see how that is.
First we show that we can indeed construct a circle that will pass through all three points. Let’s label our points A, B, and C.

We draw the lines AB and BC, and find their midpoints.

Next we extend perpendiculars from the midpoints. They intersect at point O.

AOB is an isosceles triangle, since the line we extended from the midpoint is perpendicular to AB. That means that OA = OB. The same can be said about triangle BOC, and it follows that OB = OC. This means that OA = OB = OC. The point O is equidistant from all three points, and O is the center of the circle.

Having shown that our three points define a circle, now we need to show that only one circle is defined. Suppose that two circles were indeed defined. Then all three of our points would lie both on the first circle and on the second one. This means that our two circles intersect (otherwise there would be no point that is shared by both). But the intersection of two different circles can only occur at either one point (in which case they are tangent), or two points. This contradicts the fact that all three points are defined on both circles – this only happens when the two circles coincide exactly, meaning that they are the same.

Ok, but what about ellipses, which are a generalization of circles? Intuitively, it seems as if it should take four points to define an ellipse, since it’s basically a circle but with “2 radii” instead of one. Unfortunately, by the same reasoning shown above, this intuition does not hold.
Suppose that we have K points, and we want these points to define only a single ellipse. If the points do define two ellipses, then the points must be found on the circumference of both – so they must be on the intersections between the two ellipses. Two ellipses intersect at most at four points – so if we have only four points, we are not able to resolve the ambiguity between the two. In order for there to be a contradiction, there must be at least five distinct points. Note that this proof doesn’t say that five points are enough; it only says that four are not.

The ellipse (and therefore also the circle) are actually part of a family of curves called “conic sections”: circle, ellipse, parabola, hyperbola. These are the shapes you get when you look at the intersection between a cone and a plane.

Analytically, the equation governing the conic sections is of the form:

Ax^2 + Bxy + Cy^2 + Dx + Ey + F = 0

Each point we have at our disposal can be put in as the x and y values, which gives a single equation for A, B, C, D, E, and F. Hence, in the general case, in order to fully find all of the coefficients, we need five points in order to get five linear equations (there are six coefficients, but we can always set one of them to 1, scaling the others accordingly). So the actual answer for an ellipse is five.
Of course, not every five points will give you an ellipse – there might be no solution at all, or the solution might yield a parabola or a hyperbola. This equation also shows us why we only need three points for a circle – in this case, A = C, and B = 0, so there are two less coefficients to find.
As for an ellipsoid – a “3D ellipse” – well, it is a quadratic surface, which is defined by 10 coefficients, meaning that 9 points are needed.

What about a triangle? How many points does it take to define one? While a triangle might seem like a rather simple shape, it actually isn’t when compared with a circle or an ellipse. With the latter two, we have very strong rules about how to draw them – the fact that the points have to be all at an equal distance from the foci limits us greatly, when compared with the freedom of polygons. In fact, with polygons we might have ambiguity with any number of points, since all the points can lie on the same edge. There is no minimal number of points which always generates a unique triangle. Instead we’ll try to think – what is the minimal number points which can (but not necessarily will) generate a unique triangle?
The number that comes up the fastest when we say “triangle” is three, but it takes more than three points to define a triangle. Why, three points define a circle, and that circle can either be a bounding circle of a triangle, or be bounded within a different triangle, so obviously there is an ambiguity.

The minimum number of points that I managed to find that define a triangle is six. That doesn’t mean that every six points define a triangle; it just means that no configuration of five points can uniquely define one. The configuration looks like this:

The fact that there are three collinear triplets “forces” us to draw lines through them, which reduces the freedom we have when drawing the triangle. Notice that by removing just one point (either a center point or an edge point), we can suddenly make all sorts of other triangles.

That’s it for now on defining shapes with points. If you have some spare time, or are for some reason stuck walking back and forth along a fence with nothing to do, consider trying to figure out how many points you need for different shapes in your head; hours of fun are sure to follow.

Advertisements

4 comments

  1. What about if you know the center of the ellipse? I collect data that is in the form of concentric ellipses around a known center point (X-ray Debye rings). However, some rather poor results lately have included only a couple specks of each ellipse with large gaps in between. I am trying to decide the minimum number of points I need to reliably fit an ellipse to these points. Interesting topic in general!

    • Unfortunately, in the worst case, knowing the center still won’t help you, I think. Consider the red and blue intersecting ellipses which I used as an example. It is possible to move the blue ellipse to the left so that there are still four intersection points with the red one, but their centers align. Then the fact that you know the center point doesn’t help you discern between the two, and we are back with the original problem.

  2. Your discussion on triangles is wrong, I believe. Obviously, the 3 vertices of a triangle uniquely define it. Any line segment is composed of an infinite number of points. Three line segments have 3 infinities. Your claim that “The minimum number of points that I managed to find that define a triangle is six.” is no more correct than the claim that it takes 3. Why? Because you add the condition that the 6 must be in pairs. That is an added condition. The only condition necessary for a circle or ellipse is the points must be unique. (And, as you point out, 5 don’t necessarily define an ellipse, while if we accept the idea that a circle may have infinite radius (a straight line) then three always define a circle.) For completeness, I also note that the three pairs of points defining the triangle must be non-parallel (and of course not co-linear which I include with being non-parallel).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s