From: rusin@vesuvius.math.niu.edu (Dave Rusin)
Newsgroups: sci.math
Subject: Re: Cutting bricks from stones
Date: 28 Apr 1998 13:42:17 GMT

In article <01bd6d97$c7a34fe0$1c0735c6@developer2>,
Russell Harper <rharper@intouchsurvey.com> wrote:
>Is there a method to determine the largest volume brick that can be cut
>from an arbitrarily shaped stone? By a brick, I mean a six-sided shape, all
>corners equal to 90 degrees.

I'm not sure what consititutes a "method"; it probably depends on what
consititutes a "stone". 

If the surface of the stone is a differentiable surface  S  in  R^3 , then
I guess you can begin by thinking of this as a maximization problem in
calculus: you have a simple differentiable function (volume) to
maximize on  X = V x V x SO(3)  where  V  is the interior of the
surface. (Volume is determined by locations of two opposite vertices
of the brick and the orientation of the sides).  The actual domain is
the subset of  X  determined by the condition that the entire brick fit
inside  X; this would be a little tricky to determine in general, I
guess, but 
>If the stone has no concave features is the solution easier?  
in this case the domain for maximization would be the subset of X on
which each of the other 6 vertices is also inside V. Depending on the
presentation of S this may be a candidate for Lagrange multipliers.
You can save some time by noting that in the convex case, at least one
vertex on each face must be on the surface of the stone when the brick
is maximal.

Altogether different methods may be available in case  S  is a polyhedron,
and in particular when  S  is convex I imagine there are algorithms known
to the optimization people, but not to me. You could try sci.op-research.

Or: just ask you local diamond-cutter :-)

dave



From: Jeff Erickson <jeffe@cs.duke.edu>
Newsgroups: sci.math
Subject: Re: Cutting bricks from stones
Date: Tue, 28 Apr 1998 11:22:00 -0400

Dave Rusin wrote:
> 
> Russell Harper <rharper@intouchsurvey.com> wrote:
> >Is there a method to determine the largest volume brick that can be
> >cut from an arbitrarily shaped stone?
> 
> Altogether different methods may be available in case S is a
> polyhedron, and in particular when S is convex.

It's possible to find the largest AXIS-ALIGNED "brick" inside a convex
polytope with n facets in O(n) time by a nice reduction to convex
programming.  The algorithm only considers bricks whose edges are
parallel to the coordinate axes; I don't think the general case has been
solved.

@inproceedings{a-bbhdn-94
, author =      "N. Amenta"
, title =       "Bounded Boxes, {Hausdorff} Distance, and a New Proof
                 of an Interesting {Helly}-Type Theorem"
, booktitle =   "Proc. 10th Annu. ACM Sympos. Comput. Geom."
, year =        1994
, pages =       "340--347"
}

For non-convex objects, I think only the two-dimensional case has been
solved, and then only for axis-aligned boxes.  Non-convex things in 3d
are ugly!

@article{dmr-flaap-97
, author =      "K. Daniels and V. Milenkovic and D. Roth"
, title =       "Finding the largest area axis-parallel rectangle in
                 a simple polygon"
, journal =     "Comput. Geom. Theory Appl."
, volume =      7
, year =        1997
, pages =       "125--148"
, url =         "http://www.cs.bc.edu/~daniels/papers.html"
}

--
Jeff Erickson                         Center for Geometric Computing
jeffe@cs.duke.edu                     Department of Computer Science
http://www.cs.duke.edu/~jeffe                        Duke University