home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / sci / math / symbolic / 2044 < prev    next >
Encoding:
Text File  |  1992-07-22  |  3.7 KB  |  110 lines
  1. Newsgroups: sci.math.symbolic
  2. Path: sparky!uunet!news.univie.ac.at!ai-univie!christian
  3. From: christian@ai.univie.ac.at (Christian Holzbaur)
  4. Subject: Re: Finding convex  hull ?
  5. Message-ID: <1992Jul22.113118.24947@ai.univie.ac.at>
  6. Sender: news@ai.univie.ac.at
  7. Nntp-Posting-Host: kairo.ai.univie.ac.at
  8. Organization: Dept.Medical Cybernetics&Artificial Intelligence,Univ.Vienna,Austria,Europe
  9. References: <1992Jul21.161451.8912@taloa.unice.fr>
  10. Date: Wed, 22 Jul 1992 11:31:18 GMT
  11. Lines: 97
  12.  
  13. In article <1992Jul21.161451.8912@taloa.unice.fr> guyard@dollar.unice.fr 
  14. (Frederic Guyard) writes:
  15.  
  16. >Is there a fast algorithm to find the convex hull of a set of points, where  
  17. >each point is a point of a n dimensional vector space. 
  18. >If n=2, there is  the Graham algorithm... But for n>2 ?
  19. >Is there a generalisation for the Graham algorithm ?
  20.  
  21. Within clp(r,q) [Constraint Logic Programming Languages over the Real, resp.
  22. Rational numbers] you can formulate the convex hull construction almost
  23. literally (see attached program). The magic that does
  24. the trick is the (implicit) quantifier elimination step that presents 
  25. answer substitutions and answer constraints projected onto variables in the query.
  26.  
  27.    Example in 2 dims 
  28.  
  29.        |
  30.      2 -    *    *
  31.        |
  32.        |
  33.      1 -    *
  34.        |
  35.        |
  36.      0 -----|----*----*----
  37.             1    2    3
  38.  
  39.   [Clp(Q)] ?- conv_hull([ [1,1], [2,0], [3,0], [1,2], [2,2] ], [X,Y]).
  40.  
  41.   X=<3-1/2*Y,
  42.   Y=<2,
  43.   Y>=0,
  44.   X>=1,
  45.   X>=2-Y
  46.        
  47.   The program is not limited to any number of points or dimensions. As
  48.   far as efficiency is concerned, you might want to have a look at:
  49.  
  50.     Huynh T., Lassez J.L.: Practical Issues on the Projection of Polyhedral Sets,
  51.     IBM Research Division, RC 15872 (#70560), 1990.
  52.  
  53.  
  54. % ----8<----8<----8<----8<----8<----8<----8<----8<----8<----8<----8<----
  55.       
  56. %
  57. % it's the Lambdas that get eliminated
  58. %
  59. conv_hull( Points, Xs) :-
  60.   scaled_colsums( Points, Lambdas, Xs),
  61.   polytope( Lambdas).
  62.  
  63. polytope( Xs) :-
  64.   positive_sum( Xs, 1).
  65.  
  66. positive_sum( [],     0).
  67. positive_sum( [X|Xs], X+Sum) :-
  68.   X >= 0,
  69.   positive_sum( Xs, Sum).
  70.  
  71. scaled_colsums( [],        [],     []).
  72. scaled_colsums( [S0|Rest], [L|Ls], Sums) :-
  73.   mult_row( S0, L, S1),
  74.   scaled_colsums_rest( Rest, Ls, S1, Sums).
  75.  
  76. mult_row( [],     _, []).
  77. mult_row( [X|Xs], K, [K*X|Xs1]) :-
  78.   mult_row( Xs, K, Xs1).
  79.  
  80. scaled_colsums_rest( [],        [],     S1, S1).
  81. scaled_colsums_rest( [Ps|Rest], [K|Ks], S1, S3) :-
  82.   scaled_colsum_row( Ps, K, S1, S2),
  83.   scaled_colsums_rest( Rest, Ks, S2, S3).
  84.  
  85. scaled_colsum_row( [],     _, [],     []).
  86. scaled_colsum_row( [P|Ps], K, [S|Ss], [K*P+S|Ss1]) :-
  87.   scaled_colsum_row( Ps, K, Ss, Ss1).
  88.  
  89. % ----8<----8<----8<----8<----8<----8<----8<----8<----8<----8<----8<----
  90.  
  91. PS: If you have a copy of Sicstus2.1 Prolog, you can get a Prolog implementation
  92.     of clp(r) and clp(q) via anonymous ftp from 
  93.  
  94.          ftp.ai.univie.ac.at, directory sicstus, file clp1.2.tar.Z
  95.  
  96. +----------------------------------------------------------------------+
  97. | Christian Holzbaur                  email: christian@ai.univie.ac.at |
  98. | Dept. of Med. Cybernetics & AI,                                      |
  99. | University of Vienna,               Phone: +43 222 53532810          |
  100. | Freyung 6, A-1010 Vienna              FAX: +43 222 5320652           |
  101. | Austria                                                              |
  102. +----------------------------------------------------------------------+
  103.  
  104.  
  105. -- 
  106. +----------------------------------------------------------------------+
  107. | Christian Holzbaur                  email: christian@ai.univie.ac.at |
  108. | Dept. of Med. Cybernetics & AI,                                      |
  109. | University of Vienna,               Phone: +43 222 53532810          |
  110.