  We obtain new characterizations of the Sobolev spaces $\dot
W^{1,p}(\mathbb{R}^N)$ and the bounded variation space
$\dot{BV}(\mathbb{R}^N)$. The characterizations are in terms of the functionals
$\nu_{\gamma} (E_{\lambda,\gamma/p}[u])$ where \[ E_{\lambda,\gamma/p}[u]=
\Big\{(x,y )\in \mathbb{R}^N \times \mathbb{R}^N \colon x \neq y, \,
\frac{|u(x)-u(y)|}{|x-y|^{1+\gamma/p}}>\lambda\Big\} \] and the measure
$\nu_{\gamma}$ is given by $\mathrm{d} \nu_\gamma(x,y)=|x-y|^{\gamma-N}
\mathrm{d} x \mathrm{d} y$. We provide characterizations which involve the
$L^{p,\infty}$-quasi-norms $\sup_{\lambda>0} \lambda \, \nu_{\gamma}
(E_{\lambda,\gamma/p}[u]) ^{1/p}$ and also exact formulas via corresponding
limit functionals, with the limit for $\lambda\to\infty$ when $\gamma>0$ and
the limit for $\lambda\to 0^+$ when $\gamma<0$. The results unify and
substantially extend previous work by Nguyen and by Brezis, Van Schaftingen and
Yung. For $p>1$ the characterizations hold for all $\gamma \neq 0$. For $p=1$
the upper bounds for the $L^{1,\infty}$ quasi-norms fail in the range
$\gamma\in [-1,0) $; moreover in this case the limit functionals represent the
$L^1$ norm of the gradient for $C^\infty_c$-functions but not for generic $\dot
W^{1,1}$-functions. For this situation we provide new counterexamples which are
built on self-similar sets of dimension $\gamma+1$. For $\gamma=0$ the
characterizations of Sobolev spaces fail; however we obtain a new formula for
the Lipschitz norm via the expressions $\nu_0(E_{\lambda,0}[u])$.
