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

[Janis Voigtländer]

> 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. :-)

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!


2015-10-29 13:23 GMT+01:00 Roman Cheplyaka <roma at ro-che.info>:

> On 10/29/2015 11:36 AM, Janis Voigtländer wrote:
> > What if it is additionally known that the shape represented by (x,y,z)
> > -> Bool has a closed, convex area (for example)? Most likely there are
> > then techniques from algorithmic geometry that can find an inside point
> > more efficiently than by iterating blindly through all coordinate
> triples.
>
> It's easy to prove that this is not decidable (assuming we're talking
> about unbounded numbers, such as Data.Ratio.Rational, and not finite
> Double).
>
> Say you have an algorithm. Run it first on the empty space, and wait
> until it gives up after a finite number of probes. These probes all lie
> within some ball U. If you now insert your shape, however large, outside
> of the ball U, then the algorithm won't find it.
>
> Roman
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20151029/9c0e8e97/attachment.html>