I'm trying to find all the neighbors of a given cell in a voronoi diagram. For example, given the following diagram, if I want to find the neighbors of the cell 1, then I should be able to return the points 2, 3 and 4.

enter image description here

Any hints on how to do so ?


I didn't explained myself very well, I only have the image (pixels with position and colors), not the graph itself. My struggle is that I just can't see an efficient way to create the graph form the image. In the image below you can see the problem better because I need an algorithm that recognizes black dots and from there search for all the neighbors.

enter image description here

  • $\begingroup$ How do you generate the diagram? During the tesselation the incident cells should be stored, so I do not fully understand your question. $\endgroup$ – Evil Nov 11 '17 at 4:41
  • 1
    $\begingroup$ Unless you generate the diagram as a mere bitmap, you should have a graph data structure holding the diagram. Neighbor information is found in the diagram, either explicitly or implicitly. This depends on the particular structure you use, please disclose it. (The neighbors are the points that share an edge with the given point.) $\endgroup$ – Yves Daoust Nov 11 '17 at 13:17
  • $\begingroup$ The diagram is given as an image, I have to process the image and create a data structure in order to represent the problem as a graph. It's easy when you have the graph though. $\endgroup$ – Francis Nov 11 '17 at 13:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.