![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
gusl* In 2D, the dual of a Voronoi diagram is defined by linking cells that share an edge. In 3D, we can still draw these lines, but will they form cells?
* What is the name of the diagram defined by the intersections between Voronoi cells and dual cells?
* There's a trivial O(n^3) algorithm for computing whether two cells share an edge / whether an edge is present in the dual graph. I'm sure you can do better with kd-trees. But can you do even better?
* One talks of smoothing a signal (e.g. through a low-pass filter). I haven't yet heard of smoothing a sample. But if we take each sample point and have it follow the gradient of its cell's area, we should get a smoother version of the sample. This idea makes me feel good, because it's non-parametric, at least on the surface.
It's not totally analogous to smoothing because:
* the outer points don't move, since their area is already infinite. So in the limit you will get a roughly uniform distribution that is concentrated... with signal smoothing, the limit you spreading yourself thin: the density converges to the 0 function.
* if you do it for more than 1 iteration, you get some non-trivial dynamics, as the points consider their neighbors' changing location.
* the idea of using Voronoi diagrams may not seem smooth enough: you consider your immediate neighbors while ignoring those further away. One idea is to simultaneously consider different metrics (with different weights). You could e.g. weight the horizontal direction more or less according to a parameter a: d^2 = a*x^2 + y^2. I would like to see a data structure for a whole range of a: it would let you query efficiently, and the smoothing operation would consider several different diagrams: you're now following the gradient of the expected change in area.
I don't really have applications for these ideas (other than two-sample tests). It's easy to go overboard with mathematical mind candy like this.
* What is the name of the diagram defined by the intersections between Voronoi cells and dual cells?
* There's a trivial O(n^3) algorithm for computing whether two cells share an edge / whether an edge is present in the dual graph. I'm sure you can do better with kd-trees. But can you do even better?
* One talks of smoothing a signal (e.g. through a low-pass filter). I haven't yet heard of smoothing a sample. But if we take each sample point and have it follow the gradient of its cell's area, we should get a smoother version of the sample. This idea makes me feel good, because it's non-parametric, at least on the surface.
It's not totally analogous to smoothing because:
* the outer points don't move, since their area is already infinite. So in the limit you will get a roughly uniform distribution that is concentrated... with signal smoothing, the limit you spreading yourself thin: the density converges to the 0 function.
* if you do it for more than 1 iteration, you get some non-trivial dynamics, as the points consider their neighbors' changing location.
* the idea of using Voronoi diagrams may not seem smooth enough: you consider your immediate neighbors while ignoring those further away. One idea is to simultaneously consider different metrics (with different weights). You could e.g. weight the horizontal direction more or less according to a parameter a: d^2 = a*x^2 + y^2. I would like to see a data structure for a whole range of a: it would let you query efficiently, and the smoothing operation would consider several different diagrams: you're now following the gradient of the expected change in area.
I don't really have applications for these ideas (other than two-sample tests). It's easy to go overboard with mathematical mind candy like this.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
(no subject)
Date: 2009-06-19 05:20 pm (UTC)(no subject)
Date: 2009-06-19 06:02 pm (UTC)Intersections between Delaunay and Voronoi I don't know. That's kind of a weird object.
If you care about a particular edge, it's linear time to determine whether it's Delaunay. If you compute the Delaunay, which takes O(n log n), then it's constant time. Download Triangle (by Shewchuk) to play around with this.
There's a huge industry around smoothing; dozens of papers every year, that in general do roughly what you're saying. Look up Amenta et al on Laplacian smoothing for a rare one that I actually respect (they prove stuff).
(no subject)
Date: 2009-06-19 06:03 pm (UTC)The computation of the Delaunay, on the other hand, *is* exponential in the dimension (even in terms of storage space).
(no subject)
Date: 2009-06-19 06:18 pm (UTC)what's their application of smoothing?
(no subject)
Date: 2009-06-19 06:20 pm (UTC)(no subject)
Date: 2009-06-19 06:23 pm (UTC)Smoothing is for making meshes with good aspect ratio.
I'm not going to be able to say more (battery low, going away for a week very soon).
Oh, Del has n^{d/2} d-simplices with appropriate ceil or floor, I can never remember. Vor has n cells no matter what (but many more lower-dimensional facets).