22
$\begingroup$

Suppose we have two sets of parametric equations $\mathbf c_1(u) = (x_1(u), y_1(u))$ and $\mathbf c_2(v) = (x_2(v), y_2(v))$ representing two 2D planar curves. When I say "2D planar curves" I mean that $\mathbf c_1(u)$ and $\mathbf c_2(u)$ are mappings from compact intervals in $\mathbb R$ to $\mathbb R^2$. We can assume (without loss of generality, I think) that $\mathbf c_1:I \to \mathbb R^2$ and $\mathbf c_2:I \to \mathbb R^2$, where $I=[0,1]$. You can assume some continuity or differentiability of $\mathbf c_1(u)$ and $\mathbf c_2(u)$, if that helps.

I'm interested to know how we can determine that these two sets of equations represent the same curve. In other words, how can I determine that $\mathbf c_1(I)$ and $\mathbf c_2(I)$ are the same point set.

An interesting special case: what if the parametric equations are all rational functions? In this case, it's often possible to implicitize -- i.e. convert to equations of the form $f_1(x,y)=0$ and $f_2(x,y)=0$. Then, if the two curves are the same point set, I would guess that something can be said about $f_1$ and $f_2$? Maybe one is a multiple of the other, or something like that??

Even simpler (but still interesting): what if all the functions involved are polynomials.

The implicitization doesn't necessarily solve the original problem, though. It's clear that $\mathbf c_1(I)$ is a subset of the zero set $Z_1 = \{(x,y) \in \mathbb R^2 : f_1(x,y) = 0\}$, but it might be a proper subset. So, even if we know how to relate $Z_1$ and $Z_2$, this might not tell us much about how $\mathbf c_1(I)$ is related to $\mathbf c_2(I)$. Can we say anything about when the implicitization approach will work and when it won't?

My question was inspired by this one.

There might be some connection with this question, but both the question and the answer are written in jargon that's not familiar to me.

This has practical applications -- curves in engineering and manufacturing are often described by using rational or polynomial parameterizations, and it would be nice if we had some way to identify when two curves are the same. In engineering & manufacturing, we only care about the shapes of curves (i.e. sets like $\mathbf c_1(I)$ and $\mathbf c_2(I)$), not their parameterization. For example, a circular wheel is still circular, regardless of how the circle curve is parameterized. The parameterization is artificial, in some sense, and I want to be able to ignore its effects when comparing two curves.

In case it matters to anyone, this isn't homework :-).

Example (for the rational case)

$$\mathbf c_1(t) = \left( \frac{1 - (2 - \sqrt2)t - (\sqrt2 - 1)t^2} {1 - (2 - \sqrt2)t + (2 - \sqrt2)t^2}, \frac{\sqrt2 t - (\sqrt2 - 1)t^2} {1 - (2 - \sqrt2)t + (2 - \sqrt2)t^2} \right)$$

$$\mathbf c_2(t) = \left( \frac{1 -t^2}{1 + t^2}, \frac{2t} {1 + t^2} \right)$$

Here $\mathbf c_1(I) = \mathbf c_2(I)$. They are both the first quadrant of the unit circle, actually.

Progress (December 2017)
Apparently, if two two implicit equations $f_1(x,y)=0$ and $f_2(x,y)=0$ represent the same curve, and $f_1$ and $f_2$ are both irreducible polynomials, then one must be a constant multiple of the other. This result is mentioned (without proof) in this paper by Sendra, so I suppose it must be well-known.

