in reply to Re^2: Better maps with Math::Geometry::Voronoi, (Working* code)
in thread Better maps with Math::Geometry::Voronoi, and a Challenge for Math Monks

One question - does it deal with shapes that have holes in them?

You know, the more I think about this, the more I am convinced (on the basis of my own brand of logic rather than any real mathematic understanding), that it isn't possible to have a 'hole' in a Voronoi diagram?

If someone knows better, please demonstrate?

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.
"Too many [] have been sedated by an oppressive environment of political correctness and risk aversion."
  • Comment on Re^3: Is it possible to get a 'hole' in a Veronoi diagram?

Replies are listed 'Best First'.
Re^4: Is it possible to get a 'hole' in a Veronoi diagram?
by Corion (Patriarch) on Jul 03, 2008 at 18:57 UTC

    I don't think you can get even a polygon that is not convex, because by construction, you start out with a convex polygon (the whole space) and all areas you're clipping away from that are using lines/half-spaces perpendicular to the line connecting the two points. If you assume a metric space with a symmetric metric respecting the triangle inequality, I have the feeling that you encounter a contradiction fairly quickly, but I haven't written down any formal proof either :)

[reply]

      That all sound plausible to me. Greek, but plausible :)

      My 'proof' is somewhat erm, simpler. Working with Sam's phone box analogy from above, for there to be a hole in the middle of the phone boxes would imply an area of space between them that isn't "closest" to any of them. Which just doesn't make any sense.

      Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
      "Science is about questioning the status quo. Questioning authority".
      In the absence of evidence, opinion is indistinguishable from prejudice.
[reply]
Re^4: Is it possible to get a 'hole' in a Veronoi diagram?
by roboticus (Chancellor) on Jul 03, 2008 at 20:02 UTC
    BrowserUk:

    You can't get a polygon with a hole in it in a Voronoi diagram. He's starting with a voronoi diagram and then combining adjacent polygons of the same "color". You may then get a polygon with a "hole" in it. Example: A nine by nine array of points, where the center one is red, the eight adjacent points are all blue, and the rest of the points are red. If you take one of the blue points and merge all adjacent blue polygons until you run out, you'll get a small red polygon in the center (originally in the voronoi diagram), then a polygon surrounding that one that's blue, etc. I believe that's what was meant.

    ...roboticus
[reply]
[reply]

In Section Meditations