  We introduce tools from numerical analysis and high dimensional probability
for precision control and complexity analysis of subdivision-based algorithms
in computational geometry. We combine these tools with the continuous
amortization framework from exact computation. We use these tools on a
well-known example from the subdivision family: the adaptive subdivision
algorithm due to Plantinga and Vegter. The only existing complexity estimate on
this rather fast algorithm was an exponential worst-case upper bound for its
interval arithmetic version. We go beyond the worst-case by considering both
average and smoothed analysis, and prove polynomial time complexity estimates
for both interval arithmetic and finite-precision versions of the
Plantinga-Vegter algorithm.
