Medial-axis sampling [455,635,971]

Figure 5.30: The medial axis is traced out by the centers of the largest inscribed balls. The five line segments inside of the rectangle correspond to the medial axis.

Rather than trying to sample close to the boundary, another strategy is to force the samples to be as far from the boundary as possible. Let $(X,\rho)$ be a metric space. Let a maximal ball be a ball $B(x,r) \subseteq X$ such that no other ball can be a proper subset. The centers of all maximal balls trace out a one-dimensional set of points referred to as the medial axis. A simple example of a medial axis is shown for a rectangular subset of ${\mathbb{R}}^2$ in Figure 5.30. The medial axis in ${\cal C}_{free}$ is based on the largest balls that can be inscribed in $\operatorname{cl}({\cal C}_{free})$. Sampling on the medial axis is generally difficult, especially because the representation of ${\cal C}_{free}$ is implicit. Distance information from collision checking can be used to start with a sample, ${\alpha }(i)$, and iteratively perturb it to increase its distance from $\partial{\cal C}_{free}$ [635,971]. Sampling on the medial axis of $W \setminus {\cal O}$ has also been proposed [455]. In this case, the medial axis in ${\cal W}\setminus {\cal O}$ is easier to compute, and it can be used to heuristically guide the placement of good roadmap vertices in ${\cal C}_{free}$.