  We present a general framework for analyzing the complexity of
subdivision-based algorithms whose tests are based on the sizes of regions and
their distance to certain sets (often varieties) intrinsic to the problem under
study. We call such tests diameter-distance tests. We illustrate that
diameter-distance tests are common in the literature by proving that many
interval arithmetic-based tests are, in fact, diameter-distance tests. For this
class of algorithms, we provide both non-adaptive bounds for the complexity,
based on separation bounds, as well as adaptive bounds, by applying the
framework of continuous amortization.
  Using this structure, we provide the first complexity analysis for the
algorithm by Plantinga and Vegeter for approximating real implicit curves and
surfaces. We present both adaptive and non-adaptive a priori worst-case bounds
on the complexity of this algorithm both in terms of the number of subregions
constructed and in terms of the bit complexity for the construction. Finally,
we construct families of hypersurfaces to prove that our bounds are tight.
