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

Janis Voigtländer janis.voigtlaender at gmail.com
Thu Oct 29 13:08:02 UTC 2015


> 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 at 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.
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20151029/37412f04/attachment.html>


More information about the Haskell-Cafe mailing list