![[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.