RE: [Algorithms] Bounding cones.

[Willem de B. <wd...@pl...>]

Actually, it might prove to be trickier than that. Hc as a=20
function of Vc is:

  Hc( Vc ) =3D max [ <Vi,Vc> + Hi ], for all 1<=3Di<=3DN

And the inequality constraints also contain Hc, which is exactly
the function we are trying to minimize. So, the problem is looking
very problematic :)

I do not (yet) know enough theory to work this all out; maybe
a heuristic approach like Jonathan's is best at the moment..

- Willem

-----Original Message-----
From: Willem de Boer=20
Sent: Wednesday, January 28, 2004 10:02 AM
To: 'gda...@li...'
Subject: RE: [Algorithms] Bounding cones.

Hello everyone,

Very interesting problem, Tom. I think this belongs to that esoteric
field called computational geometry; you should consult a book or two
on the subject, it's got applications in all fields within computer
graphics. Famous problems it tries to tackle include the optimal
bounding volume problem.

After my first coffe this morning, I decided you could pose your=20
problem mathematically, as follows:

Definition 1:
  A cone C is defined as an axis V and the cosine of its half-angle,
  H.=20

Definition (theorem really) 2:
  Given two cones C1 and C2, WITH COMMON ORIGINS. C1 is contained=20
  within C2 iff <V1,V2>+H1 <=3D H2. Where <,> denotes dot product.

Tom Forsyth's Problem:=20
  Given a collection {Ci} of cones with a common origin, axes {Vi}
  and cosine-half-angles {Hi}, find a cone C with axis Vc, such that
  Hc is minimised, and such that Ci is contained within C, for each
  i.

So it seems to me, one could to treat this as a minimsation
problem, try to find a Vc, so as to MINIMISE Hc, subject to N=20
inequality constraints of the form:

  <Vc,Vi>+Hi <=3D Hc.=20

So, maybe search for minimization, Kuhn-Tucker conditions, Lagrange
multipliers, that sort of stuff?

- Willem