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
    If you terminate as soon as the candidate Voronoi cell is bounded, then no, because you'll usually end up terminating with a triangle.2012-04-02
  • 0
    Is there some reason to believe there is a nontrivial Voronoi cell around your point. That is, with an infinite number of points there might be a sequence of points approaching your selected points...well, see http://en.wikipedia.org/wiki/Nearest_neighbor_search2012-04-02
  • 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.

  • 1
    Actually, I think that was the missing insight. Once I have a closed cell, I have a maximal possible extent to the cell; once the nearest point not yet considered is too far to truncate the cell (that is, it as at least twice as far as the most distant vertex of the polygon bounding the cell), then no point at greater distance can affect the cell.2012-04-02
  • 0
    @MarcA.Pelletier, once you have a closed cell, nothing outside or on the boundary of the double size cell matters, but any new point inside the double size (or even the single size cell!) cell alters the actual Voronoi cell.2012-04-02
  • 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