2
$\begingroup$

Given a plane with an unbounded number of random points, is there an economical algorithm to find the Voronoi zone of any one selected point?

I've considered making a "sweeping" circle from that point, adding a line to the zone boundary as I meet points of increasing distance; would this solution be correct as soon as I have enough lines to enclose a polygon?

(The obvious corollary question is "If stopping as soon as the point is bounded isn't correct, when do I stop?")

  • 0
    @WillJagy: The points are randomly but uniformly (at large scale) distributed over the plane (they are the result of an isotropic noise function applied to the plane). Intuitively, that guarantees a nontrivial Voronoi cell though being proven wrong there would be just as good as a solution. :-)2012-04-02

1 Answers 1

1

The termination condition seems pretty simple in principle: You can terminate if, for every point on the boundary of the candidate Voronoi cell, there is no other site closer to it than the selected site is. If there is one, you include it in your working set, recompute the Voronoi cell, and repeat.

Of course, the way I've phrased this makes it an infinitary condition, but it should be possible to do some geometry and figure out how to test this directly in finite time. Perhaps someone with more fortitude or insight than I will come along and work it out explicitly.

  • 0
    @will: Ah, yes, I should have made it clear from the outset that the points are determinate. That is, given any finite area of the plane, I can enumerate the finite number of points contained in that area; so no surprise points can pop up. :-) Thanks again.2012-04-02