Tag Archives: convex

Enveloppe convexe de points tirés au hasard

Le week-end dernier, Jean-Baptiste qui était de passage à la maison, me présentait un problème amusant de géométrie, lié à un papier mis en ligne l’an dernier, monotonicity of facet numbers of random convex hulls. Dans cet article, ils montrent que quand on tire n points au hasard (dans un espace de dimension d) alors P_n, le nombre moyen de face de l’enveloppe convexe est strictement croissant avec n. Si on n’a pas regardé la démonstration (on avait mieux à faire), Jean-Baptiste me disait que ce problème très simple était en fait très complexe. Et bien entendu, comme ça m’a interpelé, j’ai voulu regarder plus en détails. En dimension d=2, et en tirant en plus uniformément sur le carré unité (oui, j’ai fait très très simple).

Pour tirer des points au hasard, et récupérer l’enveloppe convexe, c’est assez simple, par exemple avec 15 points

library(sp)
library(geosphere)
n=15
UV=matrix(runif(2*n),n,2)
CH=chull(UV)
PLCH=UV[c(CH,CH[1]),]
plot(c(0,0,1,1),c(1,0,0,1))
polygon(PLCH,border="blue",col=rgb(0,0,1,.3))
points(UV,pch=19,cex=2,col="red")

On le voit, ici l’enveloppe convexe est un polygône de 8 côtés (ou 8 sommets). On peut alors faire un petit code pour tirer des points au hasard, construire l’enveloppe convexe, et sortir des infos (nombre de points extrémaux, surface de l’enveloppe convexe, présence ou non de certains points – sur la diagonale, etc)

simu=function(n,isplot=FALSE){
UV=matrix(runif(2*n),n,2)
CH=chull(UV)
PLCH=UV[c(CH,CH[1]),]
nb_ex=length(CH)
p_in=function(u) point.in.polygon(u,u,PLCH[,1],PLCH[,2])
pts_in=Vectorize(p_in)(seq(.5,.95,by=.05))
if(isplot==TRUE) lines(PLCH,col=rgb(0,0,1,.25))
return(list(nb=nb_ex,area=areaPolygon(PLCH),pts=pts_in))}

par exemple

plot(c(0,0,1,1),c(1,0,0,1),col="white")
for(s in 1:1000){S=simu(5,isplot=TRUE)}

(on pourrait bien entendu stocker tout plein de choses)

ou encore avec n= 20 points au lieu de 5

plot(c(0,0,1,1),c(1,0,0,1),col="white")
for(s in 1:1000){S=simu(20,isplot=TRUE)}

Essayons de boucler un peu sur n maintenant

Np=c(3,4,5,6,7,8,10,15,20,30,40,50,75,100,200)
VN=VA=rep(NA,15)
NN=matrix(NA,20000,15)
VPT=matrix(NA,15,10)
for(i in 1:15){
N=A=rep(NA,20000)
PT=matrix(NA,20000,10)
np=Np[i]
for(s in 1:20000){
S=simu(np,isplot=FALSE)
N[s]=S$nb
PT[s,]=S$pts
A[s]=S$area
}
NN[,i]=N
VN[i]=mean(N,na.rm=TRUE)
VA[i]=mean(A,na.rm=TRUE)
VPT[i,]=apply(PT,2,function(x) mean(x,na.rm=TRUE))
}

Cette fois on stocke tout plein de choses. On peut juste faire un boxplot du nombre des points extrémaux en fonction de la taille de l’échantillon

VV=rep(Np,each=20000)
boxplot(as.vector(NN)~as.factor(VV))

Oui, en moyenne, ça semble croitre. Plus amusant, si on regarde la moyenne en fonction de \log(n)

plot(Np,VN,type="l",log="x",col="blue")

on obtient… une belle droite ! Le nombre moyen de points extrémaux croit en \log(n). On peut même avoir la pente de cette droite,

> lm(VN~log(Np))
Coefficients:
(Intercept) log(Np)
0.05224 2.58717717

Je laisse les plus courageux trouver du sens à ce 2.58717… Si on continue un peu, on peut regarder la probabilité que (u,u) soit à l’intérieur, pour plusieurs valeurs de u.

plot(Np,VPT[,10],type="l",log="x",col="blue")
lines(Np,VPT[,8])
lines(Np,VPT[,5],col="red",lwd=2)

On retrouve des fonctions croisantes, en fonction de n, mais la convexité semble dépendre de l’endroit où se trouve le point u. Amusant, non ?

Nonconvexity, and playing indoor paintball

Following the two previous posts (here and there), on the number of people that don’t get wet while playing with water pistols, consider now an indoor version, in a non-convex room (i.e. player behind wall are now, somehow, protected). In the previous posts, players where playing on a square field, and I briefly mentioned that if the field was a disk, results would have been (roughly) the same: so far, the shape of the field was not an issue. But what if the field is no longer convex,

library(sp)
plot(0:2,0:2,col="white",xlab="",ylab="")
MAP=Polygon(cbind(c(0,0,1,1,2,2,0),
c(0,2,2,1,1,0,0)))
polygon(MAP@coords,col="light blue")

and players hidden behind the wall cannot be reached (red lines above are impossible hits). As earlier, it is still possible to look at the closest neighbor, we just have to exclude pairs that can no longer hit each other.

And again, it is possible to plot safe zones in green.

Once again, it is possible to look more closely are those supposed-to-be “safe zones”, i.e. by looking at the distribution of the location of players that were dry at the end of the game. With 11 players, we obtain


What about the distribution of the number of dry players, over a game ?

touch=function(x1,y1,x2,y2,n=251){
X=seq(x1,x2,length=n)
Y=seq(y1,y2,length=n)
sum(point.in.polygon(X,Y,MAP@coords[,1],
MAP@coords[,2], mode.checked=FALSE)==0)==0
}

NOTWETnc=function(n,p){
sx=runif(50)*2;sy=runif(50)*2
IN=which(point.in.polygon(sx,sy,MAP@coords[,1],
MAP@coords[,2], mode.checked=FALSE)==1)
Sx=sx[IN];Sy=sy[IN]
Sx=Sx[1:n];Sy=Sy[1:n]
IN=IN[1:n]
MI=matrix(NA,n,n)
for(i in 1:(n-1)){
for(j in (i+1):(n)){
MI[j,i]=MI[i,j]=touch(Sx[i],Sy[i],Sx[j],Sy[j])
}}
(d=as.matrix(dist(cbind(Sx,Sy),
method = "euclidean",upper=TRUE)))
diag(d)=999999
dpossible=d
dpossible[MI==FALSE]=999999
dmin=apply(dpossible,2,which.min)
#whonotwet=( (1:n) %notin% names(table(dmin)) )
notwet=n-length(table(dmin))
return(notwet)}

NOTWET=function(n){
x=runif(n)
y=runif(n)
(d=as.matrix(dist(cbind(x,y),
method = "euclidean",upper=TRUE)))
diag(d)=999999
dmin=apply(d,2,which.min)
notwet=n-length(table(dmin))
return(notwet)}

NSim=10000
Nnc=Vectorize(NOTWETnc)(n=rep(11,NSim))
Nc=Vectorize(NOTWET)(n=rep(11,NSim))
T=table(Nc)
Tn=table(Nnc)
plot(as.numeric(names(Tn)),
Tn/NSim,type="b",col="blue")
lines(as.numeric(names(T)),
T/NSim,type="b",col="red",pch=4)

On 11 players, we have the same distribution as the one on a square field. So convexity is not a key issue here…

Strange isn’t it. And with an odd number of player, not only there is at least one dry player, but at least, half of the players (maybe minus one) have to be wet…