RE: [Algorithms] Bounding cones.

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

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