MATLAB Examples

Verification of the Upper Bound Theorem (McMullen, 1970) in 2 dimensions

Contents

Introduction

The cyclic polytope $CP(n,d)$ may be defined as the convex hull of $n$ vertices on the moment curve $(t, t^2, t^3, ..., t^d)$. The precise choice of which $n$ points on this curve are selected is irrelevant for the combinatorial structure of this polytope. The number of $(d-1)$ -dimensional facets (faces) of $CP(n,d)$ is given by the formula:

$$f_i(\Delta(n,d)) = \frac{n}{n - \frac{d}{2}} {{n - \frac{d}{2}} \choose
n-d} \hspace{0.2in} d \quad \textrm{even} \quad $$

$$f_i(\Delta(n,d)) = 2 {{n - \frac{d+1}{2}} \choose n-d} \hspace{0.2in} d
\quad \textrm{odd} \quad $$

The upper bound theorem states that cyclic polytopes have the largest possible number of faces among all convex polytopes with a given dimension and number of vertices.

Initial data

Set the points the convex hull of which is to be calculated.

t=(0:0.1:2)';
points=[t,t.^2];

Plot the point set in blue circles.

figure('Name','Point set','NumberTitle','off')
scatter(points(:,1),points(:,2),...
    'marker','o','MarkerEdgeColor',[0 0 1],'LineWidth',2)
xlabel('x','FontSize',13);
ylabel('y','FontSize',13);
title('Point set','FontSize',13)
axis equal

Processing

Find the point identities defining each facet of the convex hull of the point set.

chull1=convhull_nd(points);

Post-processing

Find the number of the facets of the convex hull.

nfacets1=size(chull1,1)
nfacets1 =

    21

Calculate the number of points the convex hull of which was calculated, as well as their dimension.

[n,d]=size(points)
n =

    21


d =

     2

Calculate the maximum number of faces (1-dimensional facets) that a 2-dimensional convex hull ($$d=2$) of 21 points can have.

maxfacets=n/(n-d/2)*nchoosek(n-d/2,n-d)
maxfacets =

    21

Check the validity of the Upper Bound Theorem.

if maxfacets<nfacets1
    error('Upper Bound Theorem not satisfied')
end

Plots

Find the first and the second point identity of each edge of the convex hull.

node1=chull1(:,1);
node2=chull1(:,2);

Find the x and y coordinates of the first and second point of each edge of the convex hull.

x1=points(node1,1);
x2=points(node2,1);
y1=points(node1,2);
y2=points(node2,2);

Arrange the coordinate data.

X1=[x1,x2]';
Y1=[y1,y2]';

Plot the convex hull.

figure('Name','Convex hull','NumberTitle','off')
line(X1,Y1,'marker','.','markersize',20,'markeredgecolor',[1 0.5 0],...
    'linestyle','-', 'linewidth',2,'color','blue');
xlabel('x','FontSize',13);
ylabel('y','FontSize',13);
title('Convex hull','FontSize',13)

Contact author

(c) 2014 by George Papazafeiropoulos
First Lieutenant, Infrastructure Engineer, Hellenic Air Force
Civil Engineer, M.Sc., Ph.D. candidate, NTUA

Email: gpapazafeiropoulos@yahoo.gr

Website: http://users.ntua.gr/gpapazaf/