One of the more striking examples of the power of randomization is its use in the estimation of the volume of a polytope. Given an oracle that declares (for a given point) whether it's inside or outside the polytope, a randomized algorithm can get an arbitrarily good approximation to the volume, even though the problem is #P-Complete. A deterministic algorithm, on the other hand, will fail miserably.
A related question that I was curious about is the surface area estimation problem. Given a polytope defined by the intersection of hyperplanes (we can assume that the input promises to yield a bounded polytope for now), can we estimate its surface area efficiently ? Now, one can use a volume oracle on each hyperplane to determine the area of the face it contributes to (if at all), but I was wondering if there was a more direct method (especially since the above approach is far more wasteful than necessary, especially in small dimensions).
There's even a practical reason to do fast surface area estimation, at least in 3D: this is used as a heuristic for building efficient space partitionings for ray tracing.
Well, you can write the volume as an integral of the surface area (by using shrinking - similar to volume of ball and sphere area). Thats probably leads to something...
ReplyDeleteCheck out the paper below.
ReplyDeleteHeat Flow and a Faster Algorithm to Compute the Surface Area of a Convex Body
M. Belkin, H. Narayanan, P. Niyogi
FOCS 2006
http://www.cse.ohio-state.edu/~mbelkin/focs06.pdf
The ray-tracing application suggests a simple surface-area counterpart to the randomized volume algorithm. Instead of an oracle that tells you whether or not a randomly selected point is inside the polytope, you need an oracle that reveals whether or not a random ray passes through each face of the polytope. This should work even for nonconvex polytopes. On the other hand, that's quite an oracle!
ReplyDeleteWell, in the spirit of ray-tracing, if you randomly project to one lower dimension, the expected volume of the projection is proportional to the surface area, isn't it?
ReplyDelete-Ken Clarkson
Partha Niyogi will almost certainly talk about (among other things) his FOCS 2006 randomized heat-equation algorithm during his invited talk at SOCG.
ReplyDeleteAh. excellent. I'm looking forward to the talk.
ReplyDeleteChandra: thanks for the pointer.
Ken: That's an interesting idea, and might work reasonably well for ray tracing apps.
So, I haven't looked at the cited paper yet. But, here's my first take....
ReplyDeleteYou said the polytope was defined by the intersection of hyperplanes (half-spaces, right?). As such, it's convex. Start picking random points until your first Oracle says: "Hey, that one's inside."
Now, start picking random directions (pick three independent gaussians of zero mean and the same variance, then normalize). For each direction, ask your new Oracle the distance from the point to the polytope in the random direction. Say the i-th point is distance r_i away.
Your estimated surface area after n iterations will be ( 4π/n ) ∑ (r_i)^2.
The approximation here is that you're approximating the surface area as if the spot you hit was a spot on a sphere centered at your initial point.... that's where the 4π comes in.
I believe this works in the sphere even when your initial point isn't in the center of the sphere.... so I think it's safe in the polytope, too.
And, to add to what Ken said, in ray-tracing, the most important things would be cones eminating from light sources and the camera into the scene. So, if you could project the polytope down to a unit sphere centered at each light and one at the camera and add together the areas, you'll have a good idea of how likely the surface is to get hit. If projecting down to the unit sphere is bad, then you can probably get away with projecting to a plane a unit distance from the light/camera with the plane perpendicular to the line between the centroid of the polytope and the light/camera.
Oi... incoherent much? Time for me to sleep.
If the "tell me the distance" is too complicated for an oracle, then you could instead pick random points along that ray and ask the first Oracle (inside or outside) to estimate the radius. But, you wouldn't really be able to refine that later without tons of memory.
ReplyDeleteYou have to be a little careful here. You can't convert a membership query oracle into a distance query oracle. You're really changing the problem slightly if you assume that such an oracle exists. Now I don't mind that, except that I don't quite see how to implement it without spending linear time (drop perpendiculars to each face). This of course might be ok.
ReplyDeleteWhat's interesting is that you can estimate surface area even in the absence of such an oracle. In fact, the above cited paper by Belkin et al uses an idea not completely unrelated to what you're proposing. They do a random jump from the interior point according to a carefully chosen Gaussian, and check if the point exits the convex body. this gives them an estimate of the ratio S/V, from which they can get an estimate of S, since V can be estimated (S = surface area, V = Volume)
I suspected that could be a problem. I've never been clear on just what exactly one is allowed to ask an oracle. :)
ReplyDeleteAh.. one can only ask an Oracle yes/no questions?
ReplyDeleteYou can ask an oracle anything you want, although yes/no questions are the most common. The idea of a membership oracle to interact with a convex set comes from the idea that you want to make the class of convex sets as general as possible, and still see what can be done with it. Now it's not hard to design a distance oracle for convex polytopes, but to do so for an arbitrary convex set is much harder, whereas it's reasonable to expect that a convex set can be defined at least in terms of a membership oracle.
ReplyDelete