Re: SQL challenge

From: Mikito Harakiri <mikharakiri_at_iahu.com>
Date: Mon, 12 Jul 2004 17:36:53 -0700
Message-ID: <AkGIc.44$kQ.68@news.oracle.com>

"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

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. Received on Mon Jul 12 2004 - 19:36:53 CDT