tag:blogger.com,1999:blog-6555947.post3813323425271255631..comments2014-01-12T10:46:48.153-07:00Comments on The Geomblog: Estimating the surface area of a polytopeSuresh Venkatasubramanianhttps://plus.google.com/112165457714968997350noreply@blogger.comBlogger12125tag:blogger.com,1999:blog-6555947.post-75327604298648817052007-05-04T21:03:00.000-06:002007-05-04T21:03:00.000-06:00You can ask an oracle anything you want, although ...You 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.Sureshhttp://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-34843649402156163892007-05-04T17:49:00.000-06:002007-05-04T17:49:00.000-06:00Ah.. one can only ask an Oracle yes/no questions?Ah.. one can only ask an Oracle yes/no questions?patrickwondershttp://www.blogger.com/profile/13438444777222323470noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-70540485455225879092007-05-03T20:42:00.000-06:002007-05-03T20:42:00.000-06:00I suspected that could be a problem. I've never b...I suspected that could be a problem. I've never been clear on just what exactly one is allowed to ask an oracle. :)patrickwondershttp://www.blogger.com/profile/13438444777222323470noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-38481081862346101372007-05-03T08:35:00.000-06:002007-05-03T08:35:00.000-06:00You have to be a little careful here. You can't co...You 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.<BR/><BR/>What'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)Sureshhttp://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-85375732418085965052007-05-03T06:21:00.000-06:002007-05-03T06:21:00.000-06:00If the "tell me the distance" is too complicated f...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.patrickwondershttp://www.blogger.com/profile/13438444777222323470noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-31708025264240314602007-05-02T22:44:00.000-06:002007-05-02T22:44:00.000-06:00So, I haven't looked at the cited paper yet. But,...So, I haven't looked at the cited paper yet. But, here's my first take....<BR/><BR/>You 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."<BR/><BR/>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.<BR/><BR/>Your estimated surface area after n iterations will be ( 4π/n ) ∑ (r_i)^2.<BR/><BR/>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.<BR/><BR/>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.<BR/><BR/>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.<BR/><BR/>Oi... incoherent much? Time for me to sleep.patrickwondershttp://www.blogger.com/profile/13438444777222323470noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-30137993701851945112007-04-30T17:52:00.000-06:002007-04-30T17:52:00.000-06:00Ah. excellent. I'm looking forward to the talk.Cha...Ah. excellent. I'm looking forward to the talk.<BR/><BR/>Chandra: thanks for the pointer. <BR/><BR/>Ken: That's an interesting idea, and might work reasonably well for ray tracing apps.Sureshhttp://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-60069039496794176632007-04-30T17:36:00.000-06:002007-04-30T17:36:00.000-06:00Partha Niyogi will almost certainly talk about (am...Partha Niyogi will almost certainly talk about (among other things) his FOCS 2006 randomized heat-equation algorithm during his invited talk at SOCG.Jeff Ericksonhttp://www.blogger.com/profile/17633745186684887140noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-45394280319795163852007-04-30T09:59:00.000-06:002007-04-30T09:59:00.000-06:00Well, in the spirit of ray-tracing, if you randoml...Well, 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?<BR/><BR/>-Ken ClarksonAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-26346604106373912172007-04-30T09:57:00.000-06:002007-04-30T09:57:00.000-06:00The ray-tracing application suggests a simple surf...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!Brian Hayeshttp://bit-player.orgnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-55866310839110503692007-04-30T07:22:00.000-06:002007-04-30T07:22:00.000-06:00Check out the paper below.Heat Flow and a Faster A...Check out the paper below.<BR/><BR/>Heat Flow and a Faster Algorithm to Compute the Surface Area of a Convex Body <BR/>M. Belkin, H. Narayanan, P. Niyogi<BR/>FOCS 2006<BR/><BR/>http://www.cse.ohio-state.edu/~mbelkin/focs06.pdfChandrahttp://www.blogger.com/profile/00057069075567569157noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-56582982792381112392007-04-30T02:03:00.000-06:002007-04-30T02:03:00.000-06:00Well, you can write the volume as an integral of t...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...Anonymousnoreply@blogger.com