Connection between castability and convexity

I am wondering if there are any connection between convex polygon and castable object? What can we say about castability of the object if we know that the object is convex polygon and vice versa.

Let's gather together few basic things that we have to know.

The object is castable if it can removed from the mold.

The polyhedron P can be removed from its mold by a translation in direction $$\vec{d}$$ if and only if $$\vec{d}$$ makes an angle of at least $$90^{\circ}$$ with the outward normal of all ordinary facets of P.

For a arbitrary object testing for castability has time complexity $$O(n^2)$$. In my opinion, for a convex polygon if could be improved to linear time, because for every new top facet we should test that the vector $$\vec{d}$$ makes an angle at least $$90^{\circ}$$ with outward normal not of all but only of two adjacent ordinary facets of P.

If this is true at least we have improvement in testing for castability in case of convex polygon.

We else can we state about castability and convexity. Especially interesting to know, if castability tells us something about convexity.

• I don't understand. Are you implying there are some convex shapes that are not castable? – jmad May 5 '12 at 15:19
• If the mold is made from flexible rubber, then non-convex objects can be molded. I remember making a plaster-of-paris Mickey Mouse when I was a child. He certainly wasn't convex. – Dave Clarke May 5 '12 at 15:19
• @DaveClarke: you certainly don't need flexible material to mold all non convex objects :-) – jmad May 5 '12 at 15:54
• @jmad, convexity doesn't imply castability and vice versa – com May 5 '12 at 17:08
• Please include a (reference to) a definition of "castable". – Raphael May 10 '12 at 13:53

This is a proper answer but feel free to correct me I think I did not get the right definitions. This is why I begin with simple facts that should be checked first.

I suppose your are talking about $\vec v$-castability of a "open" polyhedron.

1. Indeed it seems that no "closed" polyhedron is $\vec v$-castable.

2. For every $\vec v$, a convex "closed" polyhedron can always be cut into two "open" parts among a plane of normal $\vec v$ that are $\vec v$-castable and $(-\vec v)$-castable.

3. The test of $\vec v$-castability is in $O(n)$ (even if is not convex)

4. The problem (Is there a $\vec v$ s.t. $P$ is $\vec v$-castable?) seems to be linearly reducible to the convex hull, which is in $O(n\log n)$:

1. First consider each outward normal $\vec{n_i}$ into a point of the unit sphere.

2. Compute $H$ the convex hull of these points.

3. If the origin $0$ is in $H$ then for all $\vec v$, $P$ is not $\vec v$-castable.

4. If the origin $0$ is not in $H$ then let $\vec v$ be the vector starting at the projection of $0$ on $H$ and ending at $0$. The vector $\vec v$ defines a half-space containing none of the $\vec{n_i}$ meaning that $(\vec v, \vec{n_i})>90°$.

5. If the origin $0$ is on the surface of $H$, just take the normal of $H$ in $0$ for $\vec v$.

not in the convex hull iff there exists $\vec v$ such that

1. If $P$ is convex and "open" (whatever it means), then you only need its "frontier" and the corresponding orientation. You apply the same algorithm as above on the frontier (plus the orientation vector) reducing the complexity. For a polygon it becomes in $O(1)$ if you already know the two segments on the frontier.

Hope this helps.

• Thank you very much for the answer, could you please elaborate a little more on the 4th step. Why do we need compute every time the corresponding convex hull, I thought the convex hull remains the same, the only thing we should check is a angle between outward normal and every new $\vec{d}$, according to definition I have wrote. – com May 6 '12 at 18:16
• The idea is that the convex hull helps finding $\vec d$ (so you only need to compute it once). I edited my answer with more details. – jmad May 6 '12 at 20:44

From Moldable and Castable Polygons by Rappaport and Rosenbloom (1994). Given the vertices of the polygon in clockwise order, 2-moldability can be determined in O(n) time, 2-castability can be determined in O(n log n) time.

• Welcome, and thank you for this reference! Can you outline the basic idea the paper proposes? – Raphael Aug 10 '12 at 18:40