an interesting geometry problem

[Amadeus W. M.]

In my research I ran into this problem, and although it's not exactly
recreational, it has a very elementary formulation, so maybe I can get
some ideas in this group. If there's a better suited group, I'd appreciate
it if someone pointed me to it.

Suppose \gamma is a (simple closed) curve in the plane. We are allowed
to deform \gamma only by similarity transforms (rotation, translation and
scale).

Let now v_1,...v_n be segments in the plane.

I would like to "fit" \gamma to the v_i's in some reasonable way. That is,
find the similarity transform T such that T(\gamma) is as tangent as
possible to all of the v_i's (at some point on the v_i).

If it helps, one can use e.g. rigid transformations (rotation and
translation) instead of similarity, or perhaps affine.

As you can see, the problem is not even very well formulated, but maybe
can help make sense of it.

Thanks!

[h.t...@gmail.com]

Generically, and with lines instead of line segments, the answer
"should" be that you can fit it to four of them and no more--similarity
transformations allow you four degrees of freedom, and each tangency
imposes one restriction. If five is possible, then it's a specially
cooked-up example.

I said the answer "should" be four, but it's easy to see that's not the
case with a circle--a circle can always be made tangent to any three
lines as long as they aren't all three parallel and don't meet in a
single point, and that circle is unique--meaning any fourth line you
add that's still tangent would be very special. (It's not to hard to
write down an equation for the fourth lines that would be permitted.)
So why is it three and not four with a circle? Well, rotating a circle
does nothing at all--so there are really only three degrees of freedom
of similarity transformations.

So what if gamma is roughly round but not a perfect circle? In that
case, to the first three lines you could add any line that was
sufficiently close to touching the unique circle: rotating your
almost-circle and fitting it to the three lines, it will move in and
out from where the fourth line almost touches the circle, and if it
varies enough to go both inside and outside the fourth line, then for
some degree of rotation it will exactly touch it. So the less like
a circle gamma is, the more likely it is that it can fit any given four
lines.

I hope this helps. I had to solve a related question at one step of my
dissertation, which I now pose as a puzzle: Given a differentiable
curve which is the boundary of a convex region with point symmetry
(that is, rotating by 180 degrees doesn't change the region), and
allowing not just similarity transformations but all affine
transformations (so you can also skew any amount along any angle,
giving a total of six degrees of freedom), show that it is possible to
make the curve tangent to the four center points of the edges of a
square.

(I had a really nifty proof with a pair of curves constructed outside
the region which enclose the same area and therefore must cross--but
then I discovered a simpler non-constructive proof which works in all
dimensions, not just two, and the nifty proof went by the wayside.)

[Amadeus W. M.]

On Fri, 09 Dec 2005 22:46:44 -0800, h.tracy wrote:

> Generically, and with lines instead of line segments, the answer
> "should" be that you can fit it to four of them and no more--similarity
> transformations allow you four degrees of freedom, and each tangency
> imposes one restriction. If five is possible, then it's a specially
> cooked-up example.
>
> I said the answer "should" be four, but it's easy to see that's not the
> case with a circle--a circle can always be made tangent to any three
> lines as long as they aren't all three parallel and don't meet in a
> single point, and that circle is unique--meaning any fourth line you add
> that's still tangent would be very special. (It's not to hard to write
> down an equation for the fourth lines that would be permitted.) So why
> is it three and not four with a circle? Well, rotating a circle does
> nothing at all--so there are really only three degrees of freedom of
> similarity transformations.
>
> So what if gamma is roughly round but not a perfect circle? In that
> case, to the first three lines you could add any line that was
> sufficiently close to touching the unique circle: rotating your
> almost-circle and fitting it to the three lines, it will move in and out
> from where the fourth line almost touches the circle, and if it varies
> enough to go both inside and outside the fourth line, then for some
> degree of rotation it will exactly touch it. So the less like a
> circle gamma is, the more likely it is that it can fit any given four
> lines.
>
>

