Re: square through 4 points (was Re Soddy)

From: Dave Rusin (rusin_at_vesuvius.math.niu.edu)
Date: 10/26/04 

Date: 26 Oct 2004 21:59:11 GMT

In article <417D3297.4010705@free.invalid>,
philippe 92 <antispam@free.invalid> wrote:
>Rainer Rosenthal wrote:

>> These days we discussed a funny question: Think of a square
>> in the sand. Put stones 1, 2, 3 and 4 on each of the sides
>> of the square. Wait two days. You see the stones but the
>> square has vanished in the wind. How to reconstruct it?

>Notes, as discussed in de.sci.maths :
>1) the problem may be impossible depending on the positions of PQRS
>2) if we allow PQRS to lie on the lines AB ... not restricted to
> segment AB, Wolfgang said there are generally 6 solutions.

The geometric constructions presented here seem to be fine.
I thought I'd look at this one algebraically. I noticed along the
way that there was a simple geometric construction and now that I
actually look at the methods already posted, I think the algebra
has led to the same techniques given geometrically. But algebra
is nice too, so here we go!

Suppose four points (x_i,y_i) are given, and we expect them to be
on the sides of a square, _in this order_. Is there really such a
square? If so, how many? (I will blithely ignore degenerate configurations.)

Well, the side containing (x1,y1) lies in a line of some slope m;
then the slopes of the other lines would be -1/m, m, -1/m respectively.
We can get the equations of those lines to be (y - y_i) - m_i (x - x_i) = 0.
(So for any sequence of four points and any nonzero slope m we now have a
rectangle.) We need only check that the distance from the first point to
the third line equals the distance from the second point to the fourth line,
i.e.
   | (y1 - y3) - m (x1 - x3) | / sqrt( 1 + m^2 ) =
   | (y2 - y4) + 1/m (x2 - x4) | / sqrt( 1 + 1/m^2)
or simply
   [ (y1 - y3) - m (x1 - x3) ] = +- [ m (y2 - y4) + (x2 - x4) ]
which has two solutions
    m = ( y1 - y3 - x2 + x4 )/( x1 - x3 + y2 - y4 )
and
    m = ( y1 - y3 + x2 - x4 )/( x1 - x3 - y2 + y4 ).
(We may subsume the latter into the former by simply reversing the
orientation of the square as we number the sides.)

But this is just the slope of the line joining (x1,y1) to
Q1 = (x3,y3) + (y4-y2, x2-x4). This point is found simply by rotating
(clockwise) the vector from the second to the fourth points by a right angle,
and then adding to (x3,y3). So we have an easily-constructed point
Q1 which we then join with a line through (x1,y1) to get the first
side of the square. The rest of the square is easily constructed:
drop a perpendicular from the second point to this line, and so on
around the square.

So there is a unique and easily constructed assembly of lines passing
through the original sequence of four points, in all but the
degenerate cases. But there are six permutations of the four points
up to cyclic equivalence, giving six configurations of lines for the
original set of four points.

Well, fine then: to every set of four points we may attach six squares.
If the four points lay on a square on the first place, it would be one
of the squares we have just constructed.

But a square is not made of lines; it is made of line _segments_.
The segments have endpoints which are the intersections of consecutive
lines. The intersection P_{i,i+1} of lines i and i+1 may be computed
in terms of the x_i and y_i . (It's messy!) We may then write e.g.
(x1,y1) in the form (1-t)/2 P41 + (1+t)/2 P12 for some real t ;
the point is within the line _segment_ iff | t | < 1 . That's not too
complicated of an expression, but as it happens it is nicer simply to
state it as the fact that t^2 - 1 must be negative; after we clear
some perfect squares from the denominator, this turns out to mean that

 ( y3*y2+y4*x2-y2*x4+x2*x3 + (-x3-y4-x2+y2)*x1+(x4-x2-y2-y3)*y1 + x1^2+y1^2 )
*( y3*y4+y4*x2-y2*x4+x4*x3 + (-x3-y4-x4+y2)*x1+(x4-x2-y4-y3)*y1 + x1^2+y1^2 )

must be negative in order for (x1,y1) to be in the line _segment_,
and of course the other three constraints are similar.

The _algebraic_ fact that this is a product of quadratics has a _geometric_
interpretation: this pair of constraints says that if the other three points
are already given then (x1,y1) must lie in the lunes between two circles.
Of course the placement of (x1,y1) will affect the square fitting the
points --- each condition that one of the other three points lies in the
appropriate line _segment_ may be interpreted as saying that (x1,y1)
must lie in certain sectors between a pair of lines. As it turns out
each of these pairs of lines, as well as the two circles mentioned,
meet at the point Q1 constructed above! So it is easy to sketch the
region of feasible locations for (x1,y1).

For example, suppose we will have to construct the square when three of
the points are at (0,1), (0,0), and (2,0). If these are to be points
#2, #3, #4 in that order, then Q1 = (-1,-2) and we can search for
solvable locations for (x1,y1) by drawing various lines and circles
through Q1. But the condition that point#2 be in the interior of its
line segment requires point#1 to be somewhere in the "narrow" sectors
between the lines x = -1 and y = 3 x + 1 (which meet at Q1);
meanwhile the condition that point#3 be in the interior of its line
segment requires point#1 to be in an "even quadrant" formed by the
lines x = -1 and y = -2 (again meeting at Q1) ; so no choice of
point#1 will lead to a square.

On the other hand, if we take point#2 to be (0,0) and point#3 to be (0,1),
then by a similar analysis we may take point#1 to be anywhere in the
region in the fourth quadrant bounded by the lines y=-1 and y=(1/2)x - 1
and inside the circle (x-1)^2 + (y + 1/2)^2 = 5/4 but outside the circle
x^2 + (y + 1/2)^2 = 1/4. (All of these figures pass through Q1 = (0,-1).)
For any point (x1,y1) in this region we may construct the square,
starting with the line through Q1 and (x1,y1) as noted above.

Clearly there are some configurations of four points which cannot
possibly lie on a square (e.g. the vertices of a unit equilateral triangle
and a fourth point further than sqrt(2) units away from each of those).

dave

Relevant Pages