Non-orthogonal multiple access (NOMA) has recently emerged as a promising multiple access technique for LTE enhancements and 5G due to its better cell coverage and potentially higher throughput than the traditional orthogonal multiple access. In its simplest form that superimposes only two constellations in the power domain, we investigate the optimal inter-constellation rotation based on the minimum distance (MD) criterion over an uplink NOMA scenario in this paper. In comparison with existing work that adopts constellation-constrained mutual information (MI) as the optimization criterion and hence can only determine the optimal inter-constellation rotation angle numerically, closed-form expressions for the MD-maximizing inter-constellation rotation angle as well as its achievable largest minimum distance among joint constellation points can be obtained for usual combinations of modulation schemes. Since the MD-maximizing inter-constellation rotation has nothing to do with the signal-to-noise ratio (SNR), as contrary to the MI-maximizing inter-constellation rotation, a more feasible SNR-independent system formulation can be established. Simulation results show that the MD-maximizing design not only can maintain a much more robust error performance than the SNR-dependent MI-maximizing design but achieves a better fairness among users.