From: christian@ai.univie.ac.at (Christian Holzbaur)
Subject: Re: Finding convex  hull ?
Organization: Dept.Medical Cybernetics&Artificial Intelligence,Univ.Vienna,Austria,Europe
Date: Wed, 22 Jul 1992 11:31:18 GMT

In article <1992Jul21.161451.8912@taloa.unice.fr> guyard@dollar.unice.fr 
(Frederic Guyard) writes:

>Is there a fast algorithm to find the convex hull of a set of points, where  
>each point is a point of a n dimensional vector space. 
>If n=2, there is  the Graham algorithm... But for n>2 ?
>Is there a generalisation for the Graham algorithm ?

Within clp(r,q) [Constraint Logic Programming Languages over the Real, resp.
Rational numbers] you can formulate the convex hull construction almost
literally (see attached program). The magic that does
the trick is the (implicit) quantifier elimination step that presents 
answer substitutions and answer constraints projected onto variables in the query.

   Example in 2 dims 

       |
     2 -    *    *
       |
       |
     1 -    *
       |
       |
     0 -----|----*----*----
            1    2    3

  [Clp(Q)] ?- conv_hull([ [1,1], [2,0], [3,0], [1,2], [2,2] ], [X,Y]).

  X=<3-1/2*Y,
  Y=<2,
  Y>=0,
  X>=1,
  X>=2-Y
       
  The program is not limited to any number of points or dimensions. As
  far as efficiency is concerned, you might want to have a look at:

    Huynh T., Lassez J.L.: Practical Issues on the Projection of Polyhedral Sets,
    IBM Research Division, RC 15872 (#70560), 1990.


% ----8<----8<----8<----8<----8<----8<----8<----8<----8<----8<----8<----
      
%
% it's the Lambdas that get eliminated
%
conv_hull( Points, Xs) :-
  scaled_colsums( Points, Lambdas, Xs),
  polytope( Lambdas).

polytope( Xs) :-
  positive_sum( Xs, 1).

positive_sum( [],     0).
positive_sum( [X|Xs], X+Sum) :-
  X >= 0,
  positive_sum( Xs, Sum).

scaled_colsums( [],        [],     []).
scaled_colsums( [S0|Rest], [L|Ls], Sums) :-
  mult_row( S0, L, S1),
  scaled_colsums_rest( Rest, Ls, S1, Sums).

mult_row( [],     _, []).
mult_row( [X|Xs], K, [K*X|Xs1]) :-
  mult_row( Xs, K, Xs1).

scaled_colsums_rest( [],        [],     S1, S1).
scaled_colsums_rest( [Ps|Rest], [K|Ks], S1, S3) :-
  scaled_colsum_row( Ps, K, S1, S2),
  scaled_colsums_rest( Rest, Ks, S2, S3).

scaled_colsum_row( [],     _, [],     []).
scaled_colsum_row( [P|Ps], K, [S|Ss], [K*P+S|Ss1]) :-
  scaled_colsum_row( Ps, K, Ss, Ss1).

% ----8<----8<----8<----8<----8<----8<----8<----8<----8<----8<----8<----

PS: If you have a copy of Sicstus2.1 Prolog, you can get a Prolog implementation
    of clp(r) and clp(q) via anonymous ftp from 

         ftp.ai.univie.ac.at, directory sicstus, file clp1.2.tar.Z

+----------------------------------------------------------------------+
| Christian Holzbaur                  email: christian@ai.univie.ac.at |
| Dept. of Med. Cybernetics & AI,                                      |
| University of Vienna,               Phone: +43 222 53532810          |
| Freyung 6, A-1010 Vienna              FAX: +43 222 5320652           |
| Austria                                                              |
+----------------------------------------------------------------------+


-- 
+----------------------------------------------------------------------+
| Christian Holzbaur                  email: christian@ai.univie.ac.at |
| Dept. of Med. Cybernetics & AI,                                      |
| University of Vienna,               Phone: +43 222 53532810          |
Newsgroups: sci.math.symbolic