$\endgroup$
  • 3
    $\begingroup$ You used the tag algebraic-geometry and algebraic-curves, but these only apply in your special case of all the functions involved being polynomials. Are you only interested in this case? It does not seem so from your question, but i might be reading it wrong. Maybe you want to add some tags to attract attention from people from other fields? (other then the plane-curves tag, which has hardly any followers?) :) $\endgroup$ – Joachim Apr 29 '13 at 1:38
  • $\begingroup$ @Joachim -- Thanks. I thought those tags would be appropriate for both the rational and polynomial cases. I would be happy to get some answers for these special cases. The general case seems very difficult, to me, so I wasn't expecting much for that. What additional tags do you think I should use? $\endgroup$ – bubba Apr 29 '13 at 3:26
  • $\begingroup$ They were appropriate, yes! But only for your "special case". As i wrote, if this is basically your only interest, the tagging was fine, but from the question it was not clear which case you were interested in the most. As for which tags to use, i never post analytic questions so i am not the right person to tell you, i would say take a look at math.stackexchange.com/tags and go shopping :) $\endgroup$ – Joachim Apr 30 '13 at 10:58
  • $\begingroup$ As for a very partial answer, let me share an idea. I will need to specialize to the algebraic case. Let $\mathbb{A}_{\mathbb{R}}^1$ be the affine real line, and let two maps $c_1, c_2 : \mathbb{A}_{\mathbb{R}} \rightarrow \mathbb{A}_{\mathbb{R}}^2$ be given that are isomorphisms on their image. If the point set of their image is the same, one can compose one map with the inverse of another $c_2^{-1} \circ c_1$ and obtain an isomorphism of the affine line. In the algebraic case, there are very few such isomorphisms: they are always composites of a multiplication and a translation. $\endgroup$ – Joachim Apr 30 '13 at 11:05
  • 2
    $\begingroup$ As a partial answer to one of your questions, $f_1(x,y)=0$ and $f_2(x,y)=0$ can define the same set without one being a multiple of the other. For example, $xy^2=0$ and $x^2y=0$ define the same subsets of $\mathbb{R}^2$, but neither is a multiple of the other. However, the sets will be the same if the radicals of the ideals generated by $f_1$ and $f_2$ are the same. This follows from Hilbert's Nullstellensatz. $\endgroup$ – Alistair Savage May 2 '13 at 3:55
4
$\begingroup$

Consider the simpler problem of two parametrized curves $(x_i(t),y_i(t))$ that start at $(0,0)$ at time $t=0$, and equality of trajectories up to reparametrization, which is stronger than equality of point sets and a more natural condition as it is local (up to matching of starting points). Heuristically, and to some extent rigorously, there is a usable criterion.

We want that when $x_1 = x_2$, then $y_1 = y_2$ so that the bivariate function $x_1(t)-x_2(s)$ divides $y_1(t)-y_2(s)$ (and vice versa) in a suitable ring of functions. Their ratio is an invertible function with positive values, at least for nonzero $s,t$ near $0$. In fact we need it to be positive only for nonzero $(s,t)$ at which $x_1(s)=x_2(t)$ or the same for $y$.

Example: parabola and half-parabola.

Curve A is $(t,t^2)$.

Curve B is $(s^2,s^4)$.

$x_1(t)-x_2(s) = t - s^2$

$y_1(t)-y_2(s) = t^2 - s^4$

Ratio is $(t + s^2)$

This is positive near the locus where $x_1(t)=x_2(s)$ (namely $t=s^2$). On the locus where $y_1(t)=y_2(s)$ (namely $t^2=s^4$), this is positive for $t>0$ and negative for $t < 0$. The positivity condition knows which half of the parabola is curve B! That is a good sign that this is either the complete answer to the simplified problem, or on the right track.

Finding an intersection point of two parametric curves OR detecting a difference between the curves is simpler than the general problem of curve intersection. Take a point on one curve, solve for the parameter values that would place its $x$ coordinate on the other curve, and test whether the $y$ coordinates are the same. For algebraic parameterizations this calculation can be done exactly.

For the point-set equality problem, locate the zeros of the $st$ ratio. These parameter values segment the two curves into arcs. Then there is a combinatorial problem of orienting and matching (by the procedure given above) identical arcs of the two curves, and testing whether both curves are covered by the matched arcs.

$\endgroup$
  • 3
    $\begingroup$ Sorry, but I'm really interested in point sets. The applications are in engineering and manufacturing of mechanical objects, so only the shape of the curve is important; its parameterization is irrelevant. This is really the foundation of the question -- computer implementations have introduced an artificial thing (parameterization) that can make two curves look different, even though they have the same shape. I'm trying to get rid of any harmful effects of this artificial thing. $\endgroup$ – bubba May 5 '13 at 22:54
  • $\begingroup$ I understood what you are asking for, and the method I stated is the essential part of a solution of that problem that is not based on converting one parameterization into another. It handles the parameterizations implicitly without the need for any nonlinear, multivalued changes of variable, and the signs of the ratio quantity tell you how to segment the curves into arcs that can be matched to each other. The rest is deciding whether the segments cover all of both curves, which is finite combinatorial problem that should be as easy in practice as in the example. $\endgroup$ – zyx May 6 '13 at 2:57
