<div dir="ltr"><div><div><div><span style="white-space:pre">> Now we are guessing, of course, but in my experience, when people<br>> casually talk about a shape in a 3-dimensional space without further<br>> clarification, they usually mean the 3d real Euclidean space or some<br>> approximation thereof.<br><br></span></div><span style="white-space:pre"><span style="white-space:pre">As long as we talk about a bounded</span> range (cube) from that space, I am actually willing to maintain my claim. (And the claim wouldn't make much sense without such bounding, because I talked about the ratio of the shape's volume vs. the range's volume.)<br><br></span></div><span style="white-space:pre">The discreteness, the coordinates being natural numbers in a finite range, is not really important.<br><br></span></div><span style="white-space:pre">Say we look at the 3d space spanned by (0,0,0) to (1,1,1) in real numbers. If there is a shape in there that is convex and takes up 0.5 of the volume, I can find a point belonging to it with a single query. <br></span><div><div><span style="white-space:pre"><br></span></div><div><span style="white-space:pre">If the ratio is 0.3 instead, what is the best querying strategy?<br><br></span></div><div><span style="white-space:pre">And so on.<br></span></div><div><span style="white-space:pre"><br></span><div><span style="white-space:pre"><br></span></div></div></div></div><div class="gmail_extra"><br><div class="gmail_quote">2015-10-29 14:01 GMT+01:00 Roman Cheplyaka <span dir="ltr"><<a href="mailto:roma@ro-che.info" target="_blank">roma@ro-che.info</a>></span>:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">On 10/29/2015 02:45 PM, Janis Voigtländer wrote:<br>
>> It's easy to prove that this is not decidable<br>
><br>
> I'm not sure what you mean by "this", but if you mean "to find a point<br>
> in an infinitely large space by finitely many experiments", then of<br>
> course it is not decidable, and I'm surprised you go to such length to<br>
> prove it. :-)<br>
<br>
I guess I was equally surprised to see you suggesting doing that!<br>
<br>
> It is not in the original question as formulated (except as hints if you<br>
> look for them), but let's assume the problem is that you have (x,y,z) -><br>
> Bool for x,y,z natural numbers below 100. And some of the 10^6 points<br>
> are True, others False. Is there a better algorithm for finding a True<br>
> point than blindly iterating through all 10^6 points?<br>
><br>
> I suggested that yes, there might be, if the shape is known to be convex<br>
> and a ratio is known of how much volume of the whole region it takes up.<br>
><br>
> Consider, for example, that the ratio is 0.5. Then only one check<br>
> suffices to find a point!<br>
<br>
Now we are guessing, of course, but in my experience, when people<br>
casually talk about a shape in a 3-dimensional space without further<br>
clarification, they usually mean the 3d real Euclidean space or some<br>
approximation thereof.<br>
<br>
</blockquote></div><br></div>