<p>This answer has a problem; see comments below.</p>

<hr>

<p>Following up on my comments, here is the rest of the full answer:</p>

<p>First, take a look at the 2008 paper <a href="http://portal.acm.org/citation.cfm?id=1477073.1477544" rel="nofollow">Euclidean Skeletons of Digital Image and Volume Data in Linear Time by the Integer Medial Axis Transform
</a> by Hesselink and Roerdink.</p>

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

<p>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.</p>

CC BY-SA 2.5
2010-11-07T18:06:11.600Z
Linear time would be excellent. You say it computes $MB$. Do you mean the Feature Transform? If I read them correctly, in the above terms that would be $FT(p) = \{y \in G | f(y), |p-y| = DT(p)\}$  That wouldn't compute $MB$ along the way, though. Maybe I'm missing something.
Rumen
CC BY-SA 2.5
2010-11-07T20:25:47.877Z
Actually, you're correct! The algorithm I had in mind, too, won't work (it took me a bit to come up with a nasty enough case); I think I'm stuck back with something equivalent to the naive technique you described. I'd recommend un-accepting my answer so that your question gets more traffic -- sorry. :)
Daniel Apon
CC BY-SA 2.5
2010-11-07T17:17:33.867Z
2010-11-07T20:27:17.217Z
2010-11-07T20:27:17.217Z
Daniel Apon
<p>Consider a finite uniform grid $G$ in three dimensions with a function $f$ mapping integer grid positions $p$ to a boolean value $f(p)$ (i.e., a black/white volume image.)</p>

<p>A ball in $f$ is a set of grid points with center $c$ and radius $r$ where $f(p)$ is true for all $p \in G$ with euclidean distance $|c-p| \leq r$.</p>

