Re: SQL challenge
Date: Thu, 15 Jul 2004 13:20:49 -0700
Message-ID: <ASBJc.37$K9.303_at_news.oracle.com>
"Jan Hidders" <jan.hidders_at_REMOVETHIS.pandora.be> wrote in message
news:pan.2004.07.15.18.58.36.38772_at_REMOVETHIS.pandora.be...
> On Thu, 15 Jul 2004 11:45:51 -0700, Mikito Harakiri wrote:
> > "Jan Hidders" <jan.hidders_at_REMOVETHIS.pandora.be> wrote in message
> > news:pan.2004.07.15.17.52.05.184333_at_REMOVETHIS.pandora.be...
> >> On Wed, 14 Jul 2004 18:35:49 -0700, Mikito Harakiri wrote:
> >> > Consider tetrahedron defined by 4 vertices p1, p2, p3, p4. Then, for
any
> >> > point p it is easily decidable if p belongs to tetrahedron interior
or
> >> > not.
> >> > Let's call this predicate as
> >> >
> >> > Inside(p, p1, p2, p3, p4)
> >> >
> >> > This predicate is expected to work in the "extreme" cases when p1=p2
(or
> >> > even when p1=p2=p3). Finding closed form expression for Inside(p, p1,
> >> > p2,
> >> > p3, p4) is left as an exercise to the reader.
> >>
> >> Could you be a bit more precise here? What if p1 p2 p3 and p4 are on a
> >> single line, what does it then exactly mean to be inside? I assume no
node
> >> would be inside then, right? Or is a node on the edges of the
tetrahedron
> >> also "inside". And the corner points, are these inside?
> >
> > That is p belongs to convex hull of p1 p2 p3 and p4 but does not
coincide
> > with the vertices of that hull. This definition spans the cases where
> > tetrahedron is collapsed into planar or linear figure. (I'm not totally
> > happy being forced to exclude vertices from tetrahedron interior,
though).
>
> Ah, ok, then I agree with your solution. OK. So I hereby award you the
> unofficial Jim Gray SQL award of comp.databases.theory. :-)
Thank you, Jan. Could you please post the "official" answer?
Interestingly, you didn't ask the "simplest" question about convex hull. The more basic question would be "Find H-polyhedron", or "Remove all the interior nodes". In a word, faces and vertices are fundamental to convex hull problem, and edges are not. Common sence hints that "simpler" questions have much more elegant SQL representations. For example, matrix multiplication is just an elegant group-by statement. (This ends my short award speach). Received on Thu Jul 15 2004 - 22:20:49 CEST