Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!uunet!paralogics!shaw
From: shaw@paralogics.UUCP (Guy Shaw)
Newsgroups: comp.graphics
Subject: Re: Random points on a sphere
Summary: I am hesitant to use rejection methods because
	 they lack performance guarantees
Message-ID: <271@paralogics.UUCP>
Date: 8 May 90 08:28:39 GMT
References: <150632@<1990May4> <4400066@m.cs.uiuc.edu>
Organization: Paralogics; Santa Monica, CA
Lines: 43

In article <4400066@m.cs.uiuc.edu>, cwg@m.cs.uiuc.edu writes a good
summary of many postings:

> (1) choose a region over which it is simple to generate random points and
> which contains the sphere, and then reject those points outside.

[...]

> (2) Choose a parameterization of the space, and then generate points
> with a probability distribution appropriate to the parametarization.


I have seen several postings which compute the _average_ cost of
computing random points in a unit cube and rejecting those that lie
outside the inscribed unit sphere.  Some argue that rejection methods
are cheaper because you don't need to compute trig functions, others
argue that the cost of 1 trig function is less than the average combined
cost of computing, rejecting, and projecting.  The race seems close
enough that all I am convinced of is that a _good_ implementation of one
method is faster than a not-so-good implementation of the other.

The thing that bothers me about using any method that involves
generating random numbers and rejecting those that fail some test
is that, even though an average rejection rate is known, there is
no guarantee that I won't generate a _long_ series of rejected numbers.

This is why I would go out of my way to choose a method involving
transformations, even if the cost of a transformation is more expensive
than the average cost of a rejection method.  But, if for some other
problem, the cost of transformation were so prohibitively expensive that
I must use rejection methods, I would want to put a limit on the length
of a run of rejected points and figure out something reasonable to do if
that limit is exceeded.

Am I just being paranoid?  Is this just a theoretical nit, or does this
count "for all practical purposes", as well?  Does anyone have some pointers
to literature on the subject?

Thanks in advance.
-- 
Guy Shaw
Paralogics
paralogics!shaw@uunet.uu.net  or  uunet!paralogics!shaw