<p>The <em>maximum ball transform</em> $MB$ finds for each grid point $p$ the radius $r$ of the largest ball in $f$ containing that point.  (Note: This is probably not the actual, commonly used name for this. However I don't know what else to call it.)</p>

<p>Are there good algorithms to compute this transform?</p>

<hr>

<p>I assume this is related to the (euclidean) distance transform. (Find for each grid point $p$ the radius of the largest disk in $f$ with center $p$.)</p>

<p>$DT(p) = min_{x \in f} |p-x|$</p>

<p>$MB(p) = max_{|x-p| &lt; DT(x)} DT(x)$</p>

<p>In the literature I can find algorithms that compute the euclidean $DT$ (and its reverse) in linear time. There are also algorithms to compute the <em>medial axis transform</em> $MAT$ (the set of all center points of the maximum balls).</p>

<p>Is there a faster algorithm than computing the $MAT$, iterating over all found maximum balls and naively tracking the largest one for each grid point? </p>

<hr>

<p><strong>Edit:</strong>
It seems this is sometimes known as <em>Thickness Distribution</em> or <em>Euclidean Opening Function</em>.</p>

<p>A recent paper computes an approximation: <a href="http://hal.archives-ouvertes.fr/hal-00529820" rel="nofollow">Fast and Accurate Approximation of the Euclidean Opening Function in Arbitrary Dimension</a> (D. Coeurjolly, 2010), (<a href="http://liris.cnrs.fr/david.coeurjolly/doku/lib/exe/fetch.php?media=presentation.pdf" rel="nofollow">presentation</a>)</p>

CC BY-SA 2.5
2010-11-06T19:08:21.213Z
Although I don't understand the last sentence of the post, and so may misunderstand the question, I think the likely answer is 'No.' The MAT contains all the information needed to compute $r$ for each point $p$, because it partitions the interior of the shape into regions whose maximal balls touch the same "section" of the boundary. Moreover, algorithms to compute MAT often implicitly sweep over all intermediate points.
Joseph O'Rourke
CC BY-SA 2.5
2010-11-06T19:44:18.480Z
Let me restate the last sentence: How can I compute MB quickly? Is computing MAT a good first step? How to continue? Scan convert all maximal balls (with max-blending)? That seems very inefficient.
Rumen
CC BY-SA 2.5
2010-11-06T20:56:51.900Z
Just wondering: do you need Euclidean balls, or might $\ell_1$ or $\ell_\infty$ balls suffice ?
Suresh Venkat
CC BY-SA 2.5
2010-11-06T22:30:46.987Z
I'm mainly looking for the Euclidean case.
Rumen
CC BY-SA 2.5
2010-11-06T22:31:57.777Z
Question: For $MB$, are you only interested in an algorithm to compute it for ALL points? If so, there is an implicit reduction to $MAT$, since knowing the radius to a maximum ball's center for each point allows you to instantly compute $MAT$ (given a 3-dimensional space and integer positions, there is at most constant number of points at a given radius from any point that you need to check) -- implying computing $MAT$ first won't cost you anything extra.
Daniel Apon
CC BY-SA 2.5
2010-11-06T22:42:32.980Z
Yes, for all points (where $f(p)$ is true).
Rumen
CC BY-SA 2.5
2010-11-06T22:50:15.333Z
Some typos on my previous comment: "reduction *from* MAT" and " *likely* won't cost". What I mean to say: if you can find an algorithm that computes $MB$ without using $MAT$ faster than one that computes $MB$ using $MAT$ first, then it implies a faster algorithm for $MAT$. That said, the later steps of iterating over the balls and tracking the largest per grid point may not be optimal; I don't have any immediate insight there.
Daniel Apon
CC BY-SA 2.5
2010-11-06T23:04:43.757Z
Probably worth pointing out, as an aside, that the grid points where $f$ is false won't be contained by any balls; making $MB$, as stated in the question, undefined at those points.
Daniel Apon
CC BY-SA 2.5
2010-11-08T18:55:39.180Z
@Rumen, does the above update answer your question ? no harm posting it as an answer and "accepting it" if it does
Suresh Venkat
CC BY-SA 2.5
2010-11-08T19:09:40.337Z
@Suresh Venkat: Not directly (it's only an approximation). Maybe there is no better answer though?
Rumen
<ds.algorithms><cg.comp-geom>
Maximum ball transform
Rumen
# Maximum ball transform

(Asked by: username_0 on 2010-11-06)

Consider a finite uniform grid $G$ in three dimensions with a function $f$ mapping integer grid positions $p$ to a boolean value $f(p)$ (i.e., a black/white volume image.)

A ball in $f$ is a set of grid points with center $c$ and radius $r$ where $f(p)$ is true for all $p \in G$ with euclidean distance $|c-p| \leq r$.

The *maximum ball transform* $MB$ finds for each grid point $p$ the radius $r$ of the largest ball in $f$ containing that point. (Note: This is probably not the actual, commonly used name for this. However I don't know what else to call it.)

Are there good algorithms to compute this transform?

---

I assume this is related to the (euclidean) distance transform. (Find for each grid point $p$ the radius of the largest disk in $f$ with center $p$.)

$DT(p) = min\_{x \in f} |p-x|$

$MB(p) = max\_{|x-p| < DT(x)} DT(x)$

In the literature I can find algorithms that compute the euclidean $DT$ (and its reverse) in linear time. There are also algorithms to compute the *medial axis transform* $MAT$ (the set of all center points of the maximum balls).

Is there a faster algorithm than computing the $MAT$, iterating over all found maximum balls and naively tracking the largest one for each grid point?

---

**Edit:**
It seems this is sometimes known as *Thickness Distribution* or *Euclidean Opening Function*.

A recent paper computes an approximation: [Fast and Accurate Approximation of the Euclidean Opening Function in Arbitrary Dimension](http://hal.archives-ouvertes.fr/hal-00529820) (D. Coeurjolly, 2010), ([presentation](http://liris.cnrs.fr/david.coeurjolly/doku/lib/exe/fetch.php?media=presentation.pdf))

**Tags:** ds.algorithms, cg.comp-geom
> **Comments:**
> **username_1**: Although I don't understand the last sentence of the post, and so may misunderstand the question, I think the likely answer is 'No.' The MAT contains all the information needed to compute $r$ for each point $p$, because it partitions the interior of the shape into regions whose maximal balls touch the same "section" of the boundary. Moreover, algorithms to compute MAT often implicitly sweep over all intermediate points.  
> **username_0**: Let me restate the last sentence: How can I compute MB quickly? Is computing MAT a good first step? How to continue? Scan convert all maximal balls (with max-blending)? That seems very inefficient.  
> **username_2**: Just wondering: do you need Euclidean balls, or might $\ell_1$ or $\ell_\infty$ balls suffice ?  
> **username_0**: I'm mainly looking for the Euclidean case.  
> **username_3**: Question: For $MB$, are you only interested in an algorithm to compute it for ALL points? If so, there is an implicit reduction to $MAT$, since knowing the radius to a maximum ball's center for each point allows you to instantly compute $MAT$ (given a 3-dimensional space and integer positions, there is at most constant number of points at a given radius from any point that you need to check) -- implying computing $MAT$ first won't cost you anything extra.  
> **username_0**: Yes, for all points (where $f(p)$ is true).  
> **username_3**: Some typos on my previous comment: "reduction *from* MAT" and " *likely* won't cost". What I mean to say: if you can find an algorithm that computes $MB$ without using $MAT$ faster than one that computes $MB$ using $MAT$ first, then it implies a faster algorithm for $MAT$. That said, the later steps of iterating over the balls and tracking the largest per grid point may not be optimal; I don't have any immediate insight there.  
> **username_3**: Probably worth pointing out, as an aside, that the grid points where $f$ is false won't be contained by any balls; making $MB$, as stated in the question, undefined at those points.  
> **username_2**: @Rumen, does the above update answer your question ? no harm posting it as an answer and "accepting it" if it does  
> **username_0**: @Suresh Venkat: Not directly (it's only an approximation). Maybe there is no better answer though?  

---

## 1 answers

### Answer by username_3 on 2010-11-07. Score: 1

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](http://portal.acm.org/citation.cfm?id=1477073.1477544) 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.

> **Comments:**
> **username_0**: Linear time would be excellent. You say it computes $MB$. Do you mean the Feature Transform? If I read them correctly, in the above terms that would be $FT(p) = \{y \in G | f(y), |p-y| = DT(p)\}$  That wouldn't compute $MB$ along the way, though. Maybe I'm missing something.  
> **username_3**: Actually, you're correct! The algorithm I had in mind, too, won't work (it took me a bit to come up with a nasty enough case); I think I'm stuck back with something equivalent to the naive technique you described. I'd recommend un-accepting my answer so that your question gets more traffic -- sorry. :)  

---

