Connection between castability and convexity

Question

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.

Answer 1

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.

Answer 2

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.