ConvexHullMesh bug in Mathematica

README.md

ConvexHullMesh sometimes excludes valid points from convex hull

I have a sequence of polytopes that I am trying to visualize, and I find that ConvexHullMesh sometimes excludes points from the convex hull, and it does so inconsistently.

In particular, notice the three convex hulls rendered in the PNG.

From left to right, the set of points is changing slightly -- a new plane (linear constraint) is added each time, which removes some vertices, but adds new ones as well. However, the convex hull drawn by Mathematica excludes different valid points in the first two plots, and includes them in the last one.

Regardless of how these points are generated, they should all be included in their convex hull (by definition), so this is clearly a bug.

UPDATE:

I got a reply from Mathematica indicating that it is a numerical precision issue (the Mathematica implementation of the convex hull seems to work at a lower precision than the data types used). Two work arounds are:

1. Scale the data by a large number
2. Approximate the data by rationals

In other words, use

PlotPolytope2[n_] := 
 Module[{V = 1000 Sort[Import["v-" <> ToString[n] <> ".csv"]]},
  Show[ConvexHullMesh[V[[All, Range[1, 3]]]], 
   Graphics3D[{Black, Point[V[[All, Range[1, 3]]]]}]]]

or

PlotPolytope3[n_] := 
 Module[{V = Rationalize[#, 10^-10] &@ Sort[Import["v-" <> ToString[n] <> ".csv"]]}, 
  Show[ConvexHullMesh[V[[All, Range[1, 3]]]], 
   Graphics3D[{Black, Point[V[[All, Range[1, 3]]]]}]]]

bug.png

code.m

PlotPolytope[n_] :=
 Module[
	{
   V = Sort[
     Import["v-" <> ToString[n - 1] <> ".csv"]]
	},
  Show[
       ConvexHullMesh[V[[All, Range[1, 3]]]],
       Graphics3D[{Black, Point[V[[All, Range[1, 3]]]]}]
   ]
  ]

GraphicsGrid[
  {
    {PlotPolytope[8], PlotPolytope[9], PlotPolytope[10]}
  }
]

v-10.csv

v-8.csv

v-9.csv