Author: Yumnam Kirani Singh
Member Calcutta Mathematical Society
Email: kiranisingh@hotmail.com
Some formulae for finding
the centre of a circle or sphere or in general hypersphere, which will pass
through some given number of points are given here. We can draw infinite number
of circles, which can pass through one or two given points. But if the number
of points given is three, then we can draw only one circle, which will pass
through the three given points. Also, we can draw many spheres, which will pass
through any three or less number of given points. But we can draw only one
sphere, which will pass through any four given points in 3-dimension. Similarly,
we can find a unique -dimensional hypersphere, which will pass through
given points.
In this paper, we also show the relation between a circle and a
triangle. Some interesting properties of triangles are also briefly mentioned
here, which may be useful from computational geometry application point of
view. All the formulae given here can be obtained easily with some knowledge of
analytical co-ordinate geometry and hence the derivations are not shown.
We will define points inCartesian co-ordinates. By a two dimensional point we will mean a point which requires two co-ordinates to locate it exactly. Similarly by a three-dimensional point, we mean a point whose exact location requires three co-ordinates and so on.
Formula 1: The co-ordinates
of a point on the perpendicular
bisector of two given points
at a distance d from the mid-point of
In the above formulas indicates there are
two possible values for each of
and
i.e., on the both sides of the line joining
and
Formula 2: Let and
be any three points, then there exists a unique point
, equidistant from
and
whose co-ordinates
are given by
,
Where
And are given by
From formula 2, we know that
there is a unique point in 2-dimensional plane, which is at equal distances
from any three given points in the plane. In other words we can say for every
triangle there exists a unique circle, which can exactly circumscribe the
triangle. Therefore, there cannot be two or more circles, which can exactly
circumscribe a given triangle. So triangles and circles are closely related. In
other words we can rightly say, ‘ A triangle is a plane figure formed by
joining any three points on the circumference of a circle’, or, we can say the
vertices of a triangle are any three points on a circumference of a circle.
We know a triangle is closely related to a circle. If the vertices of a triangle are given, then we can easily determine the centre of the circle, which will circumscribe the triangle using formula 2. Otherwise we have to use some geometrical means to find the centre. Now we describe a simple geometrical means to find the center of a circle, which will circumscribe a given triangle, as follows.
Property-1: The bisectors of the three sides of a triangle always intersect at the center of the circle, which circumscribe it.
Property 2:
The point of intersection , of the bisectors of the two smaller sides of a triangle gives the center of the circle, which will circumscribe it.
is also known as
Voronoi vertex of the triangle.
This property can be used for computing Delauney triangulation and Voronoi diagram as given below.
Drawing Delauney Triangulation:
Draw triangles in such a way that there exists no other
point whose distance from , the point of intersection of the bisectors of the two
smaller sides of a triangle, is less than the distance of
from any of its vertices.
Fig-2. Delauney Triangulation.
In figure-2, the thick lines give the Delauney tringulation. The thin lines are the bisectors of the two smaller sides of every triangle in the triangulation structure. The + indicates the point of intersections, i.e., Voronoi Vertex of each associated triangle.
Drawing Voronoi diagram:Join the adjacent Voronoi vertices in Fig-2. And draw rays assumed to be emanated from the mid-points of the outermost sides of the Delauney triangulation.
Fig-3. Voronoi Diagram of the points in Figure-1.
The proof of property 1 and
property 2 can be done easily using formula 1.
So by simply using property
2, we can easily find the centre of a circle that circumscribes a given
triangle. As we know a polygon can be decomposed into triangles, we can say
whether there can be a circle that passes through the vertices of apolygon or not.
Also we can say, whether a
given triangle is an acute angled, right angled or an obtuse angled triangle,
using property 2.
If the point of intersection of the bisectors of the two smaller sides
of a triangle lies
(i) inside the triangle, then the triangle is an acute angled triangle.
(ii)on the middle of the third side, then the triangle is a right angled triangle.
(iii)outside the triangle, then the triangle is an
obtuse angled triangle.
This property can be used for computing the minimum enclosing circle of a given set of points.
Formula 3: Let and
be any four points ,then there exists a unique point
equidistant from
and
whose co-ordinates
are given by
,
and
provided
where
and
This formula gives us the
centre of the sphere, which will pass through any four given points in
3-dimension. This can be used for finding Delauney triangulation and Voronoi
diagram of a set of points in 3-dimension. For any three or less number of
points in 3-dimension, we can find infinite number of spheres which will pass
through them, as we can draw infinite number of circles which will pass through
any one or two given points.
Proceeding in this way we can find the centre of a unique n-dimensional hypersphere, which will pass through any given points in
n-dimensions.
Formula 4: Let ,
,
be any
given points in
n-dimensional space, then there exists a unique point
which is equidistant
from all the given points whose co-ordinates are given by
,
,
,...,
provided
=first column of
being replaced by
=second column of
being replaced by
continuing this way,
column of
being replaced by
and
This can be used for finding the centre of the n- dimensional hypersphere for any given (n+1) points. This centre is unique for the given (n+1) points. If the number of points in n-dimensions is less than or equal to n, then we can find infinite number of n-dimensional hypersphere, which will pass through the given points. This can also be used for finding the Delauney tringulation and Voronoi diagram in n-dimension.
References:
Franco P Preparata, M. I. Shamos, (1985), Computational Geometry :An Introduction
G. Toussaint ,(1985), Edt., Computational Geometry,Elsevier Science Publishers, B.V.
Published in News Bull. Cal. Math. Soc. 24(5&6) 21-24(2001).