>

restart:

>	with(plots):

1. VISUALISER LE DIAGRAMME DE VORONOI

Voici une première méthode pour visualiser le diagramme de Voronoi d'un ensemble de points S : c'est la projection verticale de l'enveloppe convexe inférieure de l'union des cônes basés aux points de l'ensemble S et de pente 45°. On trace donc tous ces cônes et on visualise le résultat par dessous. On peut faire tourner la figure pour bien voir la méthode.

>

voronoi1:=proc(L) local xmax,xmin,ymax,ymin,n,P; n:=nops(L); xmax:=max(seq(L[i][1],i=1..n))+1;xmin:=min(seq(L[i][1],i=1..n))-1; ymax:=max(seq(L[i][2],i=1..n))+1;ymin:=min(seq(L[i][2],i=1..n))-1; P:=[seq(plot3d(sqrt((x-L[i][1])^2+(y-L[i][2])^2),x=xmin..xmax,y=ymin..ymax,color=COLOR(RGB,i/n,i/n,i/n),orientation=[90,180],linestyle=2,axes=BOXED),i=1..n),seq(pointplot3d([op(L[i]),0],color=red,orientation=[90,180]),i=1..n)]; plots[display](P); end proc;

>	voronoi1([[0,1],[1,-1],[1,1],[-1,0],[.5,1.5]]);voronoi1([[0,1],[1,-1],[1,1],[-1,0],[.5,1.5]]);

Voici une seconde méthode : le diagramme de Voronoi de S est la projection verticale de l'intersection des demi-espaces supérieurs limités par les hyperplans tangents au paraboloide P (d'équation t=x²) aux points (x,x²), où x décrit S. On trace donc tous les hyperplans (on connaît leur équation) et on visualise le résultat par dessus. On peut encore une fois faire tourner la figure pour bien voir la méthode.

>

voronoi2:=proc(L) local xmax,xmin,ymax,ymin,n,P; n:=nops(L); xmax:=max(seq(L[i][1],i=1..n))+1;xmin:=min(seq(L[i][1],i=1..n))-1; ymax:=max(seq(L[i][2],i=1..n))+1;ymin:=min(seq(L[i][2],i=1..n))-1; P:=[seq(plot3d(2*(x*L[i][1]+y*L[i][2])-L[i][1]^2-L[i][2]^2,x=xmin..xmax,y=ymin..ymax,color=COLOR(RGB,i/n,i/n,i/n),orientation=[-90,0],linestyle=2,axes=BOXED),i=1..n),seq(pointplot3d([op(L[i]),L[i][1]^2+L[i][2]^2+1],color=red,orientation=[-90,0]),i=1..n)]; plots[display](P); end proc;

>	voronoi2([[0,1],[1,-1],[1,1],[-1,0],[.5,1.5]]);voronoi2([[0,1],[1,-1],[1,1],[-1,0],[.5,1.5]]);

2. TRI DE LISTE PAR DIVISION-FUSION

>	divise:=L->[L[1..floor(nops(L)/2)],L[floor(nops(L)/2)+1..nops(L)]];

>	fusion:=proc(M,N) local L; if M=[] then return(N); elif N=[] then return(M); elif M[1]<=N[1] then return([M[1],op(fusion(M[2..nops(M)],N))]) else return([N[1],op(fusion(M,N[2..nops(N)]))]); end if; end proc;

>	trifusion:=proc(L) local M; if nops(L)<=1 then return(L) else M:=divise(L); fusion(trifusion(M[1]),trifusion(M[2])); end if; end proc;

>	trifusion([1,4,2,6,25,76,43,25,12,3,7,8]);

>	insert:=proc(L,e) if L=[] then return([e]) elif e<=L[1] then return([e,op(L)]) else return([L[1],op(insert(L[2..nops(L)],e))]); end if; end proc;