Path: utzoo!attcan!uunet!cs.utexas.edu!sun-barr!ccut!titcca!cc.titech.ac.jp!necom830!mohta
From: mohta@necom830.cc.titech.ac.jp (Masataka Ohta)
Newsgroups: comp.graphics
Subject: Re: Where to publish ray tracing algorithm?
Message-ID: <6191@titcce.cc.titech.ac.jp>
Date: 17 Sep 90 12:06:05 GMT
References: <1145@mti.mti.com> <1150@mti.mti.com> <6147@titcce.cc.titech.ac.jp>
Sender: news@cc.titech.ac.jp
Organization: Tokyo Institute of Technology
Lines: 20

In article <6147@titcce.cc.titech.ac.jp>
	mohta@necom830.cc.titech.ac.jp (Masataka Ohta) writes:

>>Rather than using recursive or hierarchical
>>spatial subdivision techniques to reduce ray-object intersection tests
>>(which are of O(log n) algorithms)

>Can you prove it? I think (but can't prove) hierarchical spatial
>subdivision is only O(n**(1/3)).

I have found it is obvious. All spatial subdivision is at
most O(n**(1/3)) if

	1) Objects are tiny
	2) Objects are uniformly scatterd in space

1) means that the possibility of intersection is negligible.
2) means at least O(n**(1/3)) subspace must be traversed.

							MO