Given a surface how can I get an $\epsilon$-sample? Few definitions and then my question:


  Definition 1.1. The medial axis $M$ of a curve (surface) $\Sigma \in \mathbb{R}^k$ is the closure of the set of points in $\mathbb{R}^k$ that have at least two closest points in $\Sigma$.
  
  Definition 1.2. The local feature size at a point $x \in \Sigma$ is the value of a function
  $$
f(x) : \Sigma \to \mathbb{R} \;\;\text{where} \; f(x) = d(x,M)
$$
  In other words $f(x)$ is the distance of $x \in \Sigma$ to the medial axis $M$.
  
  Definition 1.3. A sample $P$ of $\Sigma$ is a $\epsilon$-sample if each point $x \in \Sigma$ has a sample point $p \in P$ such that $\left\|x - p \right\| \leq \epsilon f(x)$


These definition are taken from chapter 1 in Curve and Surface Reconstraction : Algorithms and Mathematical analysis.

My question is : Suppose $\Sigma$ is some regular surface given, is there a known algorithm to generate a sample $P$ which is a $\epsilon$-sample?

I would imagine just a simple sampling of the surface wouldn't really work, what I want is to generate random samples which are also $\epsilon$ samples.

I guess the question should be broken down into : 
1. Known algorithms to construct the medial axis $M$
2. Known algorithms to perform $\epsilon$-sampling.

I'm asking because I'd like to implement such an algorithm and I don't have a clue where to start.
I think the difficulty of this depends on how 'nice' your surface is. If the surface is smooth with a global curvature bound, one can prove that $f(x)$ is bounded away from zero. So any sufficiently fine/dense sample of points on $\Sigma$ would work. Although I think generating such a sample for an arbitrary surface still looks hard. 

If the surface is not smooth, a general procedure seems even harder. Consider $\Sigma$ a triangle in $\mathbb{R}^2$, then the corners need to part of your sample as they are part of the medial axis.
I think the difficulty of this depends on how 'nice' your surface is. If the surface is smooth with a global curvature bound, one can prove that $f(x)$ is bounded away from zero. So any sufficiently fine/dense sample of points on $\Sigma$ would work. Although I think generating such a sample for an arbitrary surface still looks hard. 

If the surface is not smooth, a general procedure seems even harder. Consider $\Sigma$ a triangle in $\mathbb{R}^2$, then the corners need to part of your sample as they are part of the medial axis.