Thanks for the reply. It can't be lines, it has to be segments, and the
transformed curve must be tangent to those segments at some point on the
segments. I have the freedom to require that the curve be tangent to
the segments at the midpoints. The number of segments is n=O(10). I don't
expect a precise fit (i.e. I won't be able to make the curve touch all the
segments at precisely 1 point), but rather a "best" fit. Of course, the
problem is to define "best".

Maybe I should re-formulate the problem, avoiding any reference to lines
or segments. There are n points p1,...pn in the plane, and directions
theta_1,... theta_n. Ideally, I'd like to find a transform which makes
gamma go through all points p_i, and the tangents to gamma at those points
agree with the given directions theta_i. This is not possible (in
general), so find the "best" fit transform.

[h.t...@gmail.com]

Here's one approach that at least would make your optimization problem
well-defined, and reduce it to a classical (if notoriously
time-consuming) problem.

First of all, parametrize the curve with a pair of periodic functions
p(t), q(t). Ideally, p and q are polynomials in cos(t) and sin(t).
(They always will be at least approximately--but finding a good fit is
a whole other problem.) The ratio of the derivatives p'(t) and q'(t)
then gives the slope at any point; if these derivatives are never
simultaneously zero then the curve is smooth.

Secondly, define a fitness metric d_i for each target line segment and
given point (x(t_i), y(t_i)) and tangent (x'(t_i), y'(t_i)). The value
of d_i should be zero if (x,y) is the midpoint of the segment and the
tangent has the same slope, and positive in all other cases. Each
metric should be an algebraic function of x, y, x', and y', typically
involving a sum of squares with separate position and tangency terms.

The simplest position term would be (x-x_i)^2 + (y-y_i)^2, but you also
have the freedom to measure distances differently in the directions
parallel and perpendicular to the line segment. For example, it would
give the curve more freedom to slide along longer line segments if you
used (the left side of) the equation of an ellipse, one of whose axes
is the line segment itself, with the other axis a perpendicular
bisector of specified length (say 1).

The tangency term ought to be invariant under simultaneous rotation of
the line segment and tangent line (everything else about the problem is
invariant in this way). It also should depend only on the ratio of y'
to x', unless it also matters how "fast" the curve is as it approaches
the line segment. For example, you could use (we'll call this option
1):

(x'*y'_i - y'*x'_i)^2/(x'^2 + y'^2)/(x'_i^2 + y'_i^2),

which gives a "distance" of 0 for parallel lines and of 1 for
perpendicular lines. The non-constant denominator in this term
complicates later calculations, and there is some rationale for
dropping the normalization terms and using (option 2, now):

(x'*y'_i - y'*x'_i)^2

alone, since in some sense the "faster" the curve is, the more "wrong"
a wrong tangent is, and the longer the line segment, the more
particular we are that the curve be aligned with it. Dropping the
normalization (or anyway the non-constant part of it) does mean that
the optimum now depends on the "speed" of the parametrization at
various points, which wasn't the case previously.

Naturally all the various components of all the various fitness metrics
can be made more or less important by weighting them appropriately.

Once you've made all these choices, the optimization problem is well
defined. The set of similarity transformations of the curve is given
by the linear equations

x(t) = a*p(t) + b*q(t) + x_0,
y(t) = -b*p(t) + a*q(t) + y_0,

from which we see the four degrees of freedom. (If we allowed all
affine transformations, the coefficients -b and a in the second
equation would be replaced by two new variables and degrees of
freedom.)

If there are n line segments, then for n different freely varying
parameters t_i we can consider cos(t_i) and sin(t_i) as a pair of
separate parameters c_i and s_i satisfying the constraint

c_i^2 + s_i^2 = 1.

The sum of the errors d_i is now a rational function (or polynomial, if
we've chosen option 2) of the 2*n+4 variables {a, b, x_0, y_0, c_1,
s_1, . . ., c_n, s_n} with n constraints. The optimum position, size,
and orientation for the curve, together with the n points of near
tangency, can be found by minimizing the function subject to the
constraints. Using Lagrangian multipliers, this reduces to finding the
finite (but potentially huge) set of solutions to 3*n+4 polynomial
equations in 3*n+4 unknowns, and then plugging each solution in to the
error function to find the global minimizer.

Hope this helps. It's an interesting problem.

--Tracy