Newsgroups:     sci.math
From:           orourke@sophia.smith.edu (Joseph O'Rourke)
Subject:        Re: inscribed square problem
Keywords:       geometry
Organization:   Smith College, Northampton, MA, US
Date:           Thu, 11 Jun 1992 13:44:03 GMT

In article <34430@sdcc12.ucsd.edu> kwalker@canyon.ucsd.edu (Kevin Walker) writes:
>I have a dim recollection of several years ago reading the following:
> 
>"Conjecture:  For any [embedded] curve C in the plane, there exist
>points
>a, b, c, d on C such that a, b, c and d form a square."
> 
>Questions:  Is the above "conjecture" indeed merely a conjecture, or
>is it
>a theorem (or known to be false)?  If a theorem (or false), what's the
>reference?  If not a theorem, have (nontrivial) special cases been
>proved?

	It remains open after 80 years.  The best result is due to
Stromquist, who proved it for sufficiently smooth Jordan curves.
There is an excellent discussion of this problem in Klee & Wagon's
book, Old and New Unsolved Problems.

Newsgroups:     sci.math
From:           chalcraft@uk.tele.nokia.fi (Adam Chalcraft)
Subject:        Re: inscribed square problem
Organization:   cpd
Date:           Thu, 11 Jun 1992 14:52:33 GMT

In article <34430@sdcc12.ucsd.edu> kwalker@canyon.ucsd.edu (Kevin Walker) writes:

>   "Conjecture:  For any [embedded] curve C in the plane, there exist
>   points
>   a, b, c, d on C such that a, b, c and d form a square."

Vaguely related question:
A room has an uneven floor, but the skirting board is entirely horizontal.
A rectangular table has a leg at each corner.
The table will fit in the room if its top is horizontal.
Prove (or disprove) that the table will go somewhere in the room such that
[the top is horizontal and] the legs all touch the floor.
Does the answer change if the [...] clause is removed?

--
Adam.
Opinions are mine only.

Newsgroups:     sci.math
From:           bs@gauss.mitre.org (Robert D. Silverman)
Subject:        Re: inscribed square problem
Organization:   Research Computer Facility, MITRE Corporation, Bedford, MA
Date:           Thu, 11 Jun 1992 17:22:45 GMT

In article <CHALCRAFT.92Jun11165233@laurel.uk.tele.nokia.fi> chalcraft@uk.tele.nokia.fi (Adam Chalcraft) writes:
:In article <34430@sdcc12.ucsd.edu> kwalker@canyon.ucsd.edu (Kevin Walker) writes:
:
:>   "Conjecture:  For any [embedded] curve C in the plane, there exist
:>   points
:>   a, b, c, d on C such that a, b, c and d form a square."
:
:Vaguely related question:
:A room has an uneven floor, but the skirting board is entirely horizontal.
:A rectangular table has a leg at each corner.
:The table will fit in the room if its top is horizontal.
:Prove (or disprove) that the table will go somewhere in the room such that
:[the top is horizontal and] the legs all touch the floor.
:Does the answer change if the [...] clause is removed?
:
This follows almost immediately from the "Ham Sandwich" Theorem.

Another well known consequence is the fact that any suitable continuous
function defined over a closed manifold will somwhere have two points
where the function takes on the same value. i.e. there are always
at least two different points on Earth with the same temperature.
(or barometric pressure or humidity or.....).

--
Bob Silverman
These are my opinions and not MITRE's.
Mitre Corporation, Bedford, MA 01730
"You can lead a horse's ass to knowledge, but you can't make him think"

Newsgroups:     sci.math
From:           mdm@usna.navy.mil (PROF Mark Meyerson (SMA FAC))
Subject:        Re: Picnic
Organization:   U. S. Naval Academy
Date:           Wed, 27 Oct 1993 14:46:00 GMT

> In article <1993Oct25.095024.1045@dcs.warwick.ac.uk> msp@dcs.warwick.ac.uk
> (Mike Paterson) writes:

>    I would like to have a picnic on a nearby hill, which rises smoothly from 
>   a flat plane. My picnic table is square, with four legs, and I need to find 
>   a place on the hill where it will be stable with the top horizontal. 
>   Is there necessarily such a position?

> What assumptions can we make about the size of the table with respect to
> the minumum radius of curvature of the hill?  For example, if the hill is
> very pointy, and the table is pretty big, then it seems like it would be
> hard to have the legs on the ground.  Instead, the point of the hill would
> stick into the underside of the table; hardly a stable situation.

>							- Gene Stark

The "correct" assumptions are that the legs are arbitrarily long (but of the
same length), that the hill is given by a continuous non-negative function
defined inside a compact convex disk D, and that the table is to be 
placed on the hill in the sense that its center lies over D.  Then the
answer is yes there is such a position.  This is due to Roger Fenn,
"The Table Theorem", Bull London Math Soc 2 (1970), 73-76.  Discussion
of various generalizations (e.g., convexity of D is necessary, other
shape tables) can be found in my papers: Mark D. Meyerson, "Balancing
Acts", Topology Proceedings, Vol 6, 1981, 59-75, and "Convexity and the
Table Theorem", Pacific Journal of Mathematics, Vol 97, No 1, 1981, 
167-169.  Also see Kronheimer and Kronheimer, "The Tripos Problem", Jour
London Math Soc (2) 24 (1981), 182-192.  A related open problem is
whether every planar simple closed curve contains (as a subset of the
curve) the vertices of a square (see Klee & Wagon, Old and New Unsolved
Problems in Plane Geometry and Number Theory, Section 11, 1991, MAA).
                             Mark Meyerson
(P.S. Surely Fenn is well known at Warwick?)

From:           eppstein@ics.uci.edu (David Eppstein)
Date:           1 Jul 1999 11:47:12 -0700
Newsgroups:     sci.math
Subject:        Re: The Hardest Geometry Problem in the World

Bob Silverman <bobs@rsa.com> writes:
> BTW, does anyone know if any progress has been made on the following
> problem: On every Jordan curve there exists 4 points lying on the
> vertices of a square.

Last I heard it was still open, although some cases (e.g. sufficiently
smooth curves) have been solved.  I have some discussion of this on my
web site, http://www.ics.uci.edu/~eppstein/junkyard/jordan-square.html
and would be very interested in hearing about progress on this problem.

Here is a proof sketch for smooth curves.  I made it up, but I don't
expect it to be original; I haven't read previous proofs of similar results.

Consider the set of ordered pairs (x,y) of unequal points on the curve.
Topologically, the ordered pairs form a torus, but the restriction that
they be unequal turns this into an open annulus.  We can embed this
annulus geometrically as the set {(a,b): 1 < a^2+b^2 < 2} in such a way
that that swapping x and y corresponds to a 180degree rotation of the
annulus: -(a,b) = (-a,-b)

For each such pair (x,y) let point p(x,y) denote the corner clockwise
from x on a square having diagonal xy.  Classify the points of the
annulus as "in" if p(x,y) is inside the Jordan curve, "out" if p(x,y) is
outside the Jordan curve, and "on" if it is on the curve.  Obviously,
what we want to find is (a,b) for which (a,b) and -(a,b) are both
classified "on".

Then (for smooth curves) the points near one boundary of the annulus are
all classified "in", the points near the other boundary are all
classified "out", and the points classified "in" and "out" are both open
sets. Without loss of generality let's say that the "out" points are
along the outer boundary of the annulus.  Let S be the connected
component of the points classified "out" near this boundary of the
annulus, and consider the set (S union -S).  This is a connected open
set, topologically a multiple-punctured disk.  Consider the component of
its boundary that contains the origin.  Some of the boundary points are
cluster points of S (in particular, the point realizing the infimum of
absolute values of points in S is such a boundary point) and similarly
some of the boundary points are cluster points of -S.  So there must be
a boundary point (a,b) that is a cluster point of both S and -S.  Note
that (a,b) must be strictly interior to the annulus since all points
near the other boundary are "in".  Since it is a cluster point of the
"out" points, but not an "out" point itself (since it is on the boundary
of an open set) it must be an "on" point, and similarly -(a,b) is also
an "on" point, QED.

It looks like the proof generalizes a little, to curves such that, at
each point, the left and right derivatives make an obtuse angle.  But it
doesn't work for all Jordan curves; for instance the equilateral
triangle has both "in" and "out" points near both boundaries of the
annulus.  In this particular case, there are only a constant number of
misclassified points, presumably easily enough handled, but one could
imagine more monstrous examples in which the "in" and "out" points are
dense on both boundaries.
-- 
David Eppstein       UC Irvine Dept. of Information & Computer Science
eppstein@ics.uci.edu http://www.ics.uci.edu/~eppstein/

From:           "Tapio Hurme" <hurmecom@dlc.fi>
Date:           Fri, 2 Jul 1999 21:11:09 +0300
Newsgroups:     sci.math
Subject:        Re: The Hardest Geometry Problem in the World

David's poster was inspiring.

Maybe Holditch's theorem would help - this is just an idea:
"Take a smooth, closed convex curve and let a chord of constant lenght slide
around it. Choose a point on a moving chord, which divides it into two
parts, of lenghts p and q. This point will trace out a new closed curve as
the chord moves. Then, provided certain simple conditions are satisfied, the
area between the two curves will be pi*p*q." Ref: William Bender, The
Holditch's curve Tracer, Mathematics Magazine, March 1981.

Iff p=q we have used as a chord "a diameter of a circle" that has the middle
point, because p=q. Therefore the centre of the circle draws the new closed
curve inside the original closed convex curve.The area between the two
curves is now pi*p^2 = pi*q^2.

Now,  if the new closed curve has a perpendicular section (with itself) ,
i.e. a knot-point, then there is a single point for the wanted square.
Therefore - If it is possible to proof that such a point exists as a
function of p or q, then the problem is proofed (?).

Hopefully....

Tapio

David Eppstein wrote in message <7lgd3g$ci5@euclid.ics.uci.edu>...
|Bob Silverman <bobs@rsa.com> writes:
|> BTW, does anyone know if any progress has been made on the following
|> problem: On every Jordan curve there exists 4 points lying on the
|> vertices of a square.
|
|Last I heard it was still open, although some cases (e.g. sufficiently
|smooth curves) have been solved.  I have some discussion of this on my
|web site, http://www.ics.uci.edu/~eppstein/junkyard/jordan-square.html
|and would be very interested in hearing about progress on this problem.
(large snip)|

|David Eppstein       UC Irvine Dept. of Information & Computer Science
|eppstein@ics.uci.edu http://www.ics.uci.edu/~eppstein/

From:           "Tapio Hurme" <hurmecom@dlc.fi>
Date:           Sun, 4 Jul 1999 21:16:49 +0300
Newsgroups:     sci.math
Subject:        Re: The Hardest Geometry Problem in the World -part 2.

Below some additional .....

Tapio Hurme wrote in message ...
|David's poster was inspiring.
|
|Maybe Holditch's theorem would help - this is just an idea:
|"Take a smooth, closed convex curve (C-1) and let a chord of constant
length slide
|around it. Choose a point on a moving chord, which divides it into two
|parts, of lengths p and q. This point will trace out a new closed curve
(C-2) as
|the chord moves. Then, provided certain simple conditions are satisfied,
the
|area between the two curves will be pi*p*q." Ref: William Bender, The
|Holditch's curve Tracer, Mathematics Magazine, March 1981.
|
|Iff p=q we have used as a chord "a diameter of a circle" that has the
middle
|point, because p=q. Therefore the centre of the circle draws the new closed
|curve inside the original closed convex curve.The area between the two
|curves is now pi*p^2 = pi*q^2.

Well -of course the sliding chord would be the side of the wanted square,
i.e. one (or the longest side) of the wanted square is 2*p=2*q or more
simply p+q. (Note that at this point we are searching a square but not
necessarily rectangular square.) The radius of a circle (A), which goes
through the 2 edges or the corners of the wanted square with side 2*p, is
p*squareroot(2).

The centre of a circle (A) is "somewhere" perpendicular to the middle point
of the sliding chord. In other word - the sliding side of the wanted square
is tangent of the new circle (B), which touches the middle point of the
wanted square. Circle (A) and circle (B) has the same centre.

If we now let a circle (B) with radius p=q roll inside the drawn smooth,
closed convex curve (C-2) that was the result as the centre point of the
wanted square traced out, we have the third smooth, closed convex curve
(C-3) for all the centre points of the circle with radius p*squareroot(2)
because it is at the perpendicular distance of radius p from curve (C-2).
Curve (C-3) draws therefore all the centre points of circle (A) and circle
(B).
.
Certainly the circle (A) exists, if p/2 is smaller than the longest diameter
of closed curve C-1, and it touches at least two corners of the wanted
square, i.e. the ends of the sliding chord, which was a side of the wanted
square.  The circle (B) with radius p touches the middle point of the side
of the wanted square, i.e. curve (C-2) with centre on C-3.

Now if the circle (A), with the centre point on curve C-3, cuts the original
smooth, closed convex curve C-1 in 4 points we have found a square, but not
necessarily a rectangular square.
Anyway,  by choosing a certain length or p for the sliding chord, it would
be apparent that the centre of the circle (A) is found and also a kind of
square is found.

Apparently, if circle (A) with radius p*sqrt(2) rolls on the outside of the
smooth convex curve C-3, it is possible to draw a new smooth convex curve
C-4 that is at the radius distance (p*sqrt(2)) from the curve C-3. Iff now
the curves C-1 and C-4 have four common point, a square is found, but not
necessarily a rectangular square. The common points of the curves C-4 and
C-2 may help, but the proof that the solution is a rectangular square is not
so easy.

The above mentioned "story" how to find the centre of the circle (A) is not
a proof. I think it would be hopefully a method to find the proof for some p
and for some curve C-1.
The method and the proof that the wanted square is rectangular square is far
away.

At least - you may received a tip for further studies - hopefully.

Tapio

Original poster continues:
|Now,  if the new closed curve has a perpendicular section (with itself) ,
|i.e. a knot-point, then there is a single point for the wanted square.
|Therefore - If it is possible to proof that such a point exists as a
|function of p or q, then the problem is proofed (?).
|
|Hopefully....
|
|Tapio
|
|David Eppstein wrote in message <7lgd3g$ci5@euclid.ics.uci.edu>...
||Bob Silverman <bobs@rsa.com> writes:
||> BTW, does anyone know if any progress has been made on the following
||> problem: On every Jordan curve there exists 4 points lying on the
||> vertices of a square.
||
||Last I heard it was still open, although some cases (e.g. sufficiently
||smooth curves) have been solved.  I have some discussion of this on my
||web site, http://www.ics.uci.edu/~eppstein/junkyard/jordan-square.html
||and would be very interested in hearing about progress on this problem.
|(large snip)|
|
||David Eppstein       UC Irvine Dept. of Information & Computer Science
||eppstein@ics.uci.edu http://www.ics.uci.edu/~eppstein/
|
|

Date:           Mon, 22 Jan 2001 16:27:13 +0200
From:           Olexandr Ravsky <oravsky@mail.ru>
Reply-To:       Olexandr Ravsky <oravsky@mail.ru>
To:             David Eppstein <eppstein@ics.uci.edu>
Subject:        Squares on a Jordan curve

Hello David,
I found a reference of the following

Theorem. On every curve on the plane there exist 4 points lying on the
vertices of a square.

Л. Г. Шнирельман, "О некоторых геометрических свойствах замкнутых кривых
",
"Успехи математических наук", вып. Х, 1944, стр. 34 - 44.
  
( L. G. Shnirel'man, "On some gemetric properties of closed curves"
"Uspehi matematicheskih nauk", Х, 1944, pp. 34 - 44. (In Russian) )

Unfortunately, I didn't see above article and I don't know what means
the word 'curve'. But there was written that the proof is very complicated
and it may be the one which you are searching.
-- 
Best regards,
 Olexandr Ravsky                         mailto:oravsky@mail.ru

Date:           Mon, 22 Jan 2001 15:57:35 -0800
From:           David Eppstein <eppstein@ics.uci.edu>
To:             Olexandr Ravsky <oravsky@mail.ru>
Subject:        Re: Squares on a Jordan curve

On 1/22/01 4:27 PM +0200, Olexandr Ravsky wrote:
> Unfortunately, I didn't see above article and I don't know what means
> the word 'curve'. But there was written that the proof is very complicated
> and it may be the one which you are searching.

Unfortunately, it seems to require some smoothness of the curve, like the 
proofs I already knew about. Here is the review from MathScinet:

7,35c 56.0X
\v Snirel\cprime man, L. G.
On certain geometrical properties of closed curves. (Russian)
Uspehi Matem. Nauk 10, (1944). 34--44.

[An editorial note states that the paper is a reproduction of another, under 
the same title, published in Sbornik Rabot Matematiceskogo Razdela Sekcii 
Estestvennyh i Tocnyh Nauk Komakademii, Moscow, 1929, but with the earlier 
proofs somewhat amplified.] The most striking results of this paper are that 
(1) on every simple closed plane curve possessing a continuous curvature 
there may be found four points constituting the vertices of a square; (2) 
under the same hypotheses there exists on the curve a "full" system of 
rhombuses. A system $S$ of rhombuses $\{R\}$ whose vertices lie on a given 
curve $L$ is called "full" provided that (i) every point of $L$ is a vertex 
of some $R$ of $S$, (ii) each pair $R$ and $R'$ of $S$ belong to a continuous 
one-parameter family in $S$ and this family may be chosen so that an 
arbitrary vertex of $R$ passes over to a preassigned vertex in $R'$, (iii) 
none of the rhombuses is degenerate (that is, none of them is a point or 
doubly covered line-segment).

-- 
David Eppstein       UC Irvine Dept. of Information & Computer Science
eppstein@ics.uci.edu http://www.ics.uci.edu/~eppstein/

Date:           Thu, 15 Mar 2001 23:20:09 -0800
To:             eppstein@ics.uci.edu
From:           Bruce Smith <bruce@molecubotics.com>
Subject:        jordan-square.html clarification?

I can't understand one detail of your proof-sketch at the end of

  http://www.ics.uci.edu/~eppstein/junkyard/jordan-square.html

Specifically:

>Consider the set of ordered pairs (x,y) of unequal points on the curve.
>Topologically, the ordered pairs form a torus, but the restriction that
>they be unequal turns this into an open annulus.  We can embed this
>annulus geometrically as the set {(a,b): 1 < a^2+b^2 < 2} in such a way
>that that swapping x and y corresponds to a 180degree rotation of the
>annulus: -(a,b) = (-a,-b) ....

I am wondering how to embed the annulus so as to meet that condition.

It seems to me that near either annulus boundary, x is very close to y
(with one boundary having x just "before" y on the curve, and the other
boundary having x just "after" y on the curve, where we imagine the
curve as having an arbitrary "before"/"after" orientation).

Therefore, if you swap x and y for some point (a,b) near a boundary, you
must get a point near the other boundary, whereas the opposite point (-a,-b)
would be near the same boundary. Am I missing something?

- Bruce Smith
bruce@oresmus.com

Date:           Fri, 16 Mar 2001 16:04:17 -0800
From:           David Eppstein <eppstein@ics.uci.edu>
To:             Bruce Smith <bruce@molecubotics.com>
Subject:        Re: jordan-square.html clarification?

Bruce Smith <bruce@molecubotics.com> wrote (3/15/01 11:20 PM -0800):
> Am I missing something?

No, it looks like I am -- the "proof" seems to be buggy.
One reason it can't be right: if true, then (since it doesn't seem to use 
much of the square's actual geometry) it would also show e.g. that there is 
a 60-120 rhomb on any smooth Jordan curve.  But this is not true, for 
instance, when the curve is a circle.
-- 
David Eppstein       UC Irvine Dept. of Information & Computer Science
eppstein@ics.uci.edu http://www.ics.uci.edu/~eppstein/