Subject: Question about Collision Detection

From: [email-masked] (Youn jihoon)
Date: Mon, 18 May 92 22:43:34 KDT

I have read the following paper : 

	"Comutational Compexity vs. Simulated Environments",
						A.Pentland,ACM CG,pp185-192,1990.

	At page 186 of above paper, there is a paragraph
as followings:

	o Collision Detection. Physical objects do not in-
	terpenetrate, and so we must calculate collisions be-
	tween objects at each time step. For coarse colli-
	sion detection it is possible to trade storage com-
	plexity against calculation complexity. For instance:
	a typical octree scheme allows collision detection in
	O(log m) operations and O(m^2) storage locations, 
	where 1/m is the spatial resolution of the collision
	detection. However most programmers have pre-
	ferred to use bounding boxes rather than octrees,
	because although the bounding box comparison re-
	quires somewhat more calculation it it only O(m) in
	storage.

	I can not inference why it is possible to get O(log m)
and O(m^2) when using octree scheme. I think that at least
the storage complexity is about O(m^3) or a few low. Morever
is it possible to get somewhat more calculation than O(log m)
and only O(m) storage complexity by using bounding box?

	Please inform me of something to make me to understand
the above paragraph.

						From Youn Ji-Hoon.