Given a set H of n hyperplanes in R^{d},
we present an algorithm that µ-approximates the extent
between the top and bottom k-levels of the arrangement of
H in time O(n +(k/µ)^{c}), where c is
a constant depending on d. The algorithm relies on computing a
coreset of size O(k/µ^{d-1}) in near linear time,
such that the k-level of the arrangement of the coreset
approximates that of the original arrangement. Using this algorithm,
we present efficient approximation algorithms for shape fitting with
outliers, for various shapes. This is the first algorithm to handle
outliers efficiently for the shape fitting problems considered.