Following up on my comments, here is the rest of the full answer:

First, take a look at the 2008 paper Euclidean Skeletons of Digital Image and Volume Data in Linear Time by the Integer Medial Axis Transform by Hesselink and Roerdink.

From my reading of your question, Section 2 of the paper is answering your question fairly explicitly. In particular, the process they use is essentially a scan across grid points.

Additionally, I wouldn't worry about the runtime being excessive. The algorithms involved are all linear time, and in fact experimental results from the paper show that the $IMA$ transform can be computed in a matter of seconds on a modern computer, even on data sets in the tens of millions. An especially nice piece of this: It appears $MB$ is computed along the way (again, Section 2), so if you simply stop the algorithm at that point, you should have an even faster runtime than "a matter of seconds" in practice.

This answer has a problem; see comments below.

Following up on my comments, here is the rest of the full answer:

First, take a look at the 2008 paper Euclidean Skeletons of Digital Image and Volume Data in Linear Time by the Integer Medial Axis Transform by Hesselink and Roerdink.

From my reading of your question, Section 2 of the paper is answering your question fairly explicitly. In particular, the process they use is essentially a scan across grid points.

Additionally, I wouldn't worry about the runtime being excessive. The algorithms involved are all linear time, and in fact experimental results from the paper show that the $IMA$ transform can be computed in a matter of seconds on a modern computer, even on data sets in the tens of millions. An especially nice piece of this: It appears $MB$ is computed along the way (again, Section 2), so if you simply stop the algorithm at that point, you should have an even faster runtime than "a matter of seconds" in practice.