**Bradley Baetz
<bbaetz@cs.mcgill.ca>
**

The purpose of this page is to describe curves of *constant width*.

Take two parallel tangents to a curve C. The *width* of the curve with
respect to these tangents is then the distance between these two lines. The
*diameter* of C is the largest width for the curve.

A curve is said to have *constant width* if the width is identical
no matter which direction the supporting tangents are in. In a curve of
constant width, it is clear that the (constant) width must be equal to the
diameter. This fact is important in several of the proofs.

For example, a circle is the simplest curve of constant width. It has a
constant width (*r*), which is identical to its diameter. Another basic
curve of constant width, the Reuleaux Triangle (RT) will be further
discussed later.

The Reuleaux triangle

When talking about construction of a curve of constant width, it is useful to
define a *pinching set*. Just by looking at the picture of the RT, it can
been seen that it seems to have a basis of an equilateral triangle (this is
where the *triangle* part comes from.

Formally, a pinching set *V* is a set of points on the boundary of
a curve *C* of constant width such that every diameter of *C* is
incident with at least one point on *V*. In the case of the RT above,
the vertices of the triangle are the pinching set. A circle has a pinching
set of infinite size.

A Reuleaux polygon (or RP) is a curve of constant width which admits a
*finite* pinching set. (This definition excludes the circle, which has
an infinite pinching set). The number of vertices in the pinching set is
referred to as the *order* of the RP. As will be shown, all RPs have an
odd order, and for any odd integer *n* > 3, there exists an RP of
order *n*. The set of vertices making up an RP is referred to as a VRP.

A RP of order 5

The goal here is to produce any of the infinite number of RPs in linear
time. Producing a single RP of degree *n* is trivially possible
by taking a regular star-shaped polygon with n vertices and joining
them as described below. This does not, however, give us an **arbitrary**
RP. In order to do this, we need to keep track of the limitations,
to ensure that we end up with a valid polygon of constant width. An
algorithm to do so is described here.

Now, assume that there exists an edge of length > 1. Then we could take two tangents perpendicular to that edge, and the width between those tangents would be > 1.

Similarly, if there were an edge with length < 1, we could get a width of < 1.

This would mean that we have a width != 1, as well as a width = 1, and so the curve would not be of constant width. Thus no edge in the VRP can be greater than 1, and no edge can be smaller than 1, and so all edges in the VRP must have distance equal to 1.

Now consider the edge between

This implies that each edge must touch all other edges. The reason for this is that if it did not, then the new vertex would be too far from one of the vertices of the untouched edge.

Any edge of the VRP must cross
the existing edge

However, the edge between

For each vertex

The above two proofs, when combined, prove that there exists a VRP of
order *n* for all odd *n* >= 3.

In order to construct a RP, we need the set of vertices in the RP. Once we have the VRP, constructing the RP can be done in linear time, using the construction proof given above.

The above discussion suggests a simple construction of the VRP. The idea behind
this is to place points one by one into an area satisfying the requirements. We
are trying to find an RP of order *n*.

- Choose
*v*in_{1}**R**^{2}and*v*as any point at distance 1 from_{2}*v*._{1} - If n=3, then we can pick either point at distance 1 from both
*v*and_{1}*v*, and then stop._{2} - Else, for each
*v*to_{3}*v*:_{n-1} - Choose
*v*from the intersection of the disks of radius 1 centered at_{x}*v*for all_{i}*i*from 1 to*x*-2, intersected with the disk of radius 1, centered at*v*_{x-1}

The next vertex must lie on the boundary of the green circle, and within all the other circles. - Then the last point,
*v*, is simply the point at distance 1 from both_{n}*v*and_{1}*v*. As_{n-1}*n*is odd, we pick the point on the correct side (which is unique)

It is clear that this solution satisfies the constraints (by construction). This solution takes quadratic time. However, we also need to prove that such a point will always exist. This follows from the proofs above. At each stage, the algorithm adds an additional circle to the requirements, and we need to prove that the intersection of this circle with the preceeding circles is not the empty set. This can be seen from the above diagram - each added circle must at least contain the previous point, as well as the line itsself. These were, by defintion, part of the original intersection, and they are part of the new circle, so they are part of the combined intersection. Thus the combined area is not empty, and so the algorithm works.

The above solution is quadratic because every added point must examine all preceding points. This is clearly inefficient. An obvious improvement would be to avoid requiring this additional lookup. So, how do we do this?

At each step, we can see that we add additional restrictions to the required area. However, the final point lies on an arc, center the previous point, and bounded by the boundaries of other circles. The linear time algorithm produces, at each stage, the points bounding this arc.

This is done by keeping track of the restricted area as follows. Note that
the points are numbered 0 to *n*-1.

- Choose
*v*in_{0}**R**^{2}and*v*as any point at distance 1 from_{1}*v*._{0} - If n=3, then we can pick either point at distance 1 from both
*v*and_{0}*v*, and then stop._{1} - else, choose
*v*anywhere at distance 1 from_{2}*v*(apart from_{1}*v*)_{0} - Then we consider the intersections of the two circles of radius 1
centered at
*v*and_{0}*v*. There are two such points - label the one on the_{1}*v*side as_{2}*p*and the other as_{1}*p*._{0} - Now, for each other point, we update
*p*for even_{m}*m*such that we form a bound on the arc, by setting it to the intersection of the previous points' circle and the arc of radius 1 centered at*v*and bounded by_{0}*v*and_{i}*p*._{m-2} - For odd
*m*we do the same, except the arc is centered at*v*, and bounded by_{1}*v*instead. This is because of the alternating nature of the points, as discussed before._{0} - The last point behaves as in the quadratic algorithm, choosing the single remaining position.

This algorithm takes a linear amount of time, since each point is only examined once.

Heres an example showing a few steps of the algorithm (black points are
part of the VRP; red points are p)

3 points | 4 points | 5 points |

There are two applets. The first one was written by myself from scratch.
Given an odd *n* > 3, it generates a random RP of order *n*.
It implements the quadratic algorithm. Note that this sometimes locks up
under Netscape. It never locks up under the applet viewer, so I have been
unable to debug this - it may be a browser issue. There is also a small
amount of numerical instability in the algorithm, and so occasionally the
final point will have distance > 1, so the arc will be invalid.

To use the applet, type an odd integer > 3 into the text field, and
press enter.

source code

The other applet shows the idea behind the linear time solution. You can start with a regular star-shaped polygon, and distort it, dragging each point along what would be the limited arc. You can also see what happens to the resulting RP when all of the edges do not cross. It was not written by me, and source is not available. To see this applet, click here. (This is an external site which discourages downloading the applet directly)

- 1
*A linear time Construction of Reuleaux Polygons*, Yaakov Kupitz, Horst Martini, Bernd Wegner, Beitrage zur Algebra und Geometrie, Contributions to Algebra and Geometry, Volume 37 (1996), No. 2, 415-527.- 2
*Curves of Constant Width*, http://www.cut-the-knot.com/do_you_know/cwidth.html and http://www.cut-the-knot.com/Curriculum/Geometry/CWStar.html