8
$\begingroup$

Given two closed simple(no self-intersection point) curves $C_1,C_2$ in the plane $\mathbb R^2$, is there a good way to judge whether one curve can be embedded inside the other one, here embedding inside means by translation and rotation one curve can be put inside the area circled by the other one.

Ps: You could give some advice for such computation.

Thank you.

Improve this question
$\endgroup$
3
  • $\begingroup$ How are your curves given? -- Without that information, it is hard to tell what kind of answer you are looking for. $\endgroup$
    – Stefan Kohl ♦
    Commented Jul 23, 2016 at 9:59
  • $\begingroup$ Please mention whether the curves are in parametric form or in y= f(x) form, what their ranges, domains are etc., If intersection of closed ovals $ f(x,y) =0 \, \text{and} \, f( x- h, y-k) =0 $ produces imaginary roots for some $h,k$ then one of them is inside the other. $\endgroup$
    – Narasimham
    Commented Jul 23, 2016 at 18:41
  • $\begingroup$ The curves are in parameter like $(x_i(t),y_(t))$ where $i=1,2$ and $t\in [0,1]$ such that $x_i(0)=x_i(1),~y_i(0)=y_i(1)$. $\endgroup$
    – DLIN
    Commented Jul 24, 2016 at 1:28

2 Answers 2

Reset to default
6
$\begingroup$

Long ago Chazelle studied the polygonal version of your question, and obtained a polynomial-time algorithm, polynomial in the number of vertices:

Bernard Chazelle, "The polygon containment problem," in Advances in Computing Research, Vol I: Computational Geometry, (F.P. Preparata, ed.), JAI Press, Greenwich, Connecticut (1983), 1–33.

If both polygons have $n$ vertices and neither can be assumed convex, the polynomial is $O(n^7 \log n).$ If both are convex, then the complexity is reduced to $O(n^3)$. Subsequently his results have been improved in various ways. For example, the time complexity in the general case was reduced by Avnaim & Boissonnat by a factor of $n$.1 Google scholar lists more than 100 papers that cite the original.

One application is cartography: placing labels inside map regions:

            Fig.1
Fig.1(b) from Aonuma, H., Imai, H., Imai, K., & Tokuyama, T. "Maximin location of convex objects in a polygon and related dynamic Voronoi diagrams." In Proc. 6th Symposium Computational Geometry, 1990, pp. 225-234. ACM link.
1Avnaim, Francis, and Jean Daniel Boissonnat. "Polygon placement under translation and rotation." Annual Symposium on Theoretical Aspects of Computer Science. Springer Berlin Heidelberg, 1988.

Improve this answer
$\endgroup$
4
$\begingroup$

If the curves bound convex domains of the plane, there are some results in integral geometry that may be useful. For example both perimeter and area of the embedded curve must be smaller than the one of the bigger curve.

Another result is Lutwak's containment theorem, which give a necessary and sufficient condition for a convex convex set to contain a translate of another convex set.

Theorem Let $K, L$ two compact convex sets in $\mathbb{R}^n$ with non-empty interior. Then the following are equivalent.

-- there exists $v \in \mathbb{R}^n$ such that $K+v \subset L$,

-- for every simplex $D$ containing $L$, there exists $v\in \mathbb{R}^n$ such that $K+v \subset D$.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .