From: rusin@vesuvius.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Re: Least convex set containing a curve (in R^3) Date: 14 Oct 1997 07:14:30 GMT In article <3435CCEF.4B73@tin.it>, Andrea Spallanzani wrote: >Let's take a continuous closed curve C of R^3. Let V be the volume of >the >least convex set of R^3 containing C. The ratio r=V/length(C)^3 depends >on >the shape of C: i'm searching the C that maximizes r. >For istance, the following C > >x=cos(t) >y=sin(t) >z=1.05 sin(t)^2 >for 0 >has a ratio r=0.003527. Can you find better r? TIA. Well, you could take a curve joining the four vertices of a tetrahedron. Already the tetrahedron joining the origin O to the three unit basis vectors e_i in R^3 has volume 1/6; the path from e1 to O to e2 to e3 has length 2+sqrt(2), giving r=.004188. If I've done the arithmetic right, a regular tetrahedron similarly gives r=sqrt(2)/324=.00486 Naturally if that convex set is polyhedral, say the convex hull of points p1, p2, ..., p_n, then in order to be optimal, C will have to be piecewise-linear (with the p_i as the endpoints), passing through each p_i precisely once. Just offhand, I'd guess that a regular tetrahedron gives the best result among all polyhedra, at least. (Of course, you realize I'm only making a conjecture so that someone else will respond right away with a counterexample. :-) ) dave ============================================================================== From: spalland@comune.re.it (Andrea Spallanzani) Newsgroups: sci.math Subject: Re: Least convex set containing a curve (in R^3) Date: Thu, 16 Oct 1997 11:27:36 GMT Hi Dave, thank you for your interest >>Let's take a continuous closed curve C of R^3. Let V be the volume of >>the least convex set of R^3 containing C. The ratio r=V/length(C)^3 depends >>on the shape of C: i'm searching the C that maximizes r. > >Well, you could take a curve joining the four vertices of a tetrahedron. >Already the tetrahedron joining the origin O to the three unit basis >vectors e_i in R^3 has volume 1/6; the path from e1 to O to >e2 to e3 has length 2+sqrt(2), giving r=.004188. Actually, this path isn't *closed*. If you close it coming back to e1, r becomes .00148. The best path I found is x=cos(t) y=sin(t)*sqrt(2/abs(sin(t))-1) if t<>0,pi; else y=0 z=0.93abs(sin(t)) for t=0..2*pi with ratio=0.00375 Best regards Andrea Spallanzani ============================================================================== From: spalland@comune.re.it (Andrea Spallanzani) Newsgroups: sci.math Subject: Re: Least convex set containing a curve (in R^3) Date: Thu, 16 Oct 1997 19:33:19 GMT Hi Dave, >Just offhand, I'd guess that a regular tetrahedron gives the best >result among all polyhedra, at least. The best tetrahedron isn't the regular one. To get the best tetrahedron (with a ratio of .00200), take a rhombus with a diagonal = 2/sqrt(3)*side and fold it orthogonally along that diagonal. Best regards ============================================================================== From: rusin@vesuvius.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: That Calculus of Variation problem (LONG!) (Was: Re: Least convex set containing a curve (in R^3)) Date: 21 Oct 1997 06:27:31 GMT Andrea Spallanzani wrote: >Let's take a continuous closed curve C of R^3. Let V be the volume of >the least convex set of R^3 containing C. The ratio r=V/length(C)^3 depends >on the shape of C: i'm searching the C that maximizes r. >The best path I found is > >x=cos(t) >y=sin(t)*sqrt(2/abs(sin(t))-1) if t<>0,pi; else y=0 >z=0.93abs(sin(t)) >for t=0..2*pi > >with ratio=0.00375 I have a good but perhaps not yet a definitive answer to this question. I'll summarize in this post what I've found. It has grown rather long so I've broken it down into sections: I. Comments about the initial poster's proposed solutions. II. Comments about general convex hulls (I'm stumped!) III. Restriction to family of symmetric curves IV. Optimal piecewise-linear curves (got 'em!) V. Optimal smooth curve (got it! -- ratio .003796537196) VI. Bird's-eye view of Calculus of Variations. I. COMMENTS ABOUT THE INITIAL POSTER'S PROPOSED SOLUTIONS. Your estimate of the ratio in your curve seems a bit high. I get a volume of about 2.160389 and a length of 8.363218 for it, for a ratio of .00369327. (All are numerical estimates of course.) I can only assume the coefficient 0.93 was obtained by trial and error. However, I got better results changing that same coefficient to 1.16 (giving volume 2.694678, length 8.921100, ratio .00379534.) Observe that the ratio changes very little even though the shape of the curve has changed rather a lot; the objective function seems to have a rather broad peak. Your curve may be written as the intersection of two elliptical cylinders with perpendicular axes: x^2+(z/0.93)^2=1 and y^2+(z-1)^2=1. However, for curves of this general type (see section III) one must have greater symmetry. You might more appropriately try intersecting, say, x^2+(m z)^2=1 with y^2 + (m z + b)^2 = 1 for various m and b. II. COMMENTS ABOUT GENERAL CONVEX HULLS A major difficulty for me is to determine the volume of the convex hull of a spatial curve. Indeed, it's not immediately clear how even to _describe_ that convex hull at all! For example, if you grasp a pair of opposite points on a circle with two hands, and then give each a 45-degree twist in opposite directions, you'll have a nicely twisted curve; what's its convex hull? (See section IV.) I suppse I can compute its volume without viewing it: if H is the convex hull of a curve f:[0,1] -> R^3, then H is the image of the map F:[0,1]^3 -> R^3 given by F(x,y,z)=zf(x)+(1-z)f(y), so we can compute vol(H) = Integral_H 1 = Integral_[0,1]^3 |det(F')|; in this last step, however, I'm assuming F is essentially 1-to-1 on [0,1]^3, a premise which seems unclear. One feature of this integral is that it yields a high volume to curves which keep |det(F')| large. This determinant is essentially the so-called "triple product" f'(x) x f'(y) . (f(x)-f(y)). If the curve has been parameterized by arc-length, so that || f'(t) || = 1 for all t, then det(F') will, loosely speaking, be large if the tangent vectors of far-apart points are nearly perpendicular to each other. See section IV below. I would be delighted to hear of a Green's-Theorem-like result for computing volumes associated to spatial curves. III. RESTRICTION TO FAMILY OF SYMMETRIC CURVES The poster's suggested curves are part of a family of curves for which I _do_ know how to proceed with optimization: those which are symmetric respect to both the x-z and y-z planes, and which have z monotonic in the first quadrant. I can comment about both smooth and piecewise-linear curves in this case. The principal observation is that if the z axis is partitioned, the convex hull becomes the union of contiguous horizontal slabs; the top and bottom of each slab certainly include (and for good curves are _equal to_) rectangles joining the four points ( +- x, +- y, z) on the curve. Thus the volume (or in the general case a lower bound for the volume) of the convex hull is given by integrating Integral 4 x(z)*y(z) dz along the z axis; if the curve is parameterized, this may of course be written Integral 4 x(t)*y(t)*z'(t) dt. For piece-wise linear curves, one may simply add the volumes of the slabs. (The volume of each slab is (2/3)| 2*x2*y2 + 2*x1*y1 + x2*y1 + x1*y2 | * | z2-z1 |.) Of course the length of the curve is Integral Sqrt(1+x'^2+y'^2) dz. In what follows I will try to maximize these volume integrals subject to keeping the length equal to 1. Observe that this may in fact _fail_ to find the curve in this family which is truly optimal in the sense of the original question. For a sufficiently twisted curve, the portion of the convex hull within any of the horizontal slabs may be _greater_ than the volume of the rectangular-faced slabs listed above, a typical example being a coil whrapped around an hourglass. I suspect that these curves have too great a length to improve the volume/length^3 ratios we discuss below, but I certainly have no proof. Consider this an optimization problem with a restricted class of curves and a restricted notion of volume! Alternatively, one may state the our optima are indeed those of optimal volume but among an even smaller class of functions -- those with x(t) and y(t) also monotone on [0,1/4], with convex image in the x-y plane. IV. OPTIMAL PIECEWISE-LINEAR CURVES It is possible to compute the optimum piece-wise linear curves in this family. With a designated number N of segments of the curve to be in the first quadrant, begin with any curve of length 1/4 rising from some (x0, 0, -z0) to some (0, y0, z0) through N-1 equidistant points in the first quadrant. (For example, a tilted quarter-circle is fine.) Then improve the curve as follows: for each vertex not in the coordinate planes, consider spinning that vertex while leaving the rest of the curve fixed; the vertex is constrained to lie in a small circle. For each angle theta of movement around the circle, we can compute the volume of the union of the two adjoining slabs; choose theta to maximize this sum (subject to keeping the z-coordinate between those of the adjacent vertices). This requires solving a pair of quadratic polynomials to determine cos(theta) and sin(theta), so it's easy to go directly to the optimal theta. In particular, the volume of the new convex hull cannot be less than the previous volume, and the length of the curve is unchanged; we have improved the objective ratio. Repeat for all vertices. A similar but slightly different calculation is applied to the endpoints, where z is not constrained. Repeat ad infinitum to discover better and better curves. It's simply assumed here that there is a unique optimal curve, but I believe I can show that the curves are converging towards a local optimum curve (once the algorithm is corrected to forestall the possibility of drift along the z axis.) Convergence is fairly smooth at first, but I found it took very many iterations of this procedure to get better than about 95% of the maximal ratio. The optimal curve above may be described as racing quickly from the coordinate planes to points ([ +- .097, +-.097, 0]) where the slopes are about +- 1. In particular, these points furthest apart have tangent vectors which are roughly perpendicular to each other, consistent with the observation in section II and, in fact, providing a possible model for the hand-twisting of the circle there. The PL-curves I obtained have vertices whose coordinates agree to a few signifcant digits with those of the optimal smooth curve (see section V). (But note that the true optimal PL-vertices are _not_ expected to lie exactly on the optimal smooth curve.) Certainly the coordinates listed below form a good starting configuration for the optimal PL curve on 2^n vertices (for n=2, 3, ..., 7). V. OPTIMAL SMOOTH CURVES Now let us consider the problem of computing the optimal smooth curve of the type described in section III (x- and y- symmetry, z increasing). If we parameterize the curve by arclength, then x'(t)^2 + y'(t)^2 + z'(t)^2 is identically 1, and so the volume may be written as the integral Int_[0, 1/4] 4 x(t) y(t) sqrt(1 - x'(t)^2 - y'(t)^2) dt Our goal is simply to select functions x(t) and y(t) so that this is as large as possible. We need only meet the boundary conditions y(0)=x(1/4)=0 so that the curve meets both coordinate planes; differentiability of the curve at those points requires x'(0)=y'(1/4)=0. (We will also want x'(t)^2+y'(t)^2 <=1 so that z(t) may be computed as an antiderivative of sqrt(1-x'(t)^2-y'(t)^2) ; the area itself can be computed too by then solving A'(t)= x(t)*y(t)*z'(t) for A. ) So how does one select functions which maximize an expression such as Int_[0,1/4] H( x(t), y(t), x'(t), y'(t) ) dt for a function H of four variables (in this case H(T,U,V,W) = T*U*sqrt(1-V^2-W^2). ) ? The answer is through the Calculus of Variations. The short statement is that for any function y, if x is chosen to maximize such an integral, then dH/dT (x,y,x',y') = d/dt (dH/dV) (x,y,x'y'); likewise if y is optimal, we have dH/dU = d ( dH/dW ) / dt. This gives us two differential equations that x(t) and y(t) must satisfy. (See section VI for derivation.) Thus we see we have an optimal pair only when dH/dT (x,y,x',y') = d [(dH/dV) (x,y,x'y')] / dt and dH/dU (x,y,x',y') = d [(dH/dW) (x,y,x'y')] / dt . In our case H(T,U,V,W) = 4*T*U*sqrt(1 - V^2 - W^2). This will describe the optimal pair (x,y) as a solution to a pair of 2nd order ODEs. This pair of equations is remarkable in that it appears quite complicated, but it involves x''(t) and y''(t) _linearly_, permitting us to solve for them; to our great relief, the solution is quite simple: x''(t) = (-1+x'(t)^2+y'(t)^2) / x(t) y''(t) = (-1+x'(t)^2+y'(t)^2) / y(t) Equivalently, x(t) x''(t) = y(t) y''(t) = -1+x'(t)^2+y'(t)^2 [=-z'(t)^2 !] Given two 2nd-order differential equations and four boundary conditions, we expect a unique solution. Unfortunately, this is certainly _not_ the case here, since either x or y may be replaced by its negative and another solution results; in particular, there is not a unique solution starting at a point on the coordinate axes. However, the equations _are_ regular if we start somewhere on the line y=x. We thus expect we can find a unique optimal curve in the first quadrant of the plane. As far as I can see there is no closed-form solution, but we can solve the equations numerically. I ran this with Maple's "dsolve" command, taking as initial conditions sets of the form {x(0.125)=P0, y(.125)=P0, D(y)(.125)=P1, D(y)(.125)=-P1}; and then asking it to project solutions back to t=0, where I wanted y(0)=D(x)(0)=0. A simple feedback loop let me correct the P0 and P1 each time, until with P0=.9721756237111 and P1=.394594356718 I had values for y(0) and x'(0) which were within 10^-11 of zero. (In this way I deduced x(0)=.1111961005756 and as a check found y'(0)=1, as expected.) Here are 16 of the points, equally spaced by arclength, with (x,y) in the first half-quadrant; simple reflections give 128 points equally spaced along the full curve: [.1111961005, .0000000000, -.0646142154] [.1111958346, .0078049273, -.0643164187] [.1111918561, .0155644715, -.0634247746] [.1111746969, .0232335222, -.0619445939] [.1111288265, .0307675375, -.0598849670] [.1110330283, .0381228858, -.0572590964] [.1108609308, .0452572503, -.0540847157] [.1105816931, .0521301076, -.0503845480] [.1101608413, .0587032842, -.0461867515] [.1095612451, .0649415848, -.0415252923] [.1087442147, .0708134755, -.0364401870] [.1076706902, .0762917949, -.0309775592] [.1063024830, .0813544566, -.0251894672] [.1046035226, .0859850986, -.0191334745] [.1025410541, .0901736306, -.0128719550] [.1000867329, .0939166330, -.0064711479] [.0972175623, .0972175623, .0000000000] The computed volume is .003796537196 and by construction the length is 1. I have not ruled out the possibility that other optimal solutions exist, although it appears the only variant solutions to the differential equations result from sign changes, and of course the choice of additive constant in the integration of z(t). So I believe the only optimal curve in the family of section III is, up to similarity, the one described above. VI. BIRD'S-EYE VIEW OF CALCULUS OF VARIATIONS. I had to review my C-o-V to do this problem, so in case anyone else was rusty: /* Handwaving lecture mode on */ I believe it's worth taking a moment to see where these equations (the Euler equations) come from. If we wish to choose a function x to maximize an integral J(x) = Int_I H(x(t), x'(t)) dt (with a fixed function H(T,V) of two variables) on a fixed interval I, we do so by characterizing the optimal functions. If k(t) is any other function and e any small number, then if x(t) is optimal, the value of J(x+e*k) will be smaller than J(x). On the other hand, J(x+ek) may be viewed as a function of e and "so" has a Taylor series; it can only have a maximum at e=0 if the linear term is zero. We may compute that linear term by expanding the integrand. Clearly H(x+e*k, x'+e*k') = H(x,x') + e*( k * dH/dT (x,x') + k' * dH/dV (x, x') )... accounts for the linear terms in e; thus J has been increased by roughly e times Int_I k * dH/dT (x,x') + k' * dH/dV (x, x') dt. This then is the quantity which must (for optimal x ) be zero, for all k. The second summand in the integral is, by integration by parts, k * dH/dV(x,x') - Int_I k * d/dt ( dH/dV ) dt Thus the vanishing of the linear term is equivalent to k * dH/dV = Int_I k * [ dH/dT - d/dt ( dH/dV) ] for all functions k, and in particular, 0 = Int_I k * [ dH/dT - d/dt ( dH/dV) ] for all k which vanish at both endpoints of the interval; if dH/dV itself vanishes at the endpoints, then this last equality holds for all functions k. (This applies to our H ). Now, the only continous function F with Int_I k*F = 0 for all functions k is the zero function (Proof: try k=F !) so we conclude that dH/dT = d/dt ( dH/dV ) as functions of t when evaluated at T=x(t) and V=x'(t) for an optimal function x. Doing the same now for both functions x and y, we see we have an optimal pair only when dH/dT (x,y,x',y') = d [(dH/dV) (x,y,x'y')] / dt and dH/dU (x,y,x',y') = d [(dH/dW) (x,y,x'y')] / dt . /* Handwaving lecture mode off */ OK, that's enough for me. dave ============================================================================== From: rusin@vesuvius.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Re: That Calculus of Variation problem (LONG!) (Was: Re: Least convex set containing a curve (in R^3)) Date: 23 Oct 1997 14:54:22 GMT Andrea Spallanzani wrote: >Let's take a continuous closed curve C of R^3. Let V be the volume of >the least convex set of R^3 containing C. The ratio r=V/length(C)^3 depends >on the shape of C: i'm searching the C that maximizes r. It turns out this problem has a little history. Here's what I found with a little sleuthing through Math Reviews (I haven't checked any of the original articles). Bonnesen (*) apparently asked this question too; some partial results have been found: E. Egervary (Publ Math Debrecen 1 (1949) 65-70) gave a nice solution for curves which need not be closed (the best curves are helical arcs), but this assumes the best curves are "convex" in the sense that every plane meets the curve in at most three points. I.J. Schoenberg (Acta Arith 91 (1954) 143-164) solved the corresponding problem for closed curves in _even_ dimensional Euclidean spaces, again under this "convexity" assumptions (replace "three" with the dimension of the space). The curves may be viewed as a map from the unit circle (in the complex plane) to complex n-space C^n; the optimal curve is f(z) = (z, z^2/2, z^3/3, ..., z^n/n) Z.A. Melzak (Proc Amer Math Soc 11 (1960) 265-274) considered precisely the problem I did, made the same restrictive assumptions, and deduced the same answer. (To think I could have published!) V.A. Zalgaller (Algebra i Analiz 8 (1996) 1-13) surveys this and seven related geometric problems. Evidently in no case are complete solutions known. (Evidently this journal will be translated as: St. Petersburg Math J 8 (1997); no citation yet to such a translation.) If you are interested in results of this type, you may need to bone up on differential geometry and global optimization, if your interest is in smooth curves. There is a branch of geometry ("convex geometry") which is not so aggressively analytic and is perhaps a bit more geometric. See e.g. the book by Rolf Schneider, Convex bodies: the Brunn-Minkowski theory. Encyclopedia of Mathematics and its Applications, 44. Cambridge University Press, Cambridge, 1993. xiv+490 pp. ISBN 0-521-35220-7 In summary, it looks like this is a known question with good but still not complete answers. dave (*) T. Bonnesen worked with convex bodies in the plane through the early decades of this century. (He proved (1921) the isoperimetric inequality L^2-4 pi A >= pi^2 (R-r)^2, where L is the length of a simple closed curve, A is the area of its interior, and R and r are the circumradius and inradius, respectively). I thought I might find references to this topic in the work of Blaschke, but didn't see it. ============================================================================== Date: Fri, 31 Oct 1997 16:05:29 +0100 To: rusin@vesuvius.math.niu.edu From: Andrea Spallanzani Subject: That Calculus of Variation problem (LONG!) Hello Dave, On 21 Oct 1997 06:27:31 GMT, in sci.math you wrote: >Your estimate of the ratio in your curve seems a bit high. >... >I can only assume the coefficient 0.93 was obtained by trial and >error. However, I got better results changing that same coefficient to >1.16 (giving volume 2.694678, length 8.921100, ratio .00379534.) You are absolutely right. I got the same results remaking computations more accurately. >The poster's suggested curves are part of a family of curves for >which I _do_ know how to proceed with optimization: In fact this is a C-o-V problem... I was going to de-rust and broaden my few knowledge of it to face this problem, but you arrived first ;) Hovever my fear was that this family of symmetric curves couldn't contain the best one. >The computed volume is .003796537196 and by construction the length is 1. Good! So my curve wasn't so bad... Can you find more than 16 points? >OK, that's enough for me. Thank you very much for your kind interest. Best regards ============================================================================== Another reference: Math Comp 22 (1968) 188-190, where Melzak estimates numerically the optimal volume, the "Baggins constant". -- djr ============================================================================== #Some Maple procedures for describing that "bulky curve" (maximizes volume # of convex hull for a given length.) #File was dated Nov 4 1997 Digits:=13: P0:=.09721756237111: P1:=.394594356718: de:={ diff(x(t),t$2)=-diff(z(t),t)^2/x(t), x(0.125)=P0, D(x)(.125)=P1, diff(y(t),t$2)=-diff(z(t),t)^2/y(t), y(0.125)=P0, D(y)(.125)=-P1, diff(z(t),t)=sqrt(1-diff(x(t),t)^2-diff(y(t),t)^2), z(0.125)=0, diff(A(t),t)=x(t)*y(t)*diff(z(t),t), A(0.125)=0 }: s:=dsolve(de,{x(t),y(t),z(t),A(t)},type=numeric): ans:=[]: for i from 0 to 256 do u:=s(.125*(1+i/256)): ans:=[op(ans),subs({op(u)},[x(t),y(t),z(t)])]; Area_over_8:=subs({op(u)},A(t)): od: ans:=[op(ans), Area_over_8]: save(ans,myfile): quit; #To plot it: B:=[]:for i from 0 to 256 do B:=[op(B),[ans[257-i][2],ans[257-i][1],-ans[257-i][3]]]:od: for i from 1 to 256 do B:=[op(B),ans[i]]:od: C:=[]:for i from 1 to 513 do C:=[op(C),B[i]]:od: for i from 1 to 512 do C:=[op(C),[-B[513-i][1],B[513-i][2],B[513-i][3]]]:od: d:=[]:for i from 1 to 1025 do d:=[op(d),C[i]]:od: for i from 1 to 1024 do d:=[op(d),[-C[i+1][1],-C[i+1][2],C[i+1][3]]]:od: with(plots): spacecurve(d); quit;