Verification of the Upper Bound Theorem (McMullen, 1970) in 2 dimensions
The cyclic polytope may be defined as the convex hull of vertices on the moment curve . The precise choice of which points on this curve are selected is irrelevant for the combinatorial structure of this polytope. The number of -dimensional facets (faces) of is given by the formula:
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.
Set the points the convex hull of which is to be calculated.
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
Find the point identities defining each facet of the convex hull of the point set.
Find the number of the facets of the convex hull.
nfacets1 = 21
Calculate the number of points the convex hull of which was calculated, as well as their dimension.
n = 21 d = 2
Calculate the maximum number of faces (1-dimensional facets) that a 2-dimensional convex hull () of 21 points can have.
maxfacets = 21
Check the validity of the Upper Bound Theorem.
if maxfacets<nfacets1 error('Upper Bound Theorem not satisfied') end
Find the first and the second point identity of each edge of the convex hull.
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.
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)
(c) 2014 by George Papazafeiropoulos First Lieutenant, Infrastructure Engineer, Hellenic Air Force Civil Engineer, M.Sc., Ph.D. candidate, NTUA