1

I have a rectangle R of side lenghts lx (horizontal) and lz (vertical) and area of A = lx*lz. In this rectangle, there are N randomly distributed points. I would like to split A into N sub-areas, where each sub-area is determined based on circles of growing radius around each point of the point cloud. As soon as two growing circles intersect, the resulting radical line should demark the local border between the sub-areas of two points. The borders of rectangle R should additionally delimit the sub-areas.

The expected result is sketched in this Figure: Expected sub-areas in an example with 6 points

The approximate procedure is artistically illustrated in this short Youtube movie: https://www.youtube.com/watch?v=BXNvcQTNWXM&ab_channel=stopmotionkim

To find the sub-areas, I am looking for an approximate or exact algorithm that (first priority) is efficient and scales well with N (better than O[N^2], ideally O[N], although I doubt that this is possible), and (second priority), if approximate, is as accurate as possible.

Does anybody know how to do this or has a hint how one could start? Thanks a lot for your help!

Christoph Heim
  • 11
  • 2
  • Have you written any code or are you looking for a theoretical answer? Maybe [CS stack exchange](https://cs.stackexchange.com/) will be a better fit. – mnestorov Oct 06 '20 at 08:24
  • Will all circles grow simultaneously, or with delays (as on the video) ? –  Oct 06 '20 at 18:36

1 Answers1

0

What you are looking for is Clipped Voronoi Diagram. It can be calculated in O(nlogn). I suggest you to look at those papers/courses to have a better idea of the underlying theory and computational methods:

Efficient Computation of 3D Clipped Voronoi Diagram
Computational Geometry

For a Python implementation, see this post

Gilles-Philippe Paillé
  • 3,195
  • 1
  • 8
  • 21
  • The 3D diagram is overkill, this is a planar problem. (The move from 2D to 3D is not trivial.) –  Oct 06 '20 at 18:35