Tell me more ×
Cross Validated is a question and answer site for statisticians, data analysts, data miners and data visualization experts. It's 100% free, no registration required.
up vote 2 down vote favorite

N random points in a ball in $\mathbb{R}^n$ induce a Voronoi splitting or tessellation.
Is there a way of random-generating points so that the volumes of the Voronoi cells are roughly equal ?

This is 3 related questions, for $L_1, L_2$ and $L_\inf$ norms (in 3d, random splits of an octahedron, sphere, cube).

(Where does this come from ? In searching for a minimum of a noisy function of $n$ variables, one may start N parallel searches from N random start points, e.g. 10 start points in 5d.
Small Voronoi cells are then inefficient, equal-sized cells most efficient.)

share|improve this question
Not my area, but are low-discrepancy sequences any use? – onestop Jun 11 '12 at 12:28
You need to stipulate something about the boundaries of the domain, because always there will be unbounded cells of infinite area in $\mathbb{R}^n$. Also--at least in the $L_2$ case--it is unclear that maximizing efficiency would be good for the algorithm. With $n$ large, the points would have to be very close to equally spaced, which might reduce the chances of being near a minimum. – whuber♦ Jun 11 '12 at 12:36
@onestop That's a good guess, but there's a subtle twist: here, the OP appears to want a "low-discrepancy" set of points that (a) are conditioned to lie within some specified finite-volume region (for simple regions this is no problem) and (b) that have a predetermined count $N$ (equal to the number of processors): this is the subtle part. – whuber♦ Jun 11 '12 at 12:38
@whuber, yes finite volume: octahedron, sphere, cube; and smallish N n, e.g. 10 points in R5 -- the general case is surely difficult. Monte-Carlo people seem to often take just Uniform(0,1) i.i.d points in a cube; could a U-shaped distribution be better ? Onestop: thanks, will look, but it's not clear to me how they equi-volume. – Denis Jun 11 '12 at 14:25
1  
I really don't think you want to stop with just an equal-volume criterion, Denis. Look at the 2D case, for instance (it generalizes): pick $(r,\phi)$ so that $\phi$ is uniformly distributed on $[0, 2\pi/N)$ and set $x_i = (\cos(\phi+2\pi i/N), \sin(\phi+2\pi i/N))$, $i=0, 1, \ldots, N-1$. The Voronoi cells of $\{x_i\}$ within any disk concentric with the origin have exactly equal 2-volumes. Depending on how $r$ is distributed, you might never start near the origin or you might never start near the boundary of the disk. That sounds like poor behavior for a search algorithm. – whuber♦ Jun 11 '12 at 17:27

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.