RE: [Algorithms] Bounding cones.

[Gino v. d. B. <gva...@pl...>]

> -----Original Message-----
> From: Tom Forsyth [mailto:tom...@ee...]
> Sent: Wednesday, January 28, 2004 12:07
> To: gda...@li...
> Subject: RE: [Algorithms] Bounding cones.
>=20
>
[Stuff deleted]
=20
> Which means that although Nick is (probably) right when he says that
any
> bounding cone is formed by at most three cones, adding another cone
may
> produce a new bounding cone that uses a _completely different three_.
> Which
> is a pain.
>


It is not as much a pain as it sems. This problem occurs also for
bounding spheres. Welzl showed in
http://citeseer.nj.nec.com/welzl91smallest.html that on average a
randomized algorithm takes only linear time. That is, the number of
"painful" moments is relatively small. =20

=20
> However, I suspect the number you actually need to track will be
> reasonable
> in practice - you should be able to throw most of them away (anything
that
> is inside the hull is definately never going to be part of the hull in
> future). So this is certainly a plausable avenue of attack.


You can take the structure of Welzl's algorithm (who took it from
Seidel's LP algorithm) and add the necessary operations for your case:

	1. Test a cone for containment in another cone
	2. Construct a bounding cone for a set of 1 (trivial), 2, or 3
cones.

Notably the hull for 3 cones could be a challenge.

Gino van den Bergen
www.dtecta.com
=20