A new method for calculating fractal dimension is developed in this paper. The method is based on the box dimension concept; however, it involves direct estimation of a suboptimal covering of the data set of interest. By finding a suboptimal cover, this method is better able to estimate the required number of covering elements for a given cover size than is the standard box counting algorithm. Moreover, any decrease in the error of the covering element count directly increases the accuracy of the fractal dimension estimation. In general, our method represents a mathematical dual to the standard box counting algorithm by not solving for the number of boxes used to cover a data set given the size of the box. Instead, the method chooses the number of covering elements and then proceeds to find the placement of smallest hyperellipsoids that fully covers the data set. This method involves a variant of the Fuzzy-C Means clustering algorithm, as well as the use of the Minimum Cluster Volume clustering algorithm. A variety of fractal dimension estimators using this suboptimal covering method are discussed. Finally, these methods are compared to the standard box counting algorithm and wavelet-decomposition methods for calculating fractal dimension by using one-dimensional cantor dust sets and a set of standard Brownian random fractal images.