[Haskell-cafe] Find a point inside (x,y,z) -> Bool

[Roman Cheplyaka]

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.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: OpenPGP digital signature
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20151029/471b43a3/attachment.sig>