From: eppstein@euclid.ics.uci.edu (David Eppstein) Subject: Re: The Hardest Geometry Problem in the World Date: 1 Jul 1999 11:47:12 -0700 Newsgroups: sci.math Keywords: Does every curve contain the vertices of some square? Bob Silverman 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/ ============================================================================== [Presumably a reference to this paper: --djr] 91g:52003 52A20 Stromquist, Walter Inscribed squares and square-like quadrilaterals in closed curves. Mathematika 36 (1989), no. 2, 187--197 (1990). Let $\omega $ be a closed curve in $\bold R\sp n$. The author proves that under suitable conditions $\omega $ admits an inscribed quadrilateral which has equal sides and equal diagonals. In the case of plane curves, this proves that $\omega $ admits an inscribed square. The result cited above is true for smooth curves and those which satisfy "Condition A"---where each point $\omega (y)$ of the curve has a neighborhood $U(y)$ in $\bold R\sp n$ such that no two chords in $U(y)$ are perpendicular; this is true for $C\sp 2$ curves. In the plane the author is able to use an even weaker hypothesis---"local monotone"---where no chord in the neighborhood $U(y)$ of $\omega (y)$ has a chord parallel to a fixed direction $n(y)$. This result strengthens the famous theorem of L. G. Shnirelman [Uspekhi Mat. Nauk 10 (1944), 34--44; MR 7, 35] and H. W. Guggenheimer [Israel J. Math. 3 (1965), 104--112; MR 32 #6326] for $C\sp 2$ plane curves. Reviewed by G. T. Sallee © Copyright American Mathematical Society 2000