Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

This is a followup to Bill Thurston's question about different notions of hulls. Here I want to raise a question about the reflex-free hull, which is, intuitively, the smallest enclosing shape to an object that cannot hold water in any orientation. Let $S$ be a closed solid object in $\mathbb{R}^3$, and $\partial S$ its surface. Let $H$ be a closed hemispherical neighborhood, a ball intersected with a closed halfspace through its center. Define a reflex point $p$ on $\partial S$ to be one such that it has a neighborhood $H$ such that (a) $H \subset S$ and (b) $H \cap \partial S = p$. An object is reflex-free if it has no reflex points. Intuitively, a reflex point could hold a drop of water in its exterior neighborhood in some orientation. For example, this shape is reflex-free:


alt text

The reflex-free hull of an object $O$ is the intersection of all reflex-free shapes that enclose $O$. This notion was introduced in the interesting paper cited below. It has application to manufacturing by molten-metal casting, and applications to architecture.They established a number of properties of the reflex-free hull, but could not find an algorithm to construct it.

Q1. Provide a finite algorithm to construct the reflex-free hull for a polyhedron.

They identified a number of difficulties that various ideas for algorithms would encounter. An algorithm that fills in cavities naively, approaches, but never reaches, the reflex-free hull of this example (their Fig. 7):
alt text

Q2. Is the reflex-free hull the same as Thurston's "knife hull"? (Answered by Bill Thurston below: No.)

Reference. Hee-kap Ahn, Siu-Wing Cheng, Otfried Cheong, Jack Snoeyink. "The Reflex-Free Hull." In Proc. 13th Canadian Conference on Computational Geometry, 2001, and in International Journal of Computational Geometry and Applications, 14(6):453-474, 2004.

  • [CiteSeer][4].
  • [ps for preliminary 4-page abstract][5].

(See comments for links, which are not working here for some reason...)

share|improve this question
    
@jc: Yes, $\partial S$ is a closed surface, and $S$ is the solid whose boundary is $\partial S$. Links [4] & [5] are in what I posted, but for some reason they do not show up. If anyone knows how to fix that, please edit. Meanwhile, here they are again: citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.21.259 cccg.ca/proceedings/2001/snoeyink-68900.ps.gz –  Joseph O'Rourke Sep 20 '10 at 14:54
add comment

1 Answer

If I understand correctly, reflex-free is equivalent to the property that the orthogonal projection to any line has no inside local minimum, that is, there is no point where the function is a local minimum on the boundary but not in the solid. For a smooth surface, this means both principle directions can't be curving in the concave sense.

Consider any graph embedded in a ball, mostly trivalent but with some vertices of order 1 attached to faces of a ball, embedded in a way that each interior vertex is in the convex hull of its neighbors. Not all graphs admit such an embedding, but many do; examples can be constructed, using for example harmonic maps. For such a graph, you can hollow out of the ball a narrow tubular neighborhood whose complement is reflex-free These give examples where the knife-hull is different from the reflex-hull --- just for a $Y$ graph, the knife hull could be convex.

Here's an alternative characterization of reflexes (a reflexive definition?): a point $p$ is in a reflex for $S$ if there is a plane $P$ through $p$ and a region $R$ on the plane containing $p$ in its interior, such that the boundary of $R$ is contained in $\partial S$ and is null-homologous on $ \partial S$ (bounds a region on $\partial S$). This is equivalent to the definition using the special case of half-balls, because if the shape is turned so that the plane is horizontal and the surface on $\partial S$ is below, we can look at a point where the height function has a local minimum. If it's not a strict local minimum, turn by a slight random angle to make a strict minimum, in which case we can find a half-ball.

I wonder whether a variation of minimal surfaces would give a reasonable procedure to find the reflex-free hull. For a minimal surface, the two principal curvatures balance---you can think of it like rubber bands in perpendicular directions in a tug of war, trying to pull surface in opposite directions but coming to a draw. Now imagine a surface whose molecules align to pull very hard in the convex directions, and only weakly in the concave directions. To those who have ... if you take the limit of inward-pulled surfaces, as insiders grow stronger and outsiders weaker, seems like a candidate reflex-free hull.

Minimal surfaces can be difficult to analyze because there are often local minima that are not global minima, and unstable critical points of the area function as well. However, with inward-pulled surfaces, I have trouble thinking of examples where such a phenomena occurs. If there is only one local minimum, then computation might be relatively efficient.

share|improve this answer
    
@Bill: I love your idea for "inward-pulled surfaces"! This seems a quite promising new approach. Thanks for replying! –  Joseph O'Rourke Sep 20 '10 at 16:57
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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