4
$\begingroup$

Disclaimer. This answer is more like a question. Since the (+100) bounty has been raised by the same author, it will not be attached to this answer. But if someone can prove my parametrization conjecture (see below), that would be great. (Update. The bounty hasn't been awarded to anyone)

Because we are going to calculate definite integrals, it is important to have closed intervals for the parameters $t$ . For the example as presented in the question: $$ \mathbf c_1(0) = (1,0) \quad ; \quad \mathbf c_1(1) = (0,1) \\ \mathbf c_2(0) = (1,0) \quad ; \quad \mathbf c_2(1) = (0,1) $$ So we are lucky: if both parameters $t$ are allowed to be restricted to the interval $[0,1]$ then the two curves at least have the same end-points.
Consider the expression $\left[x(t)y'(t)-y(t)x'(t)\right] dt$ . It is twice the area of an infinitesimal triangle with vertices at $(0,0)$ , $(x(t),y(t))\,$ and $\,(x(t+dt),y(t+dt))$ : $$ 2 \times \mbox{area}\,\Delta = det\begin{bmatrix} x(t) & x(t+dt) \\ y(t) & y(t+dt) \end{bmatrix} = \left[x(t)\frac{y(t+dt)-y(t)}{dt} - y(t)\frac{x(t+dt)-x(t)}{dt}\right] dt $$ Now we are going to calculate the following quantities, with the end-points $\,(a,b) = (0,1)\,$ and $\,m,n\,$ positive or zero integers. Integration over an area instead of an arc length is to be preferred for some good reasons (: e.g. suppose that the curve is traversed back and forth at some places). $$ M_{m,n} = \int_a^b x(t)^m y(t)^n \left[x(t)y'(t)-y(t)x'(t)\right] dt $$ The quantities $M_{m,n}$ , not at all by coincidence, are similar to variances (in statistics terms) or moments of inertia (in physics terms). It is conjectured that the outcome of these integrals is independent of any parametrization. This may be called a Parametrization Conjecture.
It is assumed to be true in the sequel. Can someone prove or disprove?

MAPLE has been invoked to save time and effort. Definitions for the example as given in the OP's question and first few steps:

x1(t) := (1 - (2 - sqrt(2))*t - (sqrt(2) - 1)*t^2)/
         (1 - (2 - sqrt(2))*t + (2 - sqrt(2))*t^2);
y1(t) := (sqrt(2)*t - (sqrt(2) - 1)*t^2)/
         (1 - (2 - sqrt(2))*t + (2 - sqrt(2))*t^2);
x2(t) := (1-t^2)/(1+t^2); y2(t) := 2*t/(1+t^2);
x1d(t) := simplify(diff(x1(t),t)); y1d(t) := simplify(diff(y1(t),t));
x2d(t) := simplify(diff(x2(t),t)); y2d(t) := simplify(diff(y2(t),t));
M00 := int(x1(t)*y1d(t)-x1d(t)*y1(t),t=0..1);
N00 := int(x2(t)*y2d(t)-x2d(t)*y2(t),t=0..1);
verify(M00,N00,equal);
                           true
For the example at hand, the lowest order (area) moments are indeed exactly the same for the two parametrizations: $$ M_{0,0} = \frac{\pi}{2} \\ M_{1,0} = 1 \quad ; \quad M_{0,1} = 1 \\ M_{2,0} = \frac{\pi}{4} \quad ; \quad M_{1,1} = \frac{1}{2} \quad ; \quad M_{0,2} = \frac{\pi}{4} \\ M_{3,0} = \frac{2}{3} \quad ; \quad M_{2,1} = \frac{1}{3} \quad ; \quad M_{1,2} = \frac{1}{3} \quad ; \quad M_{0,3} = \frac{2}{3} \\ M_{4,0} = \frac{3\pi}{16} \quad ; \quad M_{3,1} = \frac{1}{4} \quad ; \quad M_{2,2} = \frac{\pi}{16} \quad ; \quad M_{1,3} = \frac{1}{4} \quad ; \quad M_{0,4} = \frac{3\pi}{16} \\ M_{5,0} = \frac{8}{15} \; ; \; M_{4,1} = \frac{1}{5} \; ; \; M_{3,2} = \frac{2}{15} \; ; \; M_{2,3} = \frac{2}{15} \; ; \; M_{1,4} = \frac{1}{5} \; ; \; M_{0,5} = \frac{8}{15} $$ And so on and so forth. In this way it may be confirmed, step by step, that the two parametrizations represent one and the same curve. It remains unsatisfactory that we cannot establish everything in one step, though: MAPLE could not calculate for the general expression $\,M_{m,n}$ .

$\endgroup$
  • $\begingroup$ The key, I suppose, is to identify some set of parameterization-free quantities that characterize the curve. Things like areas, arc lengths, curvatures, intrinsic equations, or the moments you suggested. And, of course, these quantities should be things that are not too difficult to compute -- this excludes intrinsic equations. The moments you suggested may or may not be enough to characterize the curve; I don't know. They are a little difficult to compute, but not too bad. Anyway, thanks very much for your attempt, and for the bounty. $\endgroup$ – bubba Sep 27 '14 at 1:53
  • $\begingroup$ @bubba: Feature extraction, if that is what you mean. That bounty didn't help much, quite unfortunately. Glad you're back in town anyway. It's better steering with good people than with reputation points. $\endgroup$ – Han de Bruijn Sep 27 '14 at 13:20
2
$\begingroup$

It would be easier for you if you have a nice set of definitions to understand your problem. So here I drop some of them hoping they will let you arrive at the correct answer. If you still have problems just ask in the comments.

By a $C^1$ path in $\Re^n$ is meant a continuously differentiable function $\gamma:[a,b] \rightarrow \Re^n$.

The $C^1$ path $\gamma:[a,b] \rightarrow \Re^n$ is said to be smooth if $\gamma' (t) \not= 0$ for all $t \in [a,b]$.

Having defined that, suppose that $\alpha:[a,b] \rightarrow \Re^n$ and $\beta:[c,d] \rightarrow \Re^n$ are two $C^1$ paths that are "geometrically equivalent" in the sense that they have the same initial point and the same terminal point, i.e., $\alpha(a)= \beta(c)$ and $\alpha(b)= \beta(d)$ respectively. Then we say that the path $\alpha:[a,b] \rightarrow \Re^n$ is equivalent to the path $\beta:[c,d] \rightarrow \Re^n$ if and only if there exists a $C^1$ function $$\psi:[a,b] \rightarrow [c,d]$$ such that $\psi([a,b])=[c,d], \alpha = \beta \circ \psi$ and $\psi'(t)> 0$ for all $t\in[a,b].$

The set $C \subseteq \Re^n$ is called a curve if and only if it is the image of a smooth path $\gamma$ which is one-to-one. And any one-to-one smooth path which is equivalent to $\gamma$ is then called a parametrization of $C$.

Finally if $\vec{x}=\gamma(t) \in C$ then $\vec{T}(\vec{x}) =\frac{\gamma'(t)}{|\gamma'(t)|}$ is a unit tangent vector to $C$ at $\vec{x}$, and $\vec{T}(\vec{x})$ is independent of the chosen parametrization $\gamma$ of $C$. Such a continuous mapping $T:C \rightarrow \Re^n$ is called an orientation for $C$. So an oriented curve is then a pair $(C,T)$ or just $C$. And $-C$ is the same geometric curve with the opposite orientation $(C,-T)$.

$\endgroup$
  • 1
    $\begingroup$ I'm only interested in the case $n=2$. I think I did explain what I mean by "geometrically equivalent" -- it means that the two sets $\mathbf c_1(I)$ and $\mathbf c_2(I)$ are the same. I don't really want to assume that $c_1$ and $c_2$ are injective maps -- curves can intersect themselves in my world. I don't really see how orientation is relevant. I added some definitions to the question. Hope that helps. $\endgroup$ – bubba May 5 '13 at 1:59
  • 2
    $\begingroup$ > different functions can trace the same curve in different forms, for example with different orientations or velocities -- yes, of course. That's the reason for the question. $\endgroup$ – bubba May 5 '13 at 6:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.