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

[Roman Cheplyaka]

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

-------------- 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/69a83f74/attachment.sig>