So, just out of curiosity, I wrote my own version. (It's not perfect; I need to review the edge cases, as I get spurious wrong results when the test point is exactly at the edge of the bounding box).

It turns out that just halving the bounding box yields pretty good results. (I still suspect that when there is only one vertex within the bounding box, it is best to pick that vertex as the splitting point -- just in case that vertex participates in a large number of sides.)

For the few test cases I did, ignoring the vertices completely (after building the half-spaces) yielded very good results for regular convex polyhedra; it also worked acceptably for a 100-vertex polyhedron with all vertices randomly on the unit sphere.

In other words, you probably should drop the vertices as soon as the halfspaces are generated. The vertex information does not seem to help as much as I originally thought.

It might be a better approach to save the bounding box of the polytope side, when the halfspaces are generated, instead. (The bounding box is just the minimum and maximum coordinates of the vertices that are at the plane of the halfspace, since the polytope is convex.)

This does make the size of each halfspace definition much bigger (fromD+1 doubles to 3D+1 doubles, whereDis the number of dimensions):

However, it might allow a better logic of how to divide the box efficiently.Code:typedef struct { point_t min; point_t max; point_t normal; double distance; } halfspace_t;