Before revision:  For axis-aligned squares instead of disks, a related concept called relative-length was already discussed and it has an exact{\epsilon})+n{\epsilon}) time algorithm, and the existing } O(n ^3) algorithm. We show that vertex-relative c-packedness has approximation factor at least 2 for c-packedness. We design the first exact algorithmfor computing the minimum c for which a given curve P is c-packed. Our algorithm runs in O(n^5) time .
After revision:  For axis-aligned squares instead of disks, a related concept called relative-length was already discussed and it has an exact{\epsilon})+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 .