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