Re: SQL challenge
Date: Mon, 12 Jul 2004 17:36:53 -0700
Message-ID: <AkGIc.44$kQ.68_at_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.
Therefore, we can proceed converting the above to SQL:
create table points (
X integer,
delete from points;
commit;
Y integer,
Z integer
)
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);
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 Tue Jul 13 2004 - 02:36:53 CEST