Since the publication of the original Marching Cubes algorithm, numerous variations have been proposed for guaranteeing water-tight constructions of triangulated approximations of iso-surfaces. Most approaches divide the 3D space into cubes that each occupies the space between eight neighboring samples of a regular lattice. The portion of the iso-surface inside a cube may be computed independently of what happens in the other cubes, provided that the constructions for each pair of neighboring cubes agree along their common face. The portion of the iso-surface associated with a cube may consist of one or more connected components, which we call sheets. We distinguish three types of decisions in the construction of the iso-surface connectivity: (1) how to split the X-faces, which have alternating in/out samples, (2) how many sheets to use in a cube, and (3) how to triangulate each sheet. Previously reported techniques make these decisions based on local criteria, often using pre-computed look-up tables or simple construction rules. Instead, we propose global strategies for optimizing several topological and combinatorial measures of the isosurfaces: triangle count, genus, and number of shells. We describe efficient implementations of these optimizations and the auxiliary data structures developed to support them.