> Now we are guessing, of course, but in my experience, when people
> casually talk about a shape in a 3-dimensional space without further
> clarification, they usually mean the 3d real Euclidean space or some
> approximation thereof.

As long as we talk about a bounded 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.)

The discreteness, the coordinates being natural numbers in a finite range, is not really important.

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.

If the ratio is 0.3 instead, what is the best querying strategy?

And so on.



2015-10-29 14:01 GMT+01:00 Roman Cheplyaka <roma@ro-che.info>:
On 10/29/2015 02:45 PM, Janis Voigtländer wrote:
>> It's easy to prove that this is not decidable
>
> I'm not sure what you mean by "this", but if you mean "to find a point
> in an infinitely large space by finitely many experiments", then of
> course it is not decidable, and I'm surprised you go to such length to
> prove it. :-)

I guess I was equally surprised to see you suggesting doing that!

> It is not in the original question as formulated (except as hints if you
> look for them), but let's assume the problem is that you have (x,y,z) ->
> Bool for x,y,z natural numbers below 100. And some of the 10^6 points
> are True, others False. Is there a better algorithm for finding a True
> point than blindly iterating through all 10^6 points?
>
> I suggested that yes, there might be, if the shape is known to be convex
> and a ratio is known of how much volume of the whole region it takes up.
>
> Consider, for example, that the ratio is 0.5. Then only one check
> suffices to find a point!

Now we are guessing, of course, but in my experience, when people
casually talk about a shape in a 3-dimensional space without further
clarification, they usually mean the 3d real Euclidean space or some
approximation thereof.