  A polygonal curve $P$ with $n$ vertices is $c$-packed, if the sum of the
lengths of the parts of the edges of the curve that are inside any disk of
radius $r$ is at most $cr$, for any $r>0$. Similarly, the concept of
$c$-packedness can be defined for any scaling of a given shape.
  Assuming $L$ is the diameter of $P$ and $\delta$ is the minimum distance
between points on disjoint edges of $P$, we show the approximation factor of
the existing $O(\frac{\log (L/\delta)}{\epsilon}n^3)$ time algorithm is
$1+\epsilon$-approximation algorithm. The massively parallel versions of these
algorithms run in $O(\log (L/\delta))$ rounds. We improve the existing
$O((\frac{n}{\epsilon^3})^{\frac 4 3}\polylog \frac n \epsilon)$ time
$(6+\epsilon)$-approximation algorithm by providing a
$(4+\epsilon)$-approximation $O(n(\log^2 n)(\log^2
\frac{1}{\epsilon})+\frac{n}{\epsilon})$ time algorithm, and the existing
$O(n^2)$ time $2$-approximation algorithm improving the existing $O(n^2\log n)$
time $2$-approximation algorithm.
  Our exact $c$-packedness algorithm takes $O(n^5)$ time, which is the first
exact algorithm for disks. We show using $\alpha$-fat shapes instead of disks
adds a factor $\alpha^2$ to the approximation.
  We also give a data-structure for computing the curve-length inside query
disks. It has $O(n^6\log n)$ construction time, uses $O(n^6)$ space, and has
query time $O(\log n+k)$, where $k$ is the number of intersected segments with
the query shape. We also give a massively parallel algorithm for relative
$c$-packedness with $O(1)$ rounds.
