How to find points lie in unbounded voronoi cells?

Let P be the set of n points and Q is a subset of P of cardinality k. I want to make (at most) k clusters of P based on Voronoi diagram of Q. I could find the points lie in the bounded Voronoi cells using the routine 'inpolygon'. How do I find the points of P lie in the unbounded cells? I thought of having a bounding box of the Vornoi Diagram, but I do not know how to implement it. Please help me or provide me some source.

Thanks in advance

Answer 1

[Ronit]

Hello Ramesh,

To find the points of “P” that lie in the unbounded Voronoi cells, you can take help of the following steps:

1. Compute the Voronoi Diagram: Use “voronoin” function to compute the Voronoi diagram for the points in “Q”
2. Identify Unbounded Cells: In a Voronoi diagram, unbounded cells are those that extend to infinity. These cells are typically associated with Voronoi vertices that lie on the boundary of the convex hull of “Q”. Use “convhull” function for the above operation.
3. Bounding Box: You can create a large bounding box around your data points to help identify which Voronoi cells are unbounded. This is done by extending the range of your data points slightly beyond their “min” and “max” values.
4. Check for Unbounded Cells: For each Voronoi cell, check if any of its vertices lie outside the bounding box. If so, the cell is unbounded. Use “inpolygon” function to check which points in “P” lie within these unbounded cells.

To get more understanding for implementation, please go through the following MATLAB’s documentation links:

1. “voronoin” - https://www.mathworks.com/help/matlab/ref/voronoin.html
2. “convhull” - https://www.mathworks.com/help/matlab/ref/convhull.html
3. “inpolygon” - https://www.mathworks.com/help/matlab/ref/inpolygon.html

I hope this helps with the query!