Re: SQL challenge

From: Jan Hidders <jan.hidders_at_REMOVETHIS.pandora.be>
Date: Tue, 13 Jul 2004 17:45:00 GMT
Message-Id: <pan.2004.07.13.17.45.22.985796@REMOVETHIS.pandora.be>

On Mon, 12 Jul 2004 17:36:53 -0700, Mikito Harakiri wrote:
> "Jan Hidders" <jan.hidders_at_REMOVETHIS.pandora.be> wrote in message
> news:pan.2004.07.12.23.10.13.427982_at_REMOVETHIS.pandora.be...

>> At the last SIGMOD conference I heard an anecdote about how Jim Gray had
>> gained the respect of some of his colleagues by computing the
>> convex hull of a set of three-dimensional points in a table with a single
>> SQL query that used only basic SQL (SQL-89). To be a little more concrete,
>> the input is a relation P(x,y,z) and the output L(x1,y1,z1,x2,y2,z2) that
>> describes the minimal set of edges that span the convex hull of the nodes
>> in P.

>
> It is easier to think of the convex hull in terms of [triangular] faces
> rather than edges. Indeed, each face defines a plane that divides the space
> into 2 halves and all the points would be in the one half-space or the
> other.
>
> Suppose we have triangle with vertices (p1.x,p1.y,p1.z), (p2.x,p2.y,p2.z),
> (p3.x,p3.y,p3.z). What side of the plane some other point (p.x,p.y,p.z) is
> positioned at? It is easy to see that we have to calculate cross product of
>
> (p1.x-p2.x,p1.y-p2.y,p1.z-p2.z) and (p1.x-p3.x,p1.y-p3.y,p1.z-p3.z)
>
> and scalarly multiply it into
>
> (p1.x-p.x,p1.y-p.y,p1.z-p.z)
>
> Then the sign of the result would indicate which side of the plane the point
> is positioned at.
>
> Technically, we have to calculate determinant
>
> det(matrix(3,3,[[p1.x-p2.x,p1.y-p2.y,p1.z-p2.z],[p1.x-p3.x,p1.y-p3.y,p1.z-p3
> .z],[p1.x-p.x,p1.y-py,p1.z-p.z]]));
>
> and Mapple says that it's eqial to
>
> p1.x*p.z*p3.y-p1.x*p.y*p3.z-p2.x*p.z*p3.y+p2.x*p.z*p1.y-
> p1.x*p.z*p2.y+p2.x*p.y*p3.z-p2.x*p.y*p1.z+p1.x*p.y*p2.z+
> p3.x*p.z*p2.y-p3.x*p.z*p1.y-p.x*p2.z*p1.y-p.x*p1.z*p3.y-
> p.x*p2.y*p3.z+p.x*p2.y*p1.z+ p.x*p1.y*p3.z-p3.x*p.y*p2.z+
> p3.x*p.y*p1.z+p.x*p2.z*p3.y-p3.x*p2.y*p1.z+p3.x*p2.z*p1.y+
> p1.x*p2.y*p3.z-p1.x*p2.z*p3.y+p2.x*p1.z*p3.y-p2.x*p1.y*p3.z

Ha, Mikito. I knew I could count on you. :-) Yes this is indeed the way to do it although you can write the above a bit more succinctly as:

  ((p1.y-p2.y)*(p1.z-p3.z)-(p1.z-p2.z)*(p1.y-p3.y))*(p.x-p1.x) +
  ((p1.z-p2.z)*(p1.x-p3.x)-(p1.x-p2.x)*(p1.z-p3.z))*(p.y-p1.y) +
  ((p1.x-p2.x)*(p1.y-p3.y)-(p1.y-p2.y)*(p1.x-p3.x))*(p.z-p1.z)

> Therefore, we can proceed converting the above to SQL:
>
> create table points (
> X integer,
> Y integer,
> Z integer
> )
>
> delete from points;
> insert into points values (0,0,0);
> insert into points values (0,0,1);
> insert into points values (0,1,0);
> insert into points values (1,0,0);
>
> commit;
>
> select p1.x,p1.y,p1.z,
> p2.x,p2.y,p2.z,
> p3.x,p3.y,p3.z
> from points p1, points p2, points p3
> where (p1.x!=p2.x or p1.y!=p2.y or p1.z!=p2.z) // p1,p2,and p3 are distinct
> and (p1.x!=p3.x or p1.y!=p3.y or p1.z!=p3.z)
> and (p2.x!=p3.x or p2.y!=p3.y or p2.z!=p3.z)
> and (
> 0=(select count(1) from points p where
> p1.x*p.z*p3.y-p1.x*p.y*p3.z-p2.x*p.z*p3.y+p2.x*p.z*p1.y-
> p1.x*p.z*p2.y+p2.x*p.y*p3.z-p2.x*p.y*p1.z+p1.x*p.y*p2.z+
> p3.x*p.z*p2.y-p3.x*p.z*p1.y-p.x*p2.z*p1.y-p.x*p1.z*p3.y-
> p.x*p2.y*p3.z+p.x*p2.y*p1.z+ p.x*p1.y*p3.z-p3.x*p.y*p2.z+
> p3.x*p.y*p1.z+p.x*p2.z*p3.y-p3.x*p2.y*p1.z+p3.x*p2.z*p1.y+
> p1.x*p2.y*p3.z-p1.x*p2.z*p3.y+p2.x*p1.z*p3.y-p2.x*p1.y*p3.z
> > 0 )
> or
> 0=(select count(1) from points p where
> p1.x*p.z*p3.y-p1.x*p.y*p3.z-p2.x*p.z*p3.y+p2.x*p.z*p1.y-
> p1.x*p.z*p2.y+p2.x*p.y*p3.z-p2.x*p.y*p1.z+p1.x*p.y*p2.z+
> p3.x*p.z*p2.y-p3.x*p.z*p1.y-p.x*p2.z*p1.y-p.x*p1.z*p3.y-
> p.x*p2.y*p3.z+p.x*p2.y*p1.z+ p.x*p1.y*p3.z-p3.x*p.y*p2.z+
> p3.x*p.y*p1.z+p.x*p2.z*p3.y-p3.x*p2.y*p1.z+p3.x*p2.z*p1.y+
> p1.x*p2.y*p3.z-p1.x*p2.z*p3.y+p2.x*p1.z*p3.y-p2.x*p1.y*p3.z
> < 0 )
> )
>
> Finally, the remaining tiny problem is selecting edges from faces.

Well, the problem was to find the *minimal* set. (Actually I didn't define that properly, what I meant was the set with the least number of edges.) If I give you the corners of a cube plus some extra points on its surface and its edges then I still just want the edges between the corner points of the cube. If you simply take the edges of your solution then there are many more edges. For example, if there is point in the middle of a plane of the convex hull then you will have (redundant) edges from and to this point. Or if there is a node in the middle of an edge of the convex hull then you will have (redundant) edges from and to this point. These need to be removed.

You're not there yet. :-)

Jan Hidders

Received on Tue Jul 13 2004 - 12:45:00 CDT