Timeline for Maximum ball transform
Current License: CC BY-SA 2.5
20 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 8, 2010 at 19:09 | comment | added | Rumen | @Suresh Venkat: Not directly (it's only an approximation). Maybe there is no better answer though? | |
| Nov 8, 2010 at 18:59 | history | edited | Rumen | CC BY-SA 2.5 |
remove duplicated text
|
| Nov 8, 2010 at 18:55 | comment | added | Suresh Venkat | @Rumen, does the above update answer your question ? no harm posting it as an answer and "accepting it" if it does | |
| Nov 8, 2010 at 18:52 | history | edited | Rumen | CC BY-SA 2.5 |
Alternative names, approximation paper
|
| Nov 7, 2010 at 22:39 | vote | accept | Rumen | ||
| Nov 7, 2010 at 22:39 | |||||
| Nov 7, 2010 at 22:38 | vote | accept | Rumen | ||
| Nov 7, 2010 at 22:38 | |||||
| Nov 7, 2010 at 17:37 | vote | accept | Rumen | ||
| Nov 7, 2010 at 17:46 | |||||
| Nov 7, 2010 at 17:31 | vote | accept | Rumen | ||
| Nov 7, 2010 at 17:31 | |||||
| Nov 7, 2010 at 17:28 | vote | accept | Rumen | ||
| Nov 7, 2010 at 17:28 | |||||
| Nov 7, 2010 at 17:17 | answer | added | Daniel Apon | timeline score: 1 | |
| Nov 6, 2010 at 23:04 | comment | added | Daniel Apon | 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. | |
| Nov 6, 2010 at 22:50 | comment | added | Daniel Apon | 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. | |
| Nov 6, 2010 at 22:42 | comment | added | Rumen | Yes, for all points (where $f(p)$ is true). | |
| Nov 6, 2010 at 22:31 | comment | added | Daniel Apon | 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. | |
| Nov 6, 2010 at 22:30 | comment | added | Rumen | I'm mainly looking for the Euclidean case. | |
| Nov 6, 2010 at 20:56 | comment | added | Suresh Venkat | Just wondering: do you need Euclidean balls, or might $\ell_1$ or $\ell_\infty$ balls suffice ? | |
| Nov 6, 2010 at 19:44 | comment | added | Rumen | 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. | |
| Nov 6, 2010 at 19:08 | comment | added | Joseph O'Rourke | 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. | |
| Nov 6, 2010 at 17:20 | history | edited | Suresh Venkat |
edited tags
|
|
| Nov 6, 2010 at 10:50 | history | asked | Rumen | CC BY-SA 2